find the maximum convex area

Question

My question is very similar to Plow's Question; but with this difference:

How can I find the maximum convex area that can fit inside a non-convex region?

For an example, consider this non-convex region:

Any ideas or solution would be appreciated, thanks.

Answer 1

I wrote an answer to this question on the Mathematics Stack Exchange, and included an image which I created using a proof-of-concept implementation. The approach used for this might work for many practical applications, so I'll describe it here in a bit more detail.

Take your shape, and approximate it using a polygon. Identify runs of consecutive vertices which have interior angle > 180°. For each such run, iterate over all possible tangent lines. A tangent line to a run is a line connecting two consecutive vertices, at least one of which lies within the run. This means that the first line is defined by the last vertex before the run and the first vertex of the run. Take the inward-pointing half plane defined by this line, and intersect it with your shape, then compute the area and compare it against the best solution found so far.

In a simplistic approach, you'd simply set up a recursive scheme to try out all possible line combinations. this means a time complexity of O(n^m), where n is the number of vertices and m is the number of runs. In a more elaborate approach, you might leverage the fact that a line which does not intersect any other line inside the shape can be chosen independently from these others. The same holds for groups of lines which don't intersect one another inside the shape. Some choices of lines will cut away a different run altogether, such that the choice made for that run becomes irrelevant. So there is a lot of potential for clever algorithms here, depending on how much effort you can invest and what performance you require.

If your input is a polygon, then a line touching a non-convex vertex need not neccessarily coincide with either the incoming or the outgoing edge of the polygon, but might be rotated arbitrarily between these two limits. For this case, the above approach might yield a non-optimal solution. But since you stated in a comment that we may assume “non-polygonal” shapes, which I take to mean “smooth”. In this case, you have a well-defined tangent at every point, and every tangent will be reasonably close to an edge of the polygonal approximation.

Contrary to what I believed initially, the above should work for shapes with holes as well, since the boundary of a convex hole would result in a non-convex run of the shape itself. So that run will ensure that you investigate all possible ways to cut away the hole. SImilar for non-convex holes: the relevant runs will ensure you cut them out as well, without loosing any convex solutions.

Applied to your example image, the algorithm yields the following result:

The non-convex runs of vertices are colored red, the best set of lines in blue and the resulting area in green. The polygon behind this has 269 vertices. The implementation was done in Java, with little regard for performance, a brute-force recursive search of all possible combinations, and some assumptions which work for this input data but may fail in general.