What code will calculate the largest simple convex polygon that is
entirely contained within a given simple polygon (which may be
concave)?

- The resulting polygon will not generally be made up solely of vertices from
the original polygon.  
- If there is no unique largest polygon, it doesn't matter which of
the largest is returned.
- The code needs to be in C++, C#, VB.NET or Java (preferably not
Java) and should take and return an array of floating-point XY coordinates
representing the polygons.
- Please note that this is not quite the same as the largest member of
the optimal convex partition.

---

Request for Question Clarification by leapinglizard-ga on 05 Jan 2005 08:04 PST

The problem you describe is known variously as the potato-peeling problem, 
the convex skull, and the maximum area convex subset. Chang and Yap
proved some twenty years ago that the problem can be solved in O(n^7)
time and proposed an algorithm to do so, but the algorithm is not useful
in practice.

    [...] Chang and Yap prove that the potato-peeling problem
    can be solved in polynomial time in the general case. More
    precisely, they detail an O(n^7) time algorithm to extract Q
    from P. Since this algorithm uses complex geometric concepts and
    dynamic programming in several key steps, it is not tractable
    in practical applications.

Centre national de la recherche scientifique (CNRS): D. Coeurjolly and
J.-M. Chassery: Fast approximation of the maximum area convex subset
for star-shaped polygons 
http://liris.cnrs.fr/docs/RR-2004-006.pdf

Given these facts, would you be happy with something less than a general
solution? In other words, would you be content to see the implementation
of an algorithm that solves the potato-peeling problem for a restricted 
class of polygons, such as star-shaped polygons or polygons with
orthogonal sides?

leapinglizard

---

Clarification of Question by squareboy-ga on 05 Jan 2005 09:13 PST

It's quite a relief to know that I'm not being stupid!  I've already
written an algorithm that gives imperfect but useful results (based on
the convex partition) so I'll stick with that.

However, thank you very much for your assistance,

squareboy (drowning in a sea of polygons)