求离散点凸包

The Convex Hull of a

2D Point Set or Polygon

by Dan Sunday

Computing a convex hull (or just "hull") is one of the first sophisticated geometry algorithms, and there are many variations of it.The most common form of this algorithm involves determining the smallest convex set (called the "convex hull") containing a discrete set of points.This algorithm also applies to a polygon, or just a set of segments, whose hull is the same as the hull of its vertex point set.There are numerous applications for convex hulls: collision avoidance, hidden object determination, and shape analysis to name a few.

The most popular algorithms are the "Graham scan" algorithm [Graham, 1972] and the "divide-and-conquer" algorithm [Preparata & Hong, 1977]. Implementations of both these algorithms are readily available (see [O'Rourke, 1998]). Both are O(n log n) time algorithms, but the Graham has a low runtime constant in 2D and runs very fast there. However, the Graham algorithm does not generalize to 3D and higher dimensions whereas the divide-and-conquer algorithm has a natural extension. We do not consider 3D algorithms here (see [O'Rourke, 1998] for more information).

Here is a list of some well-known 2D hull algorithms.For the speed, n = # points in the input set, and h = # vertices on the output hull (Note that hn, so nhn²). The list is ordered by date of first publication.

Convex Hulls

The convex hull of a geometric object (such as a point set or a polygon) is the smallest convex set containing that object.There are many equivalent definitions for a convex set S. The most basic of these is:

Def 1.A set S is convex if whenever two points P and Q are inside S, then the whole line segment PQ is also in S.

But this definition does not readily lead to algorithms for constructing convex sets.A more useful definition states:

Def 2. A set S is convex if it is exactly equal to the intersection of all the half planes containing it.

It can be shown that these two definitions are equivalent.However, the second one gives us a better computational handle, especially when the set S is the intersection of a finitenumber of half planes. In this case, the boundary of a compact set is bounded by a polygon in 2D, and a polyhedron in 3D. Then, the convex set can be identified with this polygon or polyhedron.

Def 3. The convex hull of a finite point set S = {P} is the smallest 2D polygon(or polyhedron in 3D) that contains S. That is, there is no other polygon (or polyhedron)withS

Also, this convex hull has the smallest area and the smallest perimeter of all polygons containing the set S.

Convex Hull Algorithms

This month we will cover two similar fast 2D hull algorithms: the Graham scan, and Andrew's Monotone Chain algorithm.They both use a similar idea, and are implemented as a stack.In practice, they are both very fast, but Andrew's algorithm will execute slightly faster since its sort comparisons are more efficient.An implementation of Andrew's algorithm is given below in our chainHull_2D() routine.

The "Graham Scan" Algorithm

The Graham scan algorithm [Graham, 1972] is often cited ([Preparata & Shamos, 1985], [O'Rourke, 1998]) as the first "computational geometry" algorithm. As the size of the geometric problem (namely, n = the number of points in the set) increases, it achieves the optimal asymptotic efficiency of O(n log n) time. This algorithm and its implementation has been covered in great detail by [O'Rourke, 1998, Sect 3.5, 72-86] with downloadable C code available from his web site: Computational Geometry in C. We do not repeat that level of detail here, and only give a conceptual overview of the algorithm. The O(n log n) time for the Graham scan is spent doing an initial radial sort of the input set points. After that, the algorithm employs a stack-based method which runs in just O(n) time. In fact, the method performs at most 2n simple stack push and pop operations. Thus it executes very rapidly, bounded only by the speed of sorting.

Let S = {P} be a finite set of points. The algorithm starts by picking a point in S known to be a vertex of the convex hull. This can be done in O(n) time by selecting the rightmost lowest point in the set; that is, a point with first a minimum (lowest) y coordinate, and second a maximum (rightmost) x coordinate. Having selected this base point, call it P₀, the algorithm then sorts the other points P in S by the increasing counter-clockwise (ccw) angle the line segment P₀P makes with the x-axis. If there is a tie and two points have the same angle, discard the one that is closest to P₀. For efficiency, it is important to note that the sort comparison between two points P₁and P₂can be made without actually computing their angles. In fact, computing angles would use slow inaccurate trigonometry functions, and doing these computations would be a bad mistake. Instead, one just observes that P₂would make a greater angle than P₁if (and only if) P₂lies on the left side of the directed line segment P₀P₁as shown in the following diagram. This condition can be tested by a fast accurate computation that uses only 5 additions and 2 multiplications. The code for this test was given in the isLeft() routine from Algorithm 1 about the Area of Triangles and Polygons.

After sorting, let the ccw radially ordered point set be S = {P₀, P₁, ..., P_n1}. It looks like a fan with a pivot at the point P₀.

We next loop through the points of S one-by-one testing for convex hull vertices. The algorithm is an inductive incremental procedure using a stack of points. At each stage, we save (on the stack) the vertex points for the convex hull of all points already processed. This is the induction condition. We start with P₀and P₁on the stack. Then at the k-th stage, we add the next point P_k, and compute how it alters the prior convex hull.Because of the way S was sorted, P_k is outside the hull of the prior points P_i with ik, and it must be added as a new hull vertex on the stack. But it's addition may cause previous stack points to no longer be a hull vertices. If this happens, the previous points must be popped off the stack and discarded. One tests for this by checking if the new point P_k is to the left or the right of the line joining the top two points of the stack. Again, we use the routine isLeft() to quickly make this test. If it is on the left, then prior hull vertices remain intact, and P_k just gets pushed onto the stack. But, if it is on the right side of this line, then the prior point at the stack top gets absorbed into the new hull, and that prior point must be popped off the stack. This test against the line at the stack top continues until either P_k is left of that line or the stack is reduced to the single base point P₀. In either case, P_k gets pushed onto the stack, and the algorithm proceeds to the next point P_k+1in the set. The different possibilities involved are illustrated in the following diagram.

It is easy to understand why this works by viewing it as an incremental algorithm.The old stack S_k1= {P₀, ..., P_t2, P_k1}, with P_k1at the top, is the convex hull of all points P_iwithi<k. The next point P_k is outside this hull since it is left of the line P₀P_k1which is an edge of that hull. To incrementally extend the hull S_k1to include P_k, we need to find the two tangents from P_k to S_k1. One tangent is clearly the line P_kP₀. The other is a line P_kP_Tsuch that P_k is left of the segment in S_k1preceding P_Tand is right of the segment following P_T(when it exists). This uniquely characterizes the second tangent since S_k1is a convex polygon. The way to find P_Tis simply to search from the top of the stack down until the point with the property is found. The points above P_Tin S_k1are easily seen to be contained inside the triangleP₀P_TP_k, are thus no longer on the hull extended to include P_k, and can be discarded by popping them off the stack during the search for P_T. So, the k-th convex hull is the new stack S_k= {P₀, ..., P_T, P_k}.

At the end when k=n1, the points remaining on the stack are precisely the ordered vertices of the convex hull's polygon boundary. Note that for each point of S there is one push and at most one pop operation, giving a maximum of 2n stack operations for the whole algorithm.

This procedure is summarized by the following pseudo-code.

Pseudo-Code: Graham Scan Algorithm

Input: a set of pointsS = {P = (P.x,P.y)}

Select the rightmost lowest point P₀inS

SortS angularly about P₀as a center.

For ties, discard the closer points.

Let P[N] be the sorted array of points.

Push P[0]=P₀and P[1] onto a stack.

while i < N

{

Let P_T1= the top point on

Let P_T2= the second top point on

if (P[i] is strictly left of the line P_T2to P_T1) {

Push P[i] onto

i++ // increment i

}

else

Pop the top point P_T1off the stack

}

Output:= the convex hull ofS.

Andrew's Monotone Chain Algorithm

[Andrew, 1979] discovered an alternative to the Graham scan that uses a linear lexographic sort of the point set by the x- and y-coordinates.This may be an advantage if this order is already known for a set which is often the case.Even if sorting is required, this is a faster sort than the angular Graham-scan sort with a more complicated comparison function.The "Monotone Chain" algorithm computes the upper and lower hulls of a monotone chain of points, and so we refer to it as the "Monotone Chain" algorithm.Like the Graham scan, it runs in O(n log n) time due to the sort time. After that, it only takes O(n) time to compute the hull. This algorithm also uses a stack in a manner very similar to Graham's algorithm.

First the algorithm sorts the point set S = {P₀, P₁, ..., P_n1} by increasing x and then y coordinate values. Let the minimum and maximum x-coordinates be x_min and x_max. Clearly, P₀.x = x_min, but there may be other points with this minimum x-coordinate. Let P_--be the point in S with P.x = x_min first and then min y among all such points. Also, let P_-+be the point with P.x = x_min first and then max y second. Note that P_--= P_-+when there is a unique x-minimum point. Similarly define P_+-and P₊₊as the points with P.x = x_maxfirst, and then y min or max second. Again note that P_+-= P₊₊when there is a unique x-maximum point. Next, join the lower two points, P_--and P_+-to define a lower lineL_min. Also, join the upper two points, P_-+and P₊₊to define an upper line L_max. These points and lines are shown in the following example diagram.

The algorithm now proceeds to construct a lower convex vertex chain_min below L_min and joining the two lower points P_--and P_+-; and also an upper convex vertex chain_max above L_max and joining the two upper points P₊₊and P_-+. Then the convex hullof S is constructed by joining_min and_max together.

The lower or upper convex chain is constructed using a stack algorithm almost identical to the one used for the Graham scan.For the lower chain, start with P_--on the stack. Then process the points of S in sequence. Only consider points strictly below the lower line L_min . Suppose that at any stage, the points on the stack are the convex hull of points belowL_min that have already been processed. Now consider the next point P_k that is below L_min . If the stack contains only the one point P_--then put P_k onto the stack and proceed to the next stage. Otherwise, determine whether P_k is strictly left of the line between the top two points on the stack. If it is, put P_k onto the stack and proceed. If it is not, pop the top point off the stack, and test P_k against the stack again. Continue until P_k gets pushed onto the stack. After this stage, the stack again contains the vertices of the lower hull for the points already considered. The geometric rationale is exactly the same as for the Graham scan. After all points have been processed, push P_+-onto the stack to complete the lower convex chain.

The upper convex chain_max is constructed in an analogous manner, but processes S in decreasing order {P_n1, P_n-2, ..., P₀}, starts at P₊₊, and considers only points aboveL_max. Once the two hull chains have been found, it is easy to join them together (but be careful to avoid duplicating the endpoints).

Pseudo-Code: Andrew's Monotone Chain Algorithm

Input: a setS = {P = (P.x,P.y)} of N points

SortS by increasing x- and then y-coordinate.

Let P[] be the sorted array of N points.

Get the points with 1st x min or max and 2nd y min or max

minmin = index of P with min x first and min y second

minmax = index of P with min x first and max y second

maxmin = index of P with max x first and min y second

maxmax = index of P with max x first and max y second

Compute the lower hull stack as follows:

(1) Let L_min be the lower line joining P[minmin] with P[maxmin].

(2) Push P[minmin] onto the stack.

(3) for i = minmax+1 to maxmin-1 (between the min and max)

{

if (P[i] is above or on L_min)

Ignore it and continue.

while (there are at least 2 points on the stack)

{

Let P_T1= the top point on the stack.

Let P_T2= the second point on the stack.

if (P[i] is strictly left of the line from P_T2to P_T1)

break out of this while loop.

Pop the top point P_T1off the stack.

}

Push P[i] onto the stack.

}

(4) Push P[maxmin] onto the stack.

Similarly, compute the upper hull stack.

Let= the join of the lower and upper hulls.

Output:= the convex hull ofS.

Implementation

Here is a "C++" implementation of the Chain Hull algorithm.

// Copyright 2001, softSurfer (www.softsurfer.com)

// This code may be freely used and modified for any purpose

// providing that this copyright notice is included with it.

// SoftSurfer makes no warranty for this code, and cannot be held

// liable for any real or imagined damage resulting from its use.

// Users of this code must verify correctness for their application.

// Assume that a class is already given for the object:

// Point with coordinates {float x, y;}

//===================================================================

// isLeft(): tests if a point is Left|On|Right of an infinite line.

// Input: three points P0, P1, and P2

// Return: >0 for P2 left of the line through P0 and P1

// =0 for P2 on the line

// <0 for P2 right of the line

// See: the January 2001 Algorithm on Area of Triangles

inlinefloat

isLeft( Point P0, Point P1, Point P2 )

{

return(P1.x - P0.x)(P2.y - P0.y) - (P2.x - P0.x)(P1.y - P0.y);

}

//===================================================================

// chainHull_2D(): Andrew's monotone chain 2D convex hull algorithm

// Input: P[] = an array of 2D points

// presorted by increasing x- and y-coordinates

// n = the number of points in P[]

// Output: H[] = an array of the convex hull vertices (max is n)

// Return: the number of points in H[]

int

chainHull_2D( Point P,intn, Point H )

{

// the output array H[] will be used as the stack

intbot=0, top=(-1);// indices for bottom and top of the stack

inti;// array scan index

// Get the indices of points with min x-coord and min|max y-coord

intminmin = 0, minmax;

floatxmin = P[0].x;

for(i=1; i<n; i++)

if(P[i].x != xmin)break;

minmax = i-1;

if(minmax == n-1) {// degenerate case: all x-coords == xmin

H[++top] = P[minmin];

if(P[minmax].y != P[minmin].y)// a nontrivial segment

H[++top] = P[minmax];

H[++top] = P[minmin];// add polygon endpoint

returntop+1;

}

// Get the indices of points with max x-coord and min|max y-coord

intmaxmin, maxmax = n-1;

floatxmax = P[n-1].x;

for(i=n-2; i>=0; i--)

if(P[i].x != xmax)break;

maxmin = i+1;

// Compute the lower hull on the stack H

H[++top] = P[minmin];// push minmin point onto stack

i = minmax;

while(++i <= maxmin)

{

// the lower line joins P[minmin] with P[maxmin]

if(isLeft( P[minmin], P[maxmin], P[i]) >= 0 && i < maxmin)

continue;// ignore P[i] above or on the lower line

while(top > 0)// there are at least 2 points on the stack

{

// test if P[i] is left of the line at the stack top

if(isLeft( H[top-1], H[top], P[i]) > 0)

break;// P[i] is a new hull vertex

else

top--;// pop top point off stack

}

H[++top] = P[i];// push P[i] onto stack

}

// Next, compute the upper hull on the stack H above the bottom hull

if(maxmax != maxmin)// if distinct xmax points

H[++top] = P[maxmax];// push maxmax point onto stack

bot = top;// the bottom point of the upper hull stack

i = maxmin;

while(--i >= minmax)

{

// the upper line joins P[maxmax] with P[minmax]

if(isLeft( P[maxmax], P[minmax], P[i]) >= 0 && i > minmax)

continue;// ignore P[i] below or on the upper line

while(top > bot)// at least 2 points on the upper stack

{

// test if P[i] is left of the line at the stack top

if(isLeft( H[top-1], H[top], P[i]) > 0)

break;// P[i] is a new hull vertex

else

top--;// pop top point off stack

}

H[++top] = P[i];// push P[i] onto stack

}

if

(minmax != minmin)

H[++top] = P[minmin]; // push joining endpoint onto stack

return top+1;

}

References

S.G. Akl & Godfried Toussaint, "Efficient Convex Hull Algorithms for Pattern Recognition Applications", Proc. 4th Int'l Joint Conf. on Pattern Recognition, Kyoto, Japan, 483-487 (1978)

A.M. Andrew, "Another Efficient Algorithm for Convex Hulls in Two Dimensions", Info. Proc. Letters 9, 216-219 (1979)

A. Bykat, "Convex Hull of a Finite Set of Points in Two Dimensions", Info. Proc. Letters 7, 296-298 (1978)

W. Eddy, "A New Convex Hull Algorithm for Planar Sets", ACM Trans. Math. Software 3(4), 398-403 (1977)

Ronald Graham, "An Efficient Algorithm for Determining the Convex Hull of a Finite Point Set", Info. Proc. Letters 1, 132-133 (1972)

R.A. Jarvis, "On the Identification of the Convex Hull of of a Finite Set of Points in the Plane", Info. Proc. Letters 2, 18-21 (1973)

M. Kallay, "The Complexity of Incremental Convex Hull Algorithms in R^d", Info. Proc. Letters 19, 197 (1984)

D.G. Kirkpatrick & R. Seidel, "The Ultimate Planar Convex Hull Algorithm?", SIAM Jour. Comput. 15, 287-299 (1986)

Joseph O'Rourke, Computational Geometry in C (2nd Edition), Chap. 3 "Convex Hulls in 2D" (1998)

Franco Preparata & Michael Shamos, Computational Geometry: An Introduction, Chap. 3 "Convex Hulls: Basic Algorithms" (1985)

Franco Preparata & S.J. Hong, "Convex Hulls of Finite Sets of Points in Two and Three Dimensions", Comm. ACM 20, 87-93 (1977)

源文档 <http://www.softsurfer.com/Archive/algorithm_0109/algorithm_0109.htm>
原文链接: https://www.cnblogs.com/sunliming/archive/2012/05/17/2506180.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍