How to get the largest simple convex polygon from a complex polygon?

Question

Given a polygon that may be concave and may have holes, how can I get the largest simple convex polygon composed of a subset of its vertices?

ie, given the simple concave polygon:

p = Polygon([(30, 2.01), (31.91, 0.62), (31.18, -1.63), (28.82, -1.63), (28.09, 0.62),  (30, -0.001970703138552843)])

I want the largest simple convex polygon (perhaps the same but without the leftmost point (28.09, 0.62) and replace (28.82, -1.63) with (30, -1.63)). Like this:

This is just an unmeasured example. It may be that in fact both (28.09, 0.62) and (30, 2.01) must be removed, if this produces a larger area, such as might result from the cut indicated by the green line here:

But, assuming the first cut was correct, If we added a hole to the "other side":

p = Polygon([(30, 2.01), (31.91, 0.62), (31.18, -1.63), (28.82, -1.63), (28.09, 0.62),  (30, -0.001970703138552843)], 
[[(30.1,0.62), (30.1,1.25), (31, 1.25), (31,0.62)]])

the largest simple convex polygon might in such cases rotate to the other half of the polygon, so instead of dropping the previous point, it would drop (30, 2.01) and replace (31.91, 0.62) with a point between that and (31, -1.63). Obviously, in this case it would throw out all of the vertices of the hole.

commentary

Any hole that would be left intact inside the polygon would introduce a concave angle to the polygon by definition. in the case that there is a hole in the input polygon, at most one edge from it can remain in the output polygon (and, by definition of "simple polygon", that edge would be a member of the exterior coordinates).

There's a little bit of sloppiness in this definition so I should try to be more clear. All interior and exterior vertices are members of the set of possible points in the output simple polygon. So are all points that intersect the interior and exterior bounds (so the line segments between them). The selection of points should result in a simple, convex polygon that is inscribed in the source polygon. In the case that the source polygon is a simple, convex polygon, it should return the same polygon as output. It is quite possible to have whole families of candidate solutions with equal area. If they are maximal, any one of them will do.

Sketch approach: if you throw out cuts like in the sample with the green line, then all that remains are removal of points with projections from segments. So you could count all interior and exterior points as a set, and exclude subsets of 0 or more of them, then find the largest convex polygon. So, either just exclude the point or when excluding a point produces a new concave angle, project from the line segment on that side of the angle to the line segment on the other side of the polygon (this is the approach used to produce the first sample solution image). Revisiting the green line cuts, these are lines that bisect the polygon and tangent the center point of the concave angle. If this bisection must run perpendicular to the line from the center point to the centroid of the remaining polygon, then this is not much more complex. But I'm not sure that that is true. And in any case, that is a lot of polygons to consider.

note: at first I marked a duplicate, thinking this is essentially a more complicated version of another question (Finding largest subset of points forming a convex polygon but with holes). However, this approach does not allow for addition of new vertices in the solution. For example, Delaunay triangulation of the first shape in this article produces no new points:

[ 'POLYGON ((28.09 0.62, 28.82 -1.63, 30 -0.001970703138552843, 28.09 0.62))', 
  'POLYGON ((28.09 0.62, 30 -0.001970703138552843, 30 2.01, 28.09 0.62))', 
  'POLYGON ((30 2.01, 30 -0.001970703138552843, 31.91 0.62, 30 2.01))', 
  'POLYGON ((31.91 0.62, 30 -0.001970703138552843, 31.18 -1.63, 31.91 0.62))', 
  'POLYGON ((28.82 -1.63, 31.18 -1.63, 30 -0.001970703138552843, 28.82 -1.63))']

The article provided as possible duplicate only counts subsets of the points to find the maximal convex hull -- ie, it does not introduce points on the line.

Answer 1

I am not really sure your problem is well specified (or rather, they way you describe it it is reduced to a well-known, simpler problem).

First, let me introduce you the idea of the Convex Hull:

Given a list of points, the convex hull is the smallest convex (simple) polygon that contains all points.

The shape of the CH is essentially what you would get if you were to "place a rubber band" around the points so that it touches the outer ones.

Now, there is a straightforward property of the CH:

Given a set of points, the are of their CH is larger (or equal) than the area of any other (simple) polygon those may form.

This is true because i) If they form a convex polygon, then they form the CH by definition. ii) otherwise, they form some non convex shape. Visually, you can get from the CH to that non convex shape by "removing triangles" comprised of 2 points on the CH and one inner point. So you are removing area, so the CH has the largest area.

So, the largest convex polygon comprise of all the vertices is the CH.

Now, about selecting a subset of the original vertices: This will obviously give you a smaller (or equal) -sized shape. So there is no point in selecting any subset, really.

Also, holes don't really impact this argument. Keeping the whole is obviously to your benefit, since you can add the area around the hole.

So, the final answer (unless I missed something), is that all you need is the Convex Hull.

Fortunately, there are some good python libraries for computing, plotting and messing around with convex hulls.