This PR replaces Tippecanoe's use of Wagyu to clean polygons with a new polygon cleaning implementation in polygon.cpp.
Like Wagyu, it is intended to take whatever mess of self-contradictory polygon geometry it is given and produce a new polygon or multipolygon that meets the OGC standards for "simple" and "valid" polygon geometries.
The steps of cleaning are:
Scaling
Scales the geometry from its source resolution to the output tile resolution, and attempts to correct winding errors introduced during scaling by jittering the coordinates of the central vertex of ears whose winding differs from the winding of the same ear in the source geometry.
Wagyu does not have the opportunity to correct windings here because it starts from pre-scaled geometry.
Decomposition
The scaled rings are decomposed into a set of directed edges. The information about which edges originally came from the same ring is discarded.
Spike and spindle correction
Any pairs of edges that have the same endpoints but opposite orientations are discarded. These may be "spikes" (narrow peninsulas or inlets) from a single ring, "spindles" where narrow polygon rings have collapsed to a line during scaling, or borders where an outer ring and an inner ring meet and should be merged into a single crescent ring.
As a special case, if a spike or spindle is more than 5 pixels long, it is assumed to have visual significance. Rather than being discarded, each of the two edges is split into two and bowed out slightly at the center, so the pair will display as a long, narrow diamond shape rather than being lost. (This unfortunately may introduce new self-intersections or new shard overlaps with adjacent features, or even new spindles or spikes. So any altered edges are reinspected after snap rounding until the set of edges stabilizes.)
Wagyu eliminates matched pairs of edges, but later in the process, and does not have the special case to try to convert them back into viable polygon rings.
Snap rounding
Pairs of edges from the scaled geometry that might intersect are inspected to determine whether they do intersect. If they do (and the intersection is not at one of the endpoints of the edge), the edge is split into two new edges, one from each existing endpoint to the intersection points.
The edges that have been altered are reinspected for spikes and spindles and intersections, and are re-split if necessary until the set of edges stabilizes so that edges intersect only at their endpoints.
Wagyu snap-rounds any two edges that enter the same pixel rather than only those that edges actually intersect, which provides more opportunities for accidentally introducing shard gaps. MapLibre rendering does not appear to actually require this higher level of snap-rounding.
Ring reassembly
From the surviving and modified set of edges, Tippecanoe reconstructs polygon rings. It starts from an arbitrary edge and walks the connections from that point until it finds a point that it has already visited, which may not be the starting point of the walk. When there are multiple paths leading out from a point, it follows the sharpest available left turn, which (in the Y-down tile coordinate space), which should always yield the largest outer ring or the smallest inner ring that can be reached from the starting point. After a ring has been found, it is removed from the set of edges, and more rings are sought until all the edges are consumed.
Wagyu instead builds its rings from the top down, both sides at once, following Vatti's algorithm.
Ring hierarchy determination
At this point, Wagyu does its checks for rings that cross and for spikes that need to be removed, which can cause rings to be split into two or for parts of rings to be reassigned to other rings. Tippecanoe has already removed the spikes, and it should not have been possible for the ring reconstruction to have created any rings that cross.
Both Tippecanoe and Wagyu now inspect the rings to determine which rings are children of which other rings. In the Tippecanoe case, this is done by choosing an interior point for each ring, starting from the largest, in one of the ring's ears, and using pnpoly to determine what other ring, if any, that point appears in, starting from the smallest (and therefore most inner) ring that has already been placed in the hierarchy.
The final stage is to remove any inner rings that somehow exist at the top level of the hierarchy, since there is nothing for them to be cut away from. As required by the vector tile spec, each outer ring is followed by the inner rings that cut away parts of it.
This PR replaces Tippecanoe's use of Wagyu to clean polygons with a new polygon cleaning implementation in
polygon.cpp.Like Wagyu, it is intended to take whatever mess of self-contradictory polygon geometry it is given and produce a new polygon or multipolygon that meets the OGC standards for "simple" and "valid" polygon geometries.
The steps of cleaning are:
Scaling
Scales the geometry from its source resolution to the output tile resolution, and attempts to correct winding errors introduced during scaling by jittering the coordinates of the central vertex of ears whose winding differs from the winding of the same ear in the source geometry.
Wagyu does not have the opportunity to correct windings here because it starts from pre-scaled geometry.
Decomposition
The scaled rings are decomposed into a set of directed edges. The information about which edges originally came from the same ring is discarded.
Spike and spindle correction
Any pairs of edges that have the same endpoints but opposite orientations are discarded. These may be "spikes" (narrow peninsulas or inlets) from a single ring, "spindles" where narrow polygon rings have collapsed to a line during scaling, or borders where an outer ring and an inner ring meet and should be merged into a single crescent ring.
As a special case, if a spike or spindle is more than 5 pixels long, it is assumed to have visual significance. Rather than being discarded, each of the two edges is split into two and bowed out slightly at the center, so the pair will display as a long, narrow diamond shape rather than being lost. (This unfortunately may introduce new self-intersections or new shard overlaps with adjacent features, or even new spindles or spikes. So any altered edges are reinspected after snap rounding until the set of edges stabilizes.)
Wagyu eliminates matched pairs of edges, but later in the process, and does not have the special case to try to convert them back into viable polygon rings.
Snap rounding
Pairs of edges from the scaled geometry that might intersect are inspected to determine whether they do intersect. If they do (and the intersection is not at one of the endpoints of the edge), the edge is split into two new edges, one from each existing endpoint to the intersection points.
The edges that have been altered are reinspected for spikes and spindles and intersections, and are re-split if necessary until the set of edges stabilizes so that edges intersect only at their endpoints.
Wagyu snap-rounds any two edges that enter the same pixel rather than only those that edges actually intersect, which provides more opportunities for accidentally introducing shard gaps. MapLibre rendering does not appear to actually require this higher level of snap-rounding.
Ring reassembly
From the surviving and modified set of edges, Tippecanoe reconstructs polygon rings. It starts from an arbitrary edge and walks the connections from that point until it finds a point that it has already visited, which may not be the starting point of the walk. When there are multiple paths leading out from a point, it follows the sharpest available left turn, which (in the Y-down tile coordinate space), which should always yield the largest outer ring or the smallest inner ring that can be reached from the starting point. After a ring has been found, it is removed from the set of edges, and more rings are sought until all the edges are consumed.
Wagyu instead builds its rings from the top down, both sides at once, following Vatti's algorithm.
Ring hierarchy determination
At this point, Wagyu does its checks for rings that cross and for spikes that need to be removed, which can cause rings to be split into two or for parts of rings to be reassigned to other rings. Tippecanoe has already removed the spikes, and it should not have been possible for the ring reconstruction to have created any rings that cross.
Both Tippecanoe and Wagyu now inspect the rings to determine which rings are children of which other rings. In the Tippecanoe case, this is done by choosing an interior point for each ring, starting from the largest, in one of the ring's ears, and using
pnpolyto determine what other ring, if any, that point appears in, starting from the smallest (and therefore most inner) ring that has already been placed in the hierarchy.The final stage is to remove any inner rings that somehow exist at the top level of the hierarchy, since there is nothing for them to be cut away from. As required by the vector tile spec, each outer ring is followed by the inner rings that cut away parts of it.