Finding a bounded rectangle inside a concave/convex polygon

Question

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!

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

Answer 2

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.