22

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.

Joel in Gö
  • 7,460
  • 9
  • 47
  • 77
  • Do you consider a "point in polygon" test heavy? Most of the time it's just a "greater than" and/or "less than" test of all ths points that the polygon is made up of, and only in some cases an intersection test of lines? Or...? – Dan Byström Mar 04 '09 at 13:12
  • Not sure what you mean... I am using the even-odd crossing test for a half-line (after checking the bounding rectangle of course). That ends up testing a lot of sides, and if the polygon has many sides it is pretty slow. – Joel in Gö Mar 04 '09 at 13:28
  • Coud you link to some datasets, this sounds like something which could be fun to try. – Jeremy French Mar 04 '09 at 13:30
  • 'fraid not, all I have is the database here. – Joel in Gö Mar 04 '09 at 13:34
  • I'm curious, what's it for? A concave polygon can very well have two or more such rectangles of equal area. – TrayMan Mar 10 '09 at 13:10
  • To speed up 'point in polygon' hit testing. If the polygon has an enclosing rect and an enclosed rect associated to it, we can hit test in many cases very efficiently by first hit testing the rects. The expensive exact testing only needs to be carried out for points which lie between the two rects. – Joel in Gö Mar 10 '09 at 13:39
  • I also need it for a separate task: finding a space to inscribe a piece of steel plate with the part number, where the piece may be any shape, have drill holes etc. – Joel in Gö Mar 10 '09 at 13:43

4 Answers4

8

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.

cobbal
  • 69,903
  • 20
  • 143
  • 156
4

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).
TrayMan
  • 7,180
  • 3
  • 24
  • 33
2

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

Joel in Gö
  • 7,460
  • 9
  • 47
  • 77
  • Just off the top of my head, construct horizontal and vertical lines through each vertex instead of a uniform grid. – Agnel Kurian Mar 04 '09 at 13:19
  • ...assuming that the poly does not have lots of small sides approximating curves. – Joel in Gö Mar 04 '09 at 13:29
  • I used a variation of this to good effect. Essentially I cut the polygon into 16 test points (4 wide and 4 tall based on the dimensions of the bounding rect). With a very limited list of samples, I only had to expand my rectangle by checking to see if the new point produced a rectangle completely inside the geometry. It worked very well for my purposes. – Berin Loritsch Feb 22 '16 at 19:46
0

What about using ear clipping? You could find the maximum axis-aligned rectangle in each triangle. Then you could try to join triangles and recompute your rectangles.

Josh C.
  • 4,303
  • 5
  • 30
  • 51