Incomplete work for XS-based convex_hull

9 files changed, 38 insertions, 28 deletions

diff --git a/Build.PL b/Build.PL
index 5f2340d34..5b07edc2e 100644
--- a/Build.PL
+++ b/Build.PL
@@ -13,7 +13,6 @@ my %prereqs = qw(
     File::Basename                  0
     File::Spec                      0
     Getopt::Long                    0
-    Math::ConvexHull::MonotoneChain 0.01
     Math::Geometry::Voronoi         1.3
     Math::PlanePath                 53
     Moo                             1.003001
diff --git a/lib/Slic3r/GCode/ArcFitting.pm b/lib/Slic3r/GCode/ArcFitting.pm
index 019ebc859..52078bdc0 100644
--- a/lib/Slic3r/GCode/ArcFitting.pm
+++ b/lib/Slic3r/GCode/ArcFitting.pm
@@ -73,7 +73,7 @@ sub flush_path {
         $$buffer =~ s/^/;/mg;
         $gcode = "; these moves were replaced by an arc:\n" . $$buffer;
         
-        my $orientation = Slic3r::Geometry::point_is_on_left_of_segment($cur_path->[2], [ @$cur_path[0,1] ]) ? 'ccw' : 'cw';
+        my $orientation = $cur_path->[2]->ccw(@$cur_path[0,1]) ? 'ccw' : 'cw';
         
         # to find the center, we intersect the perpendicular lines
         # passing by midpoints of $s1 and last segment
diff --git a/lib/Slic3r/GUI/Plater.pm b/lib/Slic3r/GUI/Plater.pm
index eff1ad04e..4985e412b 100644
--- a/lib/Slic3r/GUI/Plater.pm
+++ b/lib/Slic3r/GUI/Plater.pm
@@ -6,8 +6,7 @@ use utf8;
 use File::Basename qw(basename dirname);
 use List::Util qw(max sum first);
 use Slic3r::Geometry::Clipper qw(offset JT_ROUND);
-use Math::ConvexHull::MonotoneChain qw(convex_hull);
-use Slic3r::Geometry qw(X Y Z MIN MAX);
+use Slic3r::Geometry qw(X Y Z MIN MAX convex_hull);
 use threads::shared qw(shared_clone);
 use Wx qw(:bitmap :brush :button :cursor :dialog :filedialog :font :keycode :icon :id :listctrl :misc :panel :pen :sizer :toolbar :window);
 use Wx::Event qw(EVT_BUTTON EVT_COMMAND EVT_KEY_DOWN EVT_LIST_ITEM_ACTIVATED EVT_LIST_ITEM_DESELECTED EVT_LIST_ITEM_SELECTED EVT_MOUSE_EVENTS EVT_PAINT EVT_TOOL EVT_CHOICE);
@@ -991,7 +990,7 @@ sub repaint {
             
             # if sequential printing is enabled and we have more than one object
             if ($parent->{config}->complete_objects && (map @{$_->instances}, @{$parent->{objects}}) > 1) {
-            	my $convex_hull = Slic3r::Polygon->new(@{convex_hull([ map @{$_->contour->pp}, @{$parent->{object_previews}->[-1][2]} ])});
+            	my $convex_hull = convex_hull([ map @{$_->contour}, @{$parent->{object_previews}->[-1][2]} ]);
                 my ($clearance) = @{offset([$convex_hull], $parent->{config}->extruder_clearance_radius / 2 * $parent->{scaling_factor}, 100, JT_ROUND)};
                 $dc->SetPen($parent->{clearance_pen});
                 $dc->SetBrush($parent->{transparent_brush});
@@ -1255,7 +1254,6 @@ package Slic3r::GUI::Plater::Object;
 use Moo;
 
 use List::Util qw(first);
-use Math::ConvexHull::MonotoneChain qw();
 use Slic3r::Geometry qw(X Y Z MIN MAX deg2rad);
 
 has 'name'                  => (is => 'rw', required => 1);
@@ -1291,7 +1289,7 @@ sub _trigger_model_object {
 	    
     	my $mesh = $model_object->mesh;
     	$mesh->repair;
-        $self->convex_hull(Slic3r::Polygon->new(@{Math::ConvexHull::MonotoneChain::convex_hull($mesh->vertices)}));
+        $self->convex_hull(Slic3r::Geometry::convex_hull($mesh->vertices));
 	    $self->facets($mesh->facets_count);
 	    $self->vertices(scalar @{$mesh->vertices});
 	    $self->materials($model_object->materials_count);
diff --git a/lib/Slic3r/Geometry.pm b/lib/Slic3r/Geometry.pm
index 99a396743..f3cb24f32 100644
--- a/lib/Slic3r/Geometry.pm
+++ b/lib/Slic3r/Geometry.pm
@@ -9,7 +9,7 @@ our @EXPORT_OK = qw(
     line_point_belongs_to_segment points_coincide distance_between_points 
     chained_path_items chained_path_points normalize tan move_points_3D
     point_in_polygon point_in_segment segment_in_segment
-    point_is_on_left_of_segment polyline_lines polygon_lines
+    polyline_lines polygon_lines
     point_along_segment polygon_segment_having_point polygon_has_subsegment
     deg2rad rad2deg
     rotate_points move_points
@@ -20,6 +20,7 @@ our @EXPORT_OK = qw(
     rad2deg_dir bounding_box_center line_intersects_any douglas_peucker
     polyline_remove_short_segments normal triangle_normal polygon_is_convex
     scaled_epsilon bounding_box_3D size_3D size_2D
+    convex_hull
 );
 
 
@@ -174,13 +175,6 @@ sub segment_in_segment {
     return point_in_segment($needle->[A], $haystack) && point_in_segment($needle->[B], $haystack);
 }
 
-sub point_is_on_left_of_segment {
-    my ($point, $line) = @_;
-    
-    return (($line->[B][X] - $line->[A][X])*($point->[Y] - $line->[A][Y]) 
-        - ($line->[B][Y] - $line->[A][Y])*($point->[X] - $line->[A][X])) > 0;
-}
-
 sub polyline_lines {
     my ($polyline) = @_;
     my @points = @$polyline;
diff --git a/lib/Slic3r/Line.pm b/lib/Slic3r/Line.pm
index 4c77259e5..034770c71 100644
--- a/lib/Slic3r/Line.pm
+++ b/lib/Slic3r/Line.pm
@@ -23,12 +23,6 @@ sub intersection {
     return Slic3r::Geometry::line_intersection($self, $line, $require_crossing);
 }
 
-sub point_on_left {
-    my $self = shift;
-    my ($point) = @_;
-    return Slic3r::Geometry::point_is_on_left_of_segment($point, $self);
-}
-
 sub grow {
     my $self = shift;
     return Slic3r::Polyline->new(@$self)->grow(@_);
diff --git a/lib/Slic3r/Print.pm b/lib/Slic3r/Print.pm
index b13b2a7a0..aa865ad6c 100644
--- a/lib/Slic3r/Print.pm
+++ b/lib/Slic3r/Print.pm
@@ -4,9 +4,9 @@ use Moo;
 use File::Basename qw(basename fileparse);
 use File::Spec;
 use List::Util qw(min max first);
-use Math::ConvexHull::MonotoneChain qw(convex_hull);
 use Slic3r::ExtrusionPath ':roles';
-use Slic3r::Geometry qw(X Y Z X1 Y1 X2 Y2 MIN MAX PI scale unscale move_points chained_path);
+use Slic3r::Geometry qw(X Y Z X1 Y1 X2 Y2 MIN MAX PI scale unscale move_points chained_path
+    convex_hull);
 use Slic3r::Geometry::Clipper qw(diff_ex union_ex union_pt intersection_ex intersection offset
     offset2 traverse_pt JT_ROUND JT_SQUARE);
 use Time::HiRes qw(gettimeofday tv_interval);
@@ -174,8 +174,9 @@ sub validate {
             for my $obj_idx (0 .. $#{$self->objects}) {
                 my $clearance;
                 {
-                    my @points = map [ @$_[X,Y] ], map @{$_->vertices}, @{$self->objects->[$obj_idx]->meshes};
-                    my $convex_hull = Slic3r::Polygon->new(@{convex_hull(\@points)});
+                    my @points = map Slic3r::Point->new(@$_[X,Y]), map @{$_->vertices}, @{$self->objects->[$obj_idx]->meshes};
+                    my $convex_hull = convex_hull(\@points);
+                    use XXX; YYY ($convex_hull->pp);
                     ($clearance) = @{offset([$convex_hull], scale $Slic3r::Config->extruder_clearance_radius / 2, 1, JT_ROUND)};
                 }
                 for my $copy (@{$self->objects->[$obj_idx]->copies}) {
diff --git a/t/multi.t b/t/multi.t
index 4524891c7..0071363d9 100644
--- a/t/multi.t
+++ b/t/multi.t
@@ -8,9 +8,8 @@ BEGIN {
 }
 
 use List::Util qw(first);
-use Math::ConvexHull::MonotoneChain qw(convex_hull);
 use Slic3r;
-use Slic3r::Geometry qw(scale);
+use Slic3r::Geometry qw(scale convex_hull);
 use Slic3r::Test;
 
 {
@@ -54,7 +53,7 @@ use Slic3r::Test;
             $point->translate(map scale($_), @{ $config->extruder_offset->[$tool] });
         }
     });
-    my $convex_hull = Slic3r::Polygon->new(@{convex_hull([ map $_->pp, @extrusion_points ])});
+    my $convex_hull = convex_hull(\@extrusion_points);
     ok !(first { $convex_hull->contains_point($_) } @toolchange_points), 'all toolchanges happen outside skirt';
 }
 
diff --git a/xs/src/Point.cpp b/xs/src/Point.cpp
index 0c85a309c..6644cdb33 100644
--- a/xs/src/Point.cpp
+++ b/xs/src/Point.cpp
@@ -90,6 +90,28 @@ Point::distance_to(const Line &line) const
     return std::abs(n) / line.length();
 }
 
+/* Three points are a counter-clockwise turn if ccw > 0, clockwise if
+ * ccw < 0, and collinear if ccw = 0 because ccw is a determinant that
+ * gives the signed area of the triangle formed by p1, p2 and this point.
+ */
+double
+Point::ccw(const Point &p1, const Point &p2) const
+{
+    return (p2.x - p1.x)*(this->y - p1.y) - (p2.y - p1.y)*(this->x - p1.x);
+}
+
+double
+Point::ccw(const Point* p1, const Point* p2) const
+{
+    return this->ccw(*p1, *p2);
+}
+
+double
+Point::ccw(const Line &line) const
+{
+    return this->ccw(line.a, line.b);
+}
+
 #ifdef SLIC3RXS
 SV*
 Point::to_SV_ref() {
diff --git a/xs/src/Point.hpp b/xs/src/Point.hpp
index 981b6f214..175c96c3b 100644
--- a/xs/src/Point.hpp
+++ b/xs/src/Point.hpp
@@ -26,6 +26,9 @@ class Point
     double distance_to(const Point* point) const;
     double distance_to(const Line* line) const;
     double distance_to(const Line &line) const;
+    double ccw(const Point &p1, const Point &p2) const;
+    double ccw(const Point* p1, const Point* p2) const;
+    double ccw(const Line &line) const;
     
     #ifdef SLIC3RXS
     void from_SV(SV* point_sv);