Find Minimum Number of Edge-Aligned, Overlapping Rectangles in a Non-Intersecting, Concave Polygon

1
votes

I am looking for an algorithm or alogirthms I can emply to take a non-intersecting, concave polygon and find a minimum set of edge aligned rectangles partitioning the polygon. The rectangles can overlap (preferably minimally).

I was considering using ear-clipping to find the minimum triangles. I could build rectangles from those triangles. I guess each triangle could have a set of rectangles. Then I examine the rectangles and merge with other, collinear-ish rectangles. I don't know if that is a good approach or not.

I imagine the problem sounds a bit subjective, but I still think there is a good approach for solving this problem with known algorithms and a bit of heuristics.

*EDIT: More with heuristics, I can expect axis-aligned rectangles to be, incidentally, a common occurence.

**EDIT: I can also expect zero of the convex angles to be less than 90 degrees.

1
algorithmgeometrypolygoncomputational-geometry
I don't understand the question. Suppose the input was an equilateral triangle - what is the resulting set of rectangles for the partition? – mindvirus
@mdkess One. I guess you could say the triangle is minimally bounded by three minimally bounding, overlapping rectangles. However, I only need one. How do you ear-clip a triangle anyway? Perhaps this is where the heuristics kick in. Comparing this triangle to the others that share sides with this one. I would try to find the best rectangles to fit (can be merged into a single rectangle) while minimally overlapping with the rectangles that don't. – Josh C.
IMHO, you should device an algo for a convex polygon first. Once you have such an algorithm, either you can develop it further to work with concave polygons, or, you can divide a concave polygon into convex polygons and apply the same method. – ElKamina
@ElKamina, There are algorithms that find the minimum bounding box for a convex polygon. en.wikipedia.org/wiki/Minimum_bounding_box_algorithms I don't see how this approach would work without dividing my concave polygon into smaller, convex ones. I'm just guessing here, but I think that might be more difficult than using the edge-aligned rectangles covering each edge created by ear-clipping. More with heuristics, I can expect axis-aligned rectangles to be incidentally a common occurence. – Josh C.
Just a thought - this sounds a bit like a BSP tree. – mindvirus

1 Answers

0
votes

Fair warning, I have no background in computation geometry, so I'm basically just making things up. This would be my initial approach to the problem.

  1. Figure out if the polygon is convex. If so, cover it with one rectangle aligned with an edge. To do this, I'd say just try all of the edges and see which one gives the rectangle with the smallest area. There may be a better way to determine which edge to use, but again, no background in this stuff.

  2. If the polygon is concave, let's call an edge a "concave edge" if it's not on the convex hull of the polygon. Find a concave edge in the polygon, and extend it to cut the polygon into two or more new, smaller polygons. Recurse on each of the child polygons.

If the polygon has few enough edges, I think that an exhaustive search would be reasonable, and just pick the matching which covers your heuristic best (fewest rectangles, least amount of space not within the polygon covered, amount of overlap, some function of the previous factors, etc.)