New algorithm for clipping lines to complex polygons

1 files changed, 26 insertions, 2 deletions

diff --git a/t/polyclip.t b/t/polyclip.t
index 605c4834b..0a66565fe 100644
--- a/t/polyclip.t
+++ b/t/polyclip.t
@@ -1,6 +1,6 @@
 use Test::More;
 
-plan tests => 9;
+plan tests => 10;
 
 BEGIN {
     use FindBin;
@@ -9,7 +9,7 @@ BEGIN {
 
 use Slic3r;
 
-my $square = [
+my $square = [  # ccw
     [10, 10],
     [20, 10],
     [20, 20],
@@ -21,18 +21,42 @@ my $line = [ [5, 15], [30, 15] ];
 my $intersection = Slic3r::Geometry::clip_segment_polygon($line, $square);
 is_deeply $intersection, [ [10, 15], [20, 15] ], 'line is clipped to square';
 
+#==========================================================
+
 $intersection = Slic3r::Geometry::clip_segment_polygon([ [0, 15], [8, 15] ], $square);
 is $intersection, undef, 'external lines are ignored 1';
 
+#==========================================================
+
 $intersection = Slic3r::Geometry::clip_segment_polygon([ [30, 15], [40, 15] ], $square);
 is $intersection, undef, 'external lines are ignored 2';
 
+#==========================================================
+
 $intersection = Slic3r::Geometry::clip_segment_polygon([ [12, 12], [18, 16] ], $square);
 is_deeply $intersection, [ [12, 12], [18, 16] ], 'internal lines are preserved';
 
+#==========================================================
+
+my $hole_in_square = [  # cw
+    [14, 14],
+    [14, 16],
+    [16, 16],
+    [16, 14],
+];
+my $intersections = Slic3r::Geometry::clip_segment_complex_polygon($line, [ $square, $hole_in_square ]);
+is_deeply $intersections, [
+    [ [10, 15], [14, 15] ],
+    [ [16, 15], [20, 15] ],
+], 'line is clipped to square with hole';
+
+#==========================================================
+
 is Slic3r::Geometry::point_in_segment([10, 10], [ [5, 10], [20, 10] ]), 1, 'point in horizontal segment';
 is Slic3r::Geometry::point_in_segment([30, 10], [ [5, 10], [20, 10] ]), 0, 'point not in horizontal segment';
 is Slic3r::Geometry::point_in_segment([10, 10], [ [10, 5], [10, 20] ]), 1, 'point in vertical segment';
 is Slic3r::Geometry::point_in_segment([10, 30], [ [10, 5], [10, 20] ]), 0, 'point not in vertical segment';
 is Slic3r::Geometry::point_in_segment([15, 15], [ [10, 10], [20, 20] ]), 1, 'point in diagonal segment';
 is Slic3r::Geometry::point_in_segment([20, 15], [ [10, 10], [20, 20] ]), 0, 'point not in diagonal segment';
+
+#==========================================================