5

I'm looking for a method for finding an axis-aligned rectangle inside a concave or convex polygon.

I've been looking around the web, the closest solutions I could find would only fit a convex polygon, and not a concave one. For example -

Finding an axis-aligned rectangle inside a polygon

To be honest I'm not a great math wiz, so I would rather find code samples or a code library, but I guess I could handle some math by myself, or find someone to help me with it.

It would be really nice if the solution could be in Java too, but maybe I'm too greedy :P

Edit: In response to Russell's comment, I'm adding a bit more information.

The bounded rectangle should be as large as possible. The rectangle is intended to contain text inside it. 1 to 4 words max, with support for text wrapping. So if for example it would be too thin, I would place the text vertically instead of horizontally. So for aspect ratio, I guess it needs to be enough for containing 1-4 words either vertically or horizontally with word wrapping. I can resize the text if the rectangle is small, but preferably the text should be as large as possible.

Another requirement that would be nice to have would be that if the general orientation of the polygon is diagonal and the text would fit much better when it's oriented diagonally, then the rectangle wouldn't necessarily be aligned with the axis' but instead be aligned with the diagonal lines of the polygon. I guess this demand is making this really tricky, but if you guys think its possible then it would be great!

I think I've covered all of the requirements now. :P

Thanks!

Community
  • 1
  • 1
Dror
  • 2,548
  • 4
  • 33
  • 51
  • Are there any more constraints on the rectangle? Do you want it to be of maximal area? Of a certain height or width? Or perhaps a certain aspect ratio? Should it contact the edges on at least two corners? For concave polygons, where there may be several distinct possible placements, is there a heuristic for which is better? – Russell Zahniser Apr 18 '12 at 17:56

2 Answers2

1

I once implemented a similar system in a really kludgey way by just making a search through possible rectangles and using Shape.contains() on them. It was somewhat slow - perhaps 1s for layout out the Gettsburg Address in an oval - but useful for static text and for small text in simple shapes.

If you're interested you could unzip the jar file here and look at TextWrappingLayout. It's probably a lot more complicated than what you would need, because instead of laying out in a single rectangle it tries to place each line as close to the edge as it can, but you can see the basic idea.

Russell Zahniser
  • 16,188
  • 39
  • 30
  • Thanks Russell! It really is complex :) I think it would be better of for me to implement it with DeepYellow's method, though this could still be a great reference! Thanks a lot! – Dror Apr 30 '12 at 08:45
1

Since you want to do this for text, I'll assume speed is important, accuracy less important. I suggest this then:

  1. Place the polygon on a grid with cells proportional to text dimensions.
  2. Remove cells on the boundary using Bresenham's line algorithm..
  3. Remove cells outside the boundary cells (by working from the edges of the grid inward.
  4. Find the maximal rectangle on the remaining cells, e.g. the method shown here.

See also Puzzle: Find largest rectangle (maximal rectangle problem).

EDIT: I just noticed the request that this algorithm adjust if the polygon is oriented at an angle. My suggest is to find the principle axes of the polygon to check the orientation, rotate it to align the dominant axis to the x-axis, and apply the algorithm above.

Also, I want to note that "removing a cell" really just means setting a bit in a 2D array that represents the grid cells.

Community
  • 1
  • 1
Codie CodeMonkey
  • 7,669
  • 2
  • 29
  • 45
  • Thanks DeepYellow! Your algorithm seems elegant enough. Unfortunately I won't have the time to implement it at the moment since it's quite complex. But I'm marking this as answer nonetheless. I hope I'll be able to implement it soon. – Dror Apr 30 '12 at 08:42
  • This solution is not sufficient. Think of a concave polygon that almost touches itself - filling from the outside will not fill the cavity. – SudoNhim Nov 02 '15 at 22:01
  • @SudoNhim, I disagree, it works just as well whether concave or convex. Where do you think it goes wrong? – Codie CodeMonkey Nov 02 '15 at 22:30
  • When a polygon almost touches itself, the rasterized version could actually touch itself, preventing step 3 from removing all the cells that lie outside the polygon. This is not an unrealistic scenario, imagine you are trying to label a land mass that has an estuary for example. Here's a failure case for step 3: http://i.imgur.com/o8mZHbF.png – SudoNhim Nov 03 '15 at 16:22
  • The solution of course, is to use a proper rasterizing algorithm. e.g. http://www.cs.mun.ca/av/old/teaching/cg/notes/raster_poly.pdf – SudoNhim Nov 03 '15 at 16:26