CODEWITHSUNDEEP
pythonc#polygonarcgisrectangles
MaKhatib
MaKhatib

Reputation: 41

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):

https://pro.arcgis.com/en/pro-app/latest/tool-reference/data-management/minimum-bounding-geometry.htm

Example of the required result:

1

Upvotes: 3

Views: 3264

Answers (1)

AlanK
AlanK

Reputation: 1951

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.)

Upvotes: 2

Related Questions