Finding an axis-aligned rectangle inside a polygon

Question

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 1

Just for reference, so far all I have is brute force: make a grid, and for points on the grid, if they are inside the polygon, make a series of rectangles by expanding each corner or side in turn until it hits a side. Then just pick the largest.

The simplest (and very effective) optimisation is only to test whether a grid point is in the polygon once you have checked that it is not contained in one of the rectangles already constructed, as 'point in rectangle' checking is blazing fast.

For obvious reasons, this is fairly slow and inexact, not to mention inelegant :)

Answer 2

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.

Answer 3

One solution is to split the concave polygon into convex segments then use cobbal's link.

Since you really have two different fundamental problems, have you considered other alternatives to the hit test problem, such as using a BSP tree? You can speed that up further by laying a grid over the poly and constructing a BSP tree for each grid square. Or a kd-tree with at most one edge in each leaf?

Edit: I'll ellaborate on the kd-tree (out of boredom, even if it might be of any use to anyone):

kd-trees have the following properties:

1. They are binary
2. Each non-leaf node splits space along a plane perpendicular to an axis, one side per child. E.g. root splits space into x < x0 and x >= x0
3. Tree levels take turns splitting along different axes, e.g. level 0 (root) splits perpendicular to X, level 1 -> Y, etc.

To use this for the polygon hit detection, construct the tree as follows:

1. Pick a vertex to split along. (Preferrably somewhere close to middle for a balanced tree).
2. Split other vertices into two sets, one for either side of the split. The above vertex doesn't go into either set.
3. Place edges into the sets as well. Any edge that intersects the split line goes into both sets.
4. Construct children recursively from the above groups.

If the split vertex is chosen appropriately, the tree should have depth close to log(N), where N is the number of vertices. Each leaf node will have at most one edge going through it. To do the hit detection:

1. Find the leaf that the point falls into.
2. If there's an edge in the leaf, compare point to it. If not, it should be obvious whether the point is inside or outside (store this information in such leaves when constructing the tree).