largest prefix of array of vertices that forms a convex polygon

Question

Related to: Polygon Decomposition - Removing Concave Points to Form Convex Polygons

I am looking for an algorithm to do the following:

The input is an array of 2D points (P₀…P_N-1). The length N of the array varies (3 ≤ N < ∞)
For any M ≤ N there may or may not be a convex polygon whose vertices are P₀…P_M-1 in some order.

Note the edges are not necessarily adjacent pairs in the array.

What is the most efficient algorithm to find the maximum M such that this convex polygon exists?

My current algorithm is very inefficient. I test with M=3 then M=4, M=5 etc., compute the hull then test that all P₀…P_M-1 are vertices of the hull, if not then I break out of the loop and return M-1.

Example #1: [(-2,2), (2,2), (-2,-2), (-1,1)]

result: 3 (because the first three points form a triangle but adding P₃ = (-1,1) would make the polygon non-convex)

Example #2: [(-2,2), (2,2), (-2,-2), (1,-1)]

result: 4 (because a convex quadrilateral can be constructed from all 4 points in the array)

Update Example #3: [(-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1)]
result: 4.

This example demonstrates why it is not sufficient to take the convex hull of all supplied points and find a prefix that is a subset of it. (3,-3) cannot be part of a convex polygon consisting of the first five points because then the previous point (2,-1) would no longer lie on the hull. But it is (3,-3) that must be rejected, even though it lies on the hull of all six points and (2,-1) does not.

Examples of invalid inputs:

• [(-1,-1), (0,0)] (too few points)
• [(-1,-1), (0,0), (1,1), (1, -1)] (first three points are colinear: I would not expect the algorithm to be able to handle this.)

Answer 1

I think you want an incremental convex hull. Here are a few links:

• http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/incrementCH.htm
• http://ww3.algorithmdesign.net/handouts/IncrementalHull.pdf
• http://www.fandm.edu/computer-science/professors-emeriti/anderson/jay-martin-anderson/research-and-development/portal-algorithm-visualization-in-computational-geometry/convex-hull-an-incremental-algorithm

Answer 2

You can do this in O(m lg m) time.

• Store the upper hull and lower hull points in search trees keyed by X coordinate.
• When a new point arrives, find the upper and lower line segments covering its X value (search the trees).
• If the new point is between the two lines, then it is not on the hull. Give up.
• Otherwise, insert the point into the upper or lower hull (whichever has the closer line segment).
• If inserting the point turned the adjacent points into interior corners, then they are not on the hull. Give up.
• Deal with edge cases like new left-most point, vertical points, etc.
• Continue until the desired number of points are processed.

Answer 3

There is a very simple O(m log m) solution to this.

Given that there are at least 3 points and the first 3 are not collinear:

1. Find a point, P, in the triangle of the first 3 points.

2. Sort the 3 points by their angle relative to P (counterclockwise). (This sorted list will be the convex hull)

3. While we aren't at the end of the list, find the next point's position in the sorted list.

4. If inserting the point will make the polygon concave, goto 6. (This can be checked by just checking the new neighboring two turns and the current turn)

5. Insert the point and goto 3.

6. Done.

The main edge case that you have to handle here is when the insertion is at one of the ends of the list, since the list is actually circular. One simple way to handle this is for each point insert it at its angle and at its angle +- 2pi.

Answer 4

What if you try a kind of binary search? Every time the entire prefix forms a convex polygon, double the size of the prefix. Every time it fails, shrink the size of the prefix to halfway between the current size and the previous size.