Search code examples
c++polygonpartitionmanhattan

Trapezoidal decomposition of polygon in C++

I'm dealing with a polygon "fracture" problem which is to decompose a polygon with (or without) holes into trapezoids.

enter image description here

I've found something similar implemented in Python here: https://deparkes.co.uk/2015/02/05/trapezoidal-decomposition-polygons-python/.

Is there a way to do it in C++?

Given a list of point(x, y) (std::vector), then return a list of trapezoids(points).

Solution

  • I don't know of a library that does this, but here's a rough outline of an algorithm to do this, it's an instance of a scan-line or line-sweep algorithm.

    The idea is that you imagine a line parallel to your slice direction sweeping across your data. As this happens you maintain a set of active edges. Each time your line hits a vertex, you emit appropriate trapezoids and remove edges that have become inactive and introduce any new active edges.

    1. Convert all edges to directed edges (they need to have direction so that you can handle holes correctly)
    2. Sort the edges by increasing minimum x coordinate (you could do it by y either, but assuming that x is increasing from left to right in your diagram this is the correct choice for your case). For edges with the same minimum x coordinate use the y coordinate to order them. For example, in the diagram you showed it looks like they sorted from top to bottom. Whether that is increasing or decreasing y depends on your coordinate system.
    3. Set the scan-line to the first vertex and introduce and edges that touch the scan-line
    4. Advance the scan line to the next vertex. It's usually helpful to keep the value of the previous scan-line available.
    5. Emit any trapezoids. The emitted trapezoids will all be between the previous scan-line and the current one. And the vertices will be where the current or previous scan-line intersects and edge.
    6. Remove any edges that are now to left of your scan-line. (For example, in the diagram, when the scan-line is at vertex 2, you would remove the edge from 0-2)
    7. Merge in any new edges.
    8. While there are edges remaining go to step 4.

    I'm glossing over some awkward details here. You may need to "grid" the output trapezoids depending on your application and you have to be quite careful with the floating point portions of the calculations.

    If you can find code that does polygon rasterization it can often be adapted to do this. In that case you alter the code for calculating the edge intersections at every x or y coordinate to only those at vertices. Another place to look would be for open source EDA packages. This algorithm is needed to prepare chip design data for mask preparation, but since you used the term "fracture" maybe you knew this already ;-)