Finding a Bounded Rectangle Inside a Concave / Convex Polygon

Question

I am looking for a method to find a rectangle aligned in an axis inside a concave or convex polygon.

I look over the net, the closest solutions that I could find would only correspond to convex polygons, not concave ones. For example -

Find a rectangle with alignment along the axis inside the polygon

Honestly, I'm not a big math wiz, so I would rather find some code samples or a code library, but I think I could handle some math myself or find someone who could help me.

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

Change In response to a Russell comment, I am adding a bit more information.

The bounded rectangle should be as large as possible. The rectangle should contain the text inside it. 1 to 4 words with text packaging support. Therefore, if, for example, it were too thin, I would place the text vertically and not horizontally. Therefore, for the aspect ratio, I assume that this is enough to contain 1-4 words vertically or horizontally with the word. I can resize the text if the rectangle is small, but preferably the text should be as large as possible.

Another requirement that it would be nice to have is that if the general orientation of the polygon is diagonal, and the text is much better when it is oriented diagonally, then the rectangle will not necessarily be aligned with the axis', but instead be aligned with diagonal lines of the polygon. I guess this requirement makes it very difficult, but if you guys think it is possible then it would be great!

I think that now I have considered all the requirements .: P

Thanks!

Answer 1

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

• Place the polygon on a grid with cells proportional to the size of the text.
• Remove cells on the border using the Bresenham line algorithm.
• Remove cells outside the border cells (working with the edges of the grid inward.
• Find the maximum rectangle on the remaining cells, for example. method shown here .

See also Puzzle: find the largest rectangle (maximum rectangle problem) .

EDIT: I just noticed a query that this algorithm will adjust if the polygon is oriented at an angle. I suggest finding the main axes

Answer 2

I once applied a similar system to actually kludgey by simply searching through the possible rectangles and using Shape.contains() on them. This was somewhat slow - perhaps 1 second for composing a Gettsburg address in an oval, but useful for static text and for small text in simple forms.

If you're interested, you can unzip the jar file here and look at TextWrappingLayout . This is probably a lot more complicated than what you need, because instead of laying out in one rectangle, it puts each line as close to the edge as possible, but you can see the main idea.