<p>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.</p>

<p><img src="https://i.sstatic.net/5suk2.png" alt="enter image description here"></p>

<p>This post is related to another post: <a href="https://cstheory.stackexchange.com/questions/12376/">Cover a Concave Polygon with a minimum number of rectangles</a></p>

<p>I am hoping to split up the questions so I can attract better answers.</p>

CC BY-SA 3.0
2012-08-29T16:08:04.713Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-29T16:14:32.247Z
@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?
Josh C.
CC BY-SA 3.0
2012-08-29T20:46:40.450Z
(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.)
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-29T22:18:41.367Z
@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?
Josh C.
<co.combinatorics><cg.comp-geom>
Identify all of the non-overlapping rectangular regions of a simple concave polygon
Josh C.
# Identify all of the non-overlapping rectangular regions of a simple concave polygon

(Asked by: username_0 on 2012-08-29)

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.

![enter image description here](https://i.sstatic.net/5suk2.png)

This post is related to another post: [Cover a Concave Polygon with a minimum number of rectangles](https://cstheory.stackexchange.com/questions/12376/)

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

**Tags:** co.combinatorics, cg.comp-geom

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  
> **username_1**: (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.)  
> **username_0**: @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?  

---

## 0 answers

