The largest prefix of the vertex array forming a convex polygon

Question

Related: Splitting a polygon - removing concave points to create convex polygons

I am looking for an algorithm to do the following:

The input is an array of two-dimensional points (P ₀ ... P _N-1 ). The length N of the array changes (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 edges are not necessarily adjacent pairs in an array.

What is the most efficient algorithm for finding the maximum of M such that this convex polygon exists?

My current algorithm is very inefficient. I test with M = 3, then M = 4, M = 5, etc., Calculate the body, then check that all P ₀ ... P _M-1 are the vertices of the body, if not, then I exit the loop and return the 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) will make the polygon non-convex)

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

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

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

This example shows why it is not enough to take the convex hull of all the set points and find the prefix that is its subset. (3,-3) cannot be part of a convex polygon consisting of the first five points, because the previous point (2,-1) will no longer lie on the body. But this is (3,-3) , which should be rejected, although it lies on the body of all six points, but (2,-1) does not.

Examples of invalid entries:

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

Answer 1

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

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

• Find the point, P, in the triangle of the first three points.

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

• Until we are at the end of the list, find the next point position in the sorted list.

• If inserting a point makes a concave polygon, goto 6. (This can be verified by simply checking the new adjacent two turns and the current turn)

• Insert point and go 3.

• Done.

The main edge case that you need to handle here is when the insert is at one end of the list, since the list is actually circular. One easy way to handle this is to insert it at each angle and at a + - 2pi angle for each point.

Answer 2

I think you need an incremental convex hull. Here are some 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 3

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

• Store the upper case and the lower points of the case in the search trees that are indicated by the X coordinate.
• When a new point arrives, find the upper and lower segments of the line covering its X value (search for trees).
• If the new point is between two lines, then it is not on the body. Refuse.
• Otherwise, insert a point into the upper or lower case (depending on which segment is closer).
• If the insertion of a point has turned adjacent points into internal corners, then they are not on the body. Refuse.
• Deal with edge cases such as new leftmost point, vertical points, etc.
• Continue until the desired number of points has been processed.

Answer 4

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