'How to get the largest possible rectangle contained inside polygon
I am looking for a solution to get the largest possible rectangle inside a polygon.
currently I am using Arcpy for ArcGIS (python library), but there is no out of the box solution for getting it, instead there is a feature named Minimum Bounding Geometry (this returning the opposite result, a rectangle contains the polygon):
Example of the required result:
Solution 1:[1]
The best I've found is described in an academic paper titled "Finding the largest area rectangle of arbitrary orientation in a closed contour". Available in PDF, but copyright precludes me from linking the doc, which you can get to via the publisher https://www.sciencedirect.com/science/article/abs/pii/S0096300312003207.
The algorithm is O(N^3) and the authors claim there is no other with lower time complexity (which does NOT imply that it is most efficient for all use cases).
(My implementation (C#) was for a client who owns the code, so you will have to roll your own version unless it's been open sourced in the meantime.)
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | AlanK |