Finding an axis-aligned rectangle inside a polygon

algorithm geometry polygon rectangles
Joel in Gö picture Joel in Gö · Mar 4, 2009 · Viewed 9.3k times · Source

I am looking for a good algorithm to find an axis-aligned rectangle inside a (not necessarily convex) polygon. A maximal rectangle would be nice, but is not necessary - any algorithm that can find a "fairly good" rectangle would be fine.

The polygon may also have holes, but any pointers to algorithms that only work for convex or simple polygons would be helpful too.

In my implementation, intersection testing for sides is fairly cheap, but "point in polygon" tests are expensive, so ideally should be minimised.

Answer

cobbal picture cobbal · Mar 4, 2009

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
Has an algorithm for convex, the references might be worth a look.
not sure if it could be extended to non-convex though.

Related questions

An algorithm for inflating/deflating (offsetting, buffering) polygons

How would I "inflate" a polygon? That is, I want to do something similar to this: The requirement is that the new (inflated) polygon's edges/points are all at the same constant distance from the old (original) polygon's (on the …

Read More
How do I efficiently determine if a polygon is convex, non-convex or complex?

From the man page for XFillPolygon: If shape is Complex, the path may self-intersect. Note that contiguous coincident points in the path are not treated as self-intersection. If shape is Convex, for every pair of points inside the polygon, the …

Read More
Calculate coordinates of a regular polygon's vertices

I am writing a program in which I need to draw polygons of an arbitrary number of sides, each one being translated by a given formula which changes dynamically. There is some rather interesting mathematics involved but I am stuck …

Read More