Polygon Decomposition - Removing Concave Points to Form Convex Polygons

Question

I would like to deconstruct the following polygon shown in blue removing all of the points from the polygon that cause concavity.

Currently, what I have been attempting to do is:

• Take each point out of the polygon
• Test the point to see if it falls within the polygon created by the rest of the set
• If true remove the point
• If false keep the point

This works in most cases, but in the previous case the points at (2,3) and (2,4) will not both be removed. In both cases either one of the points will be removed, but the other will not depending on the order which the array is passed in.

What I am wondering is this:

1. Is there some way to test to see if the polygon I am dealing with happens to have one of these cases (IE: 3 points of failure in a row?)
   or
2. Is there simply a more effective way of creating convex polygons?

Thank you.

Answer 1

I think perhaps you're looking for the convex hull?

The first algorithm that springs to mind is QuickHull. Initially, take the leftmost and the rightmost points, l and r. They must be on the hull.

Construct a first guess at the hull that's two outward faces, one from l to r and one from r to l. So you have a polygon with zero volume.

Divide all remaining points into those in front of lr and those in front of rl.

From then on, while any face has any points in front of it:

• find the furthest point from the face
• delete this edge and replace it with two edges, one from the original start point to the furthest point and one from the furthest point to the original end point
• of all the points that were in front of the old face, put those in front of the first of the new faces you've added into its in front set, put those in front of the second into its in front set and don't retain any reference to those now inside

At the end you'll have the convex hull.

Answer 2

Why not simply compute the convex hull of the points?

This is a well studied problem with a number of algorithms in books and online. A method of "sweeping angles" is particularly common, eg.

http://courses.csail.mit.edu/6.854/06/scribe/s25-rasmu-sweepline.pdf

Answer 3

What you are looking for is known as "convex hull" finding. Look here at wikipedia for algorithms for this problem. The "gift wrapping" algorithm is easy to implement. When yout found the hull, just remove all points that are not part of the hull.

Answer 4

Be aware that the Convex Hull is already implemented in some languages/environments.

Example in Mathematica:

<< ComputationalGeometry`; 
   data2D = {{4.4, 14}, {6.7, 15.25}, {6.9,12.8}, {2.1, 11.1}, {9.5, 14.9}, 
             {13.2, 11.9}, {10.3, 12.3}, {6.8, 9.5}, {3.3, 7.7}, {0.6, 5.1}, 
             {5.3, 2.4}, {8.45, 4.7}, {11.5,9.6}, {13.8, 7.3}, {12.9, 3.1}, 
             {11, 1.1}};

PlanarGraphPlot[data2D, ConvexHull[data2D]]

Output: