Description
Convex Hull of a set of points, in 2D plane, is a convex polygon with minimum area such that each point lies either on the boundary of polygon or inside it. Now given a set of points the task is to find the convex hull of points.
思路
leetcode有一道非常相似的题，Erect the Fence
凸包问题的五种解法总结了5种方法，描述的比较清晰，但只给出了c语言的实现，下面摘录Graham的思路
Graham扫描法
-
把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。
-
把所有点的坐标平移一下，使 P0 作为原点，如上图。
-
计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。 （以上是准备步骤，以下开始求凸包）
-
以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。现在从步骤3求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。接下来开始找第三个点： 连接P0和栈顶的那个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。
-
如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。
-
当前点是凸包上的点，把它压入栈，执行步骤7。
-
检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点，返回步骤4。
下面是Graham扫描法的python实现
import math
# 求矢量积
def multiply(p0, p1, p2):
return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * (p1[1] - p0[1])
# 求向量p0p1的极角
def angle(p0, p1):
if p1[0] == p0[0]:
return math.pi / 2
arc = math.atan((p1[1] - p0[1]) / (p1[0] - p0[0]))
return arc if arc >= 0 else arc + math.pi
# 求两个点距离
def dis(p1, p2):
return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**0.5
def convex_hull(points):
# 去除重复点
points = list(set(points))
# 找到最下面的点
s = min(points, key=lambda p: (p[1], p[0]))
points.remove(s)
# 以最小面的点为坐标中心，对其他每个点按照极角的大小排序
points = sorted(points, key=lambda p: (angle(s, p), dis(s, p)))
stack = [s, points[0]]
for p in points[1:]:
while multiply(stack[-2], stack[-1], p) < 0:
stack.pop()
stack.append(p)
return stack
第5种算法, Monotone Chain Convex Hull
推荐最优的解法, 时间复杂度( O(nlogn) )
Python
# https://algorithmist.com/wiki/Monotone_Chain_Convex_Hull.py
def convex_hull(points):
"""Computes the convex hull of a set of 2D points.
Input: an iterable sequence of (x, y) pairs representing the points.
Output: a list of vertices of the convex hull in counter-clockwise order,
starting from the vertex with the lexicographically smallest coordinates.
Implements Andrew's monotone chain algorithm. O(n log n) complexity.
"""
# Sort the points lexicographically (tuples are compared lexicographically).
# Remove duplicates to detect the case we have just one unique point.
points = sorted(set(points))
# Boring case: no points or a single point, possibly repeated multiple times.
if len(points) <= 1:
return points
# 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
# Returns a positive value, if OAB makes a counter-clockwise turn,
# negative for clockwise turn, and zero if the points are collinear.
def cross(o, a, b):
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
# Build lower hull
lower = []
for p in points:
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
lower.pop()
lower.append(p)
# Build upper hull
upper = []
for p in reversed(points):
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
upper.pop()
upper.append(p)
# Concatenation of the lower and upper hulls gives the convex hull.
# Last point of each list is omitted because it is repeated at the beginning of the other list.
return lower[:-1] + upper[:-1]
C++
// https://algorithmist.com/wiki/Monotone_Chain_Convex_Hull.cpp
#include <algorithm>
#include <vector>
using namespace std;
typedef int coord_t; // coordinate type
typedef long long coord2_t; // must be big enough to hold 2*max(|coordinate|)^2
struct Point {
coord_t x, y;
bool operator <(const Point &p) const {
return x < p.x || (x == p.x && y < p.y);
}
};
// 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
// Returns a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
coord2_t cross(const Point &O, const Point &A, const Point &B)
{
return (A.x - O.x) * (coord2_t)(B.y - O.y) - (A.y - O.y) * (coord2_t)(B.x - O.x);
}
// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
vector<Point> convex_hull(vector<Point> P)
{
int n = P.size(), k = 0;
vector<Point> H(2*n);
// Sort points lexicographically
sort(P.begin(), P.end());
// Build lower hull
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
H[k++] = P[i];
}
// Build upper hull
for (int i = n-2, t = k+1; i >= 0; i--) {
while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
H[k++] = P[i];
}
H.resize(k);
return H;
}
Java
// https://algorithmist.com/wiki/Monotone_Chain_Convex_Hull.java
class Point implements Comparable<Point>
{
int x,y;
Point(int x, int y)
{
this.x = x;
this.y = y;
}
// sort first on x then on y
public int compareTo(Point other)
{
if( x == other.x)
return y - other.y;
else
return x - other.x;
}
// cross product of two vectors
public int cross( Point p)
{
return x * p.y - y * p.x;
}
// subtraction of two points
public Point sub( Point p)
{
return new Point( x - p.x, y - p.y );
}
public String toString()
{
return "Point[x=" + x + ",y=" + y + "]";
}
}
// Each point passed in via the "points" array should be unique.
// If duplicates are passed in the returned polygon might not be a convex hull.
public Point[] findHull( Point[] points)
{
int n = points.length;
Arrays.sort( points);
Point[] ans = new Point[2 * n]; // In between we may have a 2n points
int k = 0;
int start = 0; // start is the first insertion point
for(int i = 0; i < n; i ++) // Finding lower layer of hull
{
Point p = points[i];
while( k - start >= 2 && p.sub( ans[k-1] ).cross(p.sub( ans[k-2] ) ) > 0 )
k--;
ans[k++] = p;
}
k--; // drop off last point from lower layer
start = k ;
for(int i = n-1 ; i >= 0 ; i --) // Finding top layer from hull
{
Point p = points[i];
while( k - start >= 2 && p.sub( ans[k-1] ).cross(p.sub( ans[k-2] ) ) > 0 )
k--;
ans[k++] = p;
}
k--; // drop off last point from top layer
return Arrays.copyOf(ans, k); // convex hull is of size k
}
网友评论