I want to partition a polygon into non-overlapping polygons with specific areas and no specific dimension. The polygons should be rectangular. You are allowed to add points.
Input Polygon:
Desired Output (please note that all the lines would be straight):
Please ignore the disconnected lines. The input would be number of polygons and area for each of them.
So, I was wondering how to approach this problem?
I am going to assume in the following that all angles on the input polygon are right angles.
At first I was confused by your figures, since the rectangles have different area, and solving that problem is very easy, just modify the ear-cutting algorithm to work with squares instead of triangles (it works because of the right angles). If they just need to have the same area, you would just need to divide each resulting rectangles into smaller rectables with the size of the greatest common divisor for the area of all the rectangles you have found thus far. I am then left with solving the problem for a specific pre-choosen value for the area.
There are a few realizations on the nature of the solution that we can use to solve this problem (assuming a given instance is solveable).
The first realization is that a polygon needs to have its area divisible by the specific area, and any subdivision of the polygon must also satisfy this.
The second realization is that it is trivial to subdivide a rectangle that has an area divisible by the specific area into smaller rectangles of the correct size, simply divide it in the correct number of slices along one of the directions.
The third realization is that we need to reduce the complexity of the polygon until we are left with just rectangles. Specifically there must exist a set of subdivisions, each having some multiple of the correct area and each forming a rectangle.
The forth realization is that (one set of) the subdivisions from the third realization must have its internal borders be extensions of internal concave corners of the polygon we started with. It can be a bit tricky to see why this is so, but if we do not have such an extention, then at one side of such a subdivision we would need to go beyond the line, and the resulting form will not have reduced its complexity, no matter how many times we would continue to subdivide, we would be continously forced to invade another rectangle with some of the area, which means that rectangle will also have increased complexity, and we would therefor never be able to remove the complexity.
In other words, one way to find a suitable division of a polygon into rectangles of a specific area, is to first look for subdivisions of the polygon along the lines extended by concave corners (where the area of each side is a multiple of the specific area) until all the subdivisions turns into rectangles. If this fails then no suitable subdivision exists. If it success, all that is left is to subdivide those rectangles as previously mentioned.
It should be noted that there may exists subdivisions into such rectangles that do not conform to subdivions described in realization 3 and 4, but they still only exists if such a suitable division can be made, since they are effectively just rearrangements of the rectangles such that they cross those subdivisions.
