2D凸包算法（四）：Quick Hull Algorithm

本文主要是介绍2D凸包算法（四）：Quick Hull Algorithm，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Quick Hull Algorithm 图示

在这里插入图片描述
先确定两个距离最大的点，连接后构成线。然后寻找离线的最远的点，构成三角形。以此类推，向外快速扩展，直到所有点都在凸包内。

时间复杂度： O(N²) ，是最有效率的演算法。
（预先剔除凸包内部大部分的点，而且不必预先排序所有点。）

具体思想：

找出最左点与最右点，连线，所有点分为上半部与下半部。（上半部与下半部分开求解）
处理上半部，找出上半凸包：
找到距离底线最远的点，形成一个三角形区域。（如果有许多点，就找最靠近左端点的那一点。避免凸包上多点共线。）
运用叉积运算，找出三角形外部的点，分为左、右两份。
至于三角形内部、三角形上的点，不会是凸包顶点，尽数剔除之。
左、右两份分别递归求解，直到找出上半凸包。（三角形的两边，分别做为左、右两份的底线。）
处理下半部，找出下半凸包，重复3-6步。

在这里插入图片描述

Quick Hull Algorithm 代码

目前测出当点数偏多时容易出现问题，code 仅供参考。

void quickhull(const vpdd &input)
{int min_x = 0, max_x = 0;for (int i = 0; i < input.size(); i++){if (input[i].first < input[min_x].first){min_x = i;}if (input[i].first > input[max_x].first){max_x = i;}}hull_quick.push_back(input[min_x]);hull_quick.push_back(input[max_x]);vpdd left, right;for (int i = 0, temp; i < input.size(); i++){if (i == min_x || i == max_x){continue;}temp = getsign(input[min_x], input[max_x], input[i]);if (temp == 0){continue;}if (temp < 0){left.push_back(input[i]);}else{right.push_back(input[i]);}}qhullrecur(right, input[min_x], input[max_x]);qhullrecur(left, input[max_x], input[min_x]);
}void qhullrecur(const vpdd &input, pdd a, pdd b)
{if (input.size() == 0){return;}vpdd right_p;pid max_ind = make_pair(-1, 0);for (int i = 0; i < input.size(); i++){if (get_right(a, b, input[i])){if (max_ind.second < dist(a, b, input[i])){max_ind.first = i;max_ind.second = dist(a, b, input[i]);}}}pdd c = input[max_ind.first];hull_quick.push_back(c);vpdd acr, bcr;for (int i = 0; i < input.size(); i++){if (get_right(a, c, input[i])){acr.push_back(input[i]);}if (get_right(c, b, input[i])){bcr.push_back(input[i]);}}qhullrecur(acr, a, c);qhullrecur(bcr, c, b);
}
int getsign(pdd a, pdd b, pdd c)
{int d = (c.first - a.first) * (b.second - a.second) - (c.second - a.second) * (b.first - a.first);return d;
}bool get_right(pdd a, pdd b, pdd c)
{return ((c.first - a.first) * (b.second - a.second) - (c.second - a.second) * (b.first - a.first)) > 0;
}double dist(pdd a, pdd b, pdd c)
{return abs((c.first - a.first) * (b.second - a.second) - (c.second - a.second) * (b.first - a.first));
}