Is there a linear-time algorithm for finding the convex hull of a complex polygon?

I know there's a worst-case O(n log n) algorithm for finding the convex hull of a complex polygon and a worst-case O(n) algorithm for finding the convex hull of a simple polygon. Is 开发者_Python百科there a worst-case O(n) algorithm for finding the convex hull of a complex polygon?

A complex polygon is a polygon where the line segments may intersect. Finding the convex hull of a complex polygon is equivalent to finding the convex hull of an unordered list of points.

---

If your point sets are such that some non-comparison based sorting mechanism (like radix sort) will be faster than comparison based methods, then it seems you can use the Graham scan algorithm (http://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf) to compute it. The time complexity of the Graham scan is dominated by the sorting step. The rest is linear.

---

I'm pretty sure not. Convex hull on arbitrary point sets can be shown to be equivalent to sorting. We can order an arbitrary point set and connect the points in sequence making it into a complex polygon, thereby reducing the problem on arbitrary point sets to yours.

Here is a link to a proof that convex hull is equivalent to sorting. I'm too damn lazy and too bad a typist to write it out myself.

---

In general, no there is not a O(n) solution. There is a pixelated version that is better than O(n log n). It is, however, so hobbled in other ways that you'd be crazy to use it in practice.

You render the first polygon (using verts 0, 1, 2) into screen space, then re-render the verts themselves using a distinct ID so they can be identified later. For example, you might clear the frame buffer to RGBA ffffffff and use fffffffe for space that is covered by the convex hull. Each vertex would be rendered using its ID as its RGBA; 00000000, 00000001, etc.

A 16-bit example:

fffffffffffffff
fffffff0fffffff
ffffffeeeffffff
fffffeeeeefffff
ffffeeeeeeeffff
fffeeeeeeeeefff
ff2eeeeeeeee1ff
fffffffffffffff

Checking a new point is a simple lookup in the current frame buffer. If the pixel it occupies is 'shaded' with polygon or with a vertex ID, the new vertex is rejected.

If the new vertex is outside the existing polygon, you find the first pixel between the new vertex and some point inside the convex hull (something in the middle of the first poly works fine) and march along the circumference of the hull - in both directions - until you find yourself on the far side of the hull from the new vertex. (I'll leave this as an exercise to the user. There are plenty of solutions that all suck, from an efficiency perspective.) Fill in the poly defined by these two points and the new vertex with the ID for polygon space - being careful not to erase any vertex IDs - and go on to the next pixel.

When you're done, any pixel which contains a vertex ID that is not completely surrounded by hull IDs is a convex hull vertex.

While the algorithm's complexity is O(n) with the number of vertices, it's deficiencies are obvious. Nobody in their right mind would use it unless they had a ridiculous, insane, staggering number of points to process so that nearly every vertex would be immediately rejected, and unless they could accept the limitation of an aliased result.

Friends don't let friends implement this algorithm.

---

If your points come from a finite universe (which is always the case in practice) you can do radix sort and then run Andrew's monotone chain algorithm.