# Identify all of the non-overlapping rectangular regions of a simple concave polygon

I am looking for an algorithm to identify all of the rectangles bounded by two parallel edges of a polygon. The rectangle must remain inside of the polygon at all times. My polygon is simple and will never have an acute angle. I have looked for algorithms already, but they seem to only work for convex or orthogonal polygons. Is there a good approach to this. At this point, I am thinking I should group all edges by parallelity and inspect those sets to find rectangular regions. It sounds bad.

This post is related to another post: Cover a Concave Polygon with a minimum number of rectangles

I am hoping to split up the questions so I can attract better answers.

• A possible formulation of your question may be the following, although in my formulation, the resulting rectangles may overlap with each other (so the title of the question suggests that this is not the right formulation of the question you have in mind). For the purpose of this comment, a rectangle R is said to be aligned with an edge E when one of the edges of R intersects with E for a nonzero length. Problem: Given a simple polygon P which does not have an acute angle, find all maximal rectangles that are contained in P and are aligned with two parallel edges of P. Aug 29, 2012 at 16:08
• @TsuyoshiIto is that different from collinearity? I would like to achieve results with no overlapping rectangles. However, results with overlapping rectangles may have a purpose too. Is there a known algorithm for your formulation? Aug 29, 2012 at 16:14
• (1) “is that different from collinearity?” I do not know what you mean by “that.” (2) I do not have any interesting algorithm for the problem which I stated in my previous comment in mind. (3) If your question were clear from the beginning, I would not have posted something which I know is different from the question you have in mind. Please edit your question to make its meaning clear. (But to do so, you should first understand that your question is unclear.) Aug 29, 2012 at 20:46
• @TsuyoshiIto I think I see what you mean, and I do see how your formulation allows for overlapping rectangles. Could we bound the rectangles at the vertices of the two edges? I believe this would prevent overlap. Does that clarify the question? Aug 29, 2012 at 22:18