1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
package Slic3r::ExPolygon;
use strict;
use warnings;
# an ExPolygon is a polygon with holes
use Boost::Geometry::Utils;
use List::Util qw(first);
use Math::Geometry::Voronoi;
use Slic3r::Geometry qw(X Y A B point_in_polygon same_line epsilon);
use Slic3r::Geometry::Clipper qw(union_ex JT_MITER);
sub contour {
my $self = shift;
return $self->[0];
}
sub holes {
my $self = shift;
return @$self[1..$#$self];
}
sub is_valid {
my $self = shift;
return (!first { !$_->is_valid } @$self)
&& $self->contour->is_counter_clockwise
&& (!first { $_->is_counter_clockwise } $self->holes);
}
# returns false if the expolygon is too tight to be printed
sub is_printable {
my $self = shift;
my ($width) = @_;
# try to get an inwards offset
# for a distance equal to half of the extrusion width;
# if no offset is possible, then expolygon is not printable.
return Slic3r::Geometry::Clipper::offset($self, -$width / 2) ? 1 : 0;
}
sub wkt {
my $self = shift;
return sprintf "POLYGON(%s)",
join ',', map "($_)", map { join ',', map "$_->[0] $_->[1]", @$_ } @$self;
}
sub offset {
my $self = shift;
return Slic3r::Geometry::Clipper::offset($self, @_);
}
sub offset_ex {
my $self = shift;
return Slic3r::Geometry::Clipper::offset_ex($self, @_);
}
sub safety_offset {
my $self = shift;
return Slic3r::Geometry::Clipper::safety_offset_ex($self, @_);
}
sub noncollapsing_offset_ex {
my $self = shift;
my ($distance, @params) = @_;
return $self->offset_ex($distance + 1, @params);
}
sub encloses_point {
my $self = shift;
my ($point) = @_;
return Boost::Geometry::Utils::point_covered_by_polygon($point->arrayref, $self->pp);
}
# A version of encloses_point for use when hole borders do not matter.
# Useful because point_on_segment is probably slower (this was true
# before the switch to Boost.Geometry, not sure about now)
sub encloses_point_quick {
my $self = shift;
my ($point) = @_;
return Boost::Geometry::Utils::point_within_polygon($point->arrayref, $self->arrayref);
}
sub encloses_line {
my $self = shift;
my ($line, $tolerance) = @_;
my $clip = $self->clip_line($line);
if (!defined $tolerance) {
# optimization
return @$clip == 1 && same_line($clip->[0], $line);
} else {
return @$clip == 1 && abs(Boost::Geometry::Utils::linestring_length($clip->[0]) - $line->length) < $tolerance;
}
}
sub bounding_box {
my $self = shift;
return $self->contour->bounding_box;
}
sub clip_line {
my $self = shift;
my ($line) = @_; # line must be a Slic3r::Line object
return Boost::Geometry::Utils::polygon_multi_linestring_intersection($self->pp, [$line->pp]);
}
sub simplify {
my $self = shift;
my ($tolerance) = @_;
# it would be nice to have a multilinestring_simplify method in B::G::U
my @simplified = Slic3r::Geometry::Clipper::simplify_polygons(
[ map Boost::Geometry::Utils::linestring_simplify($_, $tolerance), @{$self->pp} ],
);
return @{ Slic3r::Geometry::Clipper::union_ex([ @simplified ]) };
}
sub area {
my $self = shift;
my $area = $self->contour->area;
$area -= $_->area for $self->holes;
return $area;
}
# this method only works for expolygons having only a contour or
# a contour and a hole, and not being thicker than the supplied
# width. it returns a polyline or a polygon
sub medial_axis {
my $self = shift;
my ($width) = @_;
my @self_lines = map $_->lines, @$self;
my $expolygon = $self->clone;
my @points = ();
foreach my $polygon (@$expolygon) {
Slic3r::Geometry::polyline_remove_short_segments($polygon, $width / 2);
# subdivide polygon segments so that we don't have anyone of them
# being longer than $width / 2
$polygon->subdivide($width/2);
push @points, @$polygon;
}
my $voronoi = Math::Geometry::Voronoi->new(points => \@points);
$voronoi->compute;
my @skeleton_lines = ();
my $vertices = $voronoi->vertices;
my $edges = $voronoi->edges;
foreach my $edge (@$edges) {
# ignore lines going to infinite
next if $edge->[1] == -1 || $edge->[2] == -1;
my ($a, $b);
$a = $vertices->[$edge->[1]];
$b = $vertices->[$edge->[2]];
next if !$self->encloses_point_quick($a) || !$self->encloses_point_quick($b);
push @skeleton_lines, [$edge->[1], $edge->[2]];
}
# remove leafs (lines not connected to other lines at one of their endpoints)
{
my %pointmap = ();
$pointmap{$_}++ for map @$_, @skeleton_lines;
@skeleton_lines = grep {
$pointmap{$_->[A]} >= 2 && $pointmap{$_->[B]} >= 2
} @skeleton_lines;
}
return () if !@skeleton_lines;
# now walk along the medial axis and build continuos polylines or polygons
my @polylines = ();
{
# build a map of line endpoints
my %pointmap = (); # point_idx => [line_idx, line_idx ...]
for my $line_idx (0 .. $#skeleton_lines) {
for my $point_idx (@{$skeleton_lines[$line_idx]}) {
$pointmap{$point_idx} ||= [];
push @{$pointmap{$point_idx}}, $line_idx;
}
}
# build the list of available lines
my %spare_lines = map {$_ => 1} (0 .. $#skeleton_lines);
CYCLE: while (%spare_lines) {
push @polylines, [];
my $polyline = $polylines[-1];
# start from a random line
my $first_line_idx = +(keys %spare_lines)[0];
delete $spare_lines{$first_line_idx};
push @$polyline, @{ $skeleton_lines[$first_line_idx] };
while (1) {
my $last_point_id = $polyline->[-1];
my $lines_starting_here = $pointmap{$last_point_id};
# remove all the visited lines from the array
shift @$lines_starting_here
while @$lines_starting_here && !$spare_lines{$lines_starting_here->[0]};
# do we have a line starting here?
my $next_line_idx = shift @$lines_starting_here;
if (!defined $next_line_idx) {
delete $pointmap{$last_point_id};
next CYCLE;
}
# line is not available anymore
delete $spare_lines{$next_line_idx};
# add the other point to our polyline and continue walking
push @$polyline, grep $_ ne $last_point_id, @{$skeleton_lines[$next_line_idx]};
}
}
}
my @result = ();
foreach my $polyline (@polylines) {
next unless @$polyline >= 2;
# now replace point indexes with coordinates
@$polyline = map $vertices->[$_], @$polyline;
# cleanup
$polyline = Slic3r::Geometry::douglas_peucker($polyline, $width / 7);
if (Slic3r::Geometry::same_point($polyline->[0], $polyline->[-1])) {
next if @$polyline == 2;
push @result, Slic3r::Polygon->new(@$polyline[0..$#$polyline-1]);
} else {
push @result, Slic3r::Polyline->new(@$polyline);
}
}
return @result;
}
package Slic3r::ExPolygon::Collection;
use Slic3r::Geometry qw(X1 Y1);
sub align_to_origin {
my $self = shift;
my @bb = Slic3r::Geometry::bounding_box([ map @$_, map @$_, @$self ]);
$self->translate(-$bb[X1], -$bb[Y1]);
$self;
}
sub size {
my $self = shift;
return [ Slic3r::Geometry::size_2D([ map @$_, map @$_, @$self ]) ];
}
1;
|