As you already noticed, I keep coming back to this problem. Partly because I like to solve these problems, but also because it annoyed me a bit, that I could not find an elegant algorithm for something that seems so easy.
Well, don't be fooled, this is not a trivial problem that you can solve with some simple dot manipulation, although it certainly does. This is partly due to the fact that although you think that you work only with points, you also secretly manipulate line segments and the areas covered by them, which also have their own limitations (i.e., segments should always form one or more closed chains and cannot intersect, except for the vertices that we define them c).
In addition, your algorithm should work on any input that you feed it. That is, it is not allowed to give an answer or an incorrect answer just because the polygon that you fed it is oriented in such a way that your algorithm is not like.
However, you can limit the type of input that your algorithm accepts. Therefore, the requirement that the input polygon contains only axes aligned along the axis is perfectly valid. (The difference between “incorrectly oriented” and “only axis-oriented segments” is that the first is vague criteria that cannot be determined without checking it on the algorithm, while the second may be).
To reproduce, we are looking for a way to horizontally split any rectangular polygon (i.e., consisting only of line segments along the axis) into rectangles.
Rectangular Polygon Example
Here's the plan:
- Choose our building blocks
- Allow Extra Peaks
- Grid Alignment.
- Work with grid cells with uneven size.
- What cells are inside your polygon?
- Building rectangles.
Choose our building blocks
Although these are implementation details, getting this clear background may help you better understand how the algorithm works.
In the code, we will use the following types of objects as the main building blocks to represent our polygon with:
- Point consisting of x and y coordinates. (e.g. use Point2D.Double )
- A segment consisting of a start and end point (e.g. use Line2D.Double )
- A polygon consisting of a closed chain of segments (for example, use an ArrayList from Line2D.Double), where one segment ends at the same point as the starting point for the next segment.
In addition, we will use a grid that can be modeled as a two-dimensional array.
Allow extra vertices.
You stated that "rectangles should be formed using intersecting lines that begin and end on existing coordinates." However, note that most rectilinear polygons cannot be divided into rectangles using existing vertices only - see the Example above (as well as the caravan examples given earlier).
Therefore, this restriction will have to go - although we will not actually create new vertices explicitly.
Grid Alignment.
A thought experiment: what if your polygon existed only from (axis aligned) segments of length 10, 20, 30 or 40 ... i.e. multiples of 10? Then we could project our polygon onto a grid and use the grid cells that lie inside the polygon to compose the rectangles. Also, sizing these rectangles would be a breeze: just count the number of horizontally consecutive cells that lie inside the polygon and multiply by 10; what is your width.
Grid Aligned Polygon
Good idea besides:
- A polygon does not consist of segments of the same or multiple lengths
- How to determine which mesh cells lie inside a polygon?
We will consider each of the following issues.
Work with grid cells with uneven size.
If you think about it, there is no real reason that all grid cells have the same width and height. Therefore, we can create a grid located at a distance, so that our polygon coincides perfectly with it.
To get the width of the horizontal axes of the grid:
- Collect all the x-coordinates of the vertices that make up the polygon.
- Duplicate and sort them by increasing cost.
- The difference between the two subsequent values ​​determines the width of this column.
Polygon matched mesh
Obviously, the cell heights can be determined identically. You must define these widths and heights and store them in two arrays called gridWidths and gridHeights , respectively.
Now that we know the number of cells and their sizes, we can start modeling the contents of the grid.
What cells are inside your polygon?
Remember that our polygon is stored as a chain of line segments. To determine whether a grid cell is inside this polygon, we can use an even rule : construct a line segment outside * the polygon in the center of the cell we want to check, and count the number of intersections between this line segment and the polygon segments (i.e. use Line2D .Double intersectsLine () ). If the number is equal, it lies outside the polygon; if it is odd, it is inside the polygon.
* - It is best to build only horizontal line segments between the centers of the cells (as shown in the example), so that you do not run the risk of crossing the end points of the segment - this can be considered as 0 or 2 intersections, ruining your score.
So, we will model this grid as a grid , a two-dimensional array of Booleans. Treat each grid cell in this way and mark the corresponding spot in the grid as true (inside the polygon) or false (outer polygon).
Inside (T) or outside (F) based on an even-odd rule
Building rectangles.
Now that we have a view of the polygon mesh, as well as the actual widths and heights of each cell, we can start building rectangles. I assume that you are only interested in the width and height of each rectangle, and not in the actual coordinates of the vertices that make up the rectangle (although this is now easy too).
Foreach row in grid run_start = null Foreach cell C in row if C is marked as true and run_start = null //Found the start of a new run run_start = C else if C is marked as false and run_start != null //Found the end of a run The cells [run_start...C] form a horizontal rectangle. Use the gridWidths and gridHeights arrays to determine the dimensions, and report this rectangle as a result //Prepare for the next run run_start = null
A polygon divided into rectangles.
Please note that the two rectangles in the upper left corner have the same start and end x-coordinates and therefore can be considered as one rectangle. If you want, you can implement an extra pass that combines these types of rectangles.
Conclusion
Comparing a rectilinear polygon on a grid, we can easily divide it horizontally in rectangles without resorting to more complex geometric data structures. Please note that there are some optimization possibilities for this algorithm to work faster, but I don’t think it really matters for the current input sizes, and this will make implementation difficult.