aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjaseg <git@jaseg.de>2023-11-14 19:54:54 +0100
committerjaseg <git@jaseg.de>2023-11-14 20:50:52 +0100
commit8e8bcee209be254da1f23787a2b82349f3a23ef9 (patch)
treeafda3d50e15045a817f8f74d5cdbbf7aa4246927
parent1442601f7b02bd023e78a188321999e17deafc3b (diff)
downloadgerbolyze-8e8bcee209be254da1f23787a2b82349f3a23ef9.tar.gz
gerbolyze-8e8bcee209be254da1f23787a2b82349f3a23ef9.tar.bz2
gerbolyze-8e8bcee209be254da1f23787a2b82349f3a23ef9.zip
Fix infinite loop bug in dehole_polytree
Closes #43. Thanks to github users @Altomare for reporting this one, and @fstark for suggesting a fix.
-rw-r--r--svg-flatten/src/svg_geom.cpp39
1 files changed, 31 insertions, 8 deletions
diff --git a/svg-flatten/src/svg_geom.cpp b/svg-flatten/src/svg_geom.cpp
index a36c881..3825775 100644
--- a/svg-flatten/src/svg_geom.cpp
+++ b/svg-flatten/src/svg_geom.cpp
@@ -122,14 +122,37 @@ static void dehole_polytree_worker(PolyNode &ptree, Paths &out, queue<PolyTree>
/* Find a viable cut: Cut from top-left bounding box corner, through two subsequent points on the hole
* outline and to top-right bbox corner. */
IntRect bbox = c.GetBounds();
- Path tri = { { bbox.left, bbox.top }, nod->Childs[0]->Contour[0], nod->Childs[0]->Contour[1], { bbox.right, bbox.top } };
- c.AddPath(tri, ptClip, true);
-
- c.StrictlySimple(true);
- /* Execute twice, once for intersection fragment and once for difference fragment. Note that this will yield
- * at least two, but possibly more polygons. */
- c.Execute(ctDifference, todo.emplace(), pftNonZero);
- c.Execute(ctIntersection, todo.emplace(), pftNonZero);
+
+ /* Clipper might return a polygon with a zero-length, or an exactly vertical outline segment. We iterate
+ * until we find a point that has a different X coordinate than our starting point. If we can't find one
+ * because the polygon only consists only of points on a vertical line, we can safely discard it and do
+ * nothing since it has zero area anyway. */
+ for (size_t i=0; i<nod->Childs[0]->Contour.size(); i++) {
+ if (nod->Childs[0]->Contour[i].X == nod->Childs[0]->Contour[0].X) {
+ continue;
+ }
+
+ /* We now have found that Contour[0] - Contour[i] has a non-zero horizontal component, and is a
+ * candidate for our cut. However, we have to make sure that the first point is left (lower X
+ * coordinate) of the second point, or the cutting polygon we create here would have a
+ * self-intersection, which with high likelihood would lead to a new hole being created when cutting.
+ */
+ int a=0, b=i;
+ if (nod->Childs[0]->Contour[i].X < nod->Childs[0]->Contour[0].X) {
+ /* Swap points */
+ a = i;
+ b = 0;
+ }
+ Path tri = { { bbox.left, bbox.top }, nod->Childs[0]->Contour[a], nod->Childs[0]->Contour[b], { bbox.right, bbox.top } };
+ c.AddPath(tri, ptClip, true);
+
+ /* Execute twice, once for intersection fragment and once for difference fragment. Note that this will yield
+ * at least two, but possibly more polygons. */
+ c.StrictlySimple(true);
+ c.Execute(ctDifference, todo.emplace(), pftNonZero);
+ c.Execute(ctIntersection, todo.emplace(), pftNonZero);
+ break;
+ }
}
}
}