1//////////////////////////////////////////////////////////////////////
2// LibFile: regions.scad
3// This file provides 2D Boolean set operations on polygons, where you can
4// compute, for example, the intersection or union of the shape defined by point lists, producing
5// a new point list. Of course, such operations may produce shapes with multiple
6// components. To handle that, we use "regions" which are lists of paths representing the polygons.
7// In addition to set operations, you can calculate offsets, determine whether a point is in a
8// region and you can decompose a region into parts.
9// Includes:
10// include <BOSL2/std.scad>
11// FileGroup: Advanced Modeling
12// FileSummary: Offsets and Boolean geometry of 2D paths and regions.
13// FileFootnotes: STD=Included in std.scad
14//////////////////////////////////////////////////////////////////////
15
16
17// CommonCode:
18// include <BOSL2/rounding.scad>
19
20
21// Section: Regions
22// A region is a list of polygons meeting these conditions:
23// .
24// - Every polygon on the list is simple, meaning it does not intersect itself
25// - Two polygons on the list do not cross each other
26// - A vertex of one polygon never meets the edge of another one except at a vertex
27// .
28// Note that this means vertex-vertex touching between two polygons is acceptable
29// to define a region. Note, however, that regions with vertex-vertex contact usually
30// cannot be rendered with CGAL. See {{is_valid_region()}} for examples of valid regions and
31// lists of polygons that are not regions. Note that {{is_region_simple()}} will identify
32// regions with no polygon intersections at all, which should render successfully witih CGAL.
33// .
34// The actual geometry of the region is defined by XORing together
35// all of the polygons in the list. This may sound obscure, but it simply means that nested
36// boundaries make rings in the obvious fashion, and non-nested shapes simply union together.
37// Checking that a list of polygons is a valid region, meaning that it satisfies all of the conditions
38// above, can be a time consuming test, so it is not done automatically. It is your responsibility to ensure that your regions are
39// compliant. You can construct regions by making a suitable list of polygons, or by using
40// set operation function such as union() or difference(), which all acccept polygons, as
41// well as regions, as their inputs. And if you must you can clean up an ill-formed region using make_region(),
42// which will break up self-intersecting polygons and polygons that cross each other.
43
44
45// Function: is_region()
46// Synopsis: Returns true if the input appears to be a region.
47// Topics: Regions, Paths, Polygons, List Handling
48// See Also: is_valid_region(), is_1region(), is_region_simple()
49// Usage:
50// bool = is_region(x);
51// Description:
52// Returns true if the given item looks like a region. A region is a list of non-crossing simple polygons. This test just checks
53// that the argument is a list whose first entry is a path.
54function is_region(x) = is_list(x) && is_path(x.x);
55
56
57// Function: is_valid_region()
58// Synopsis: Returns true if the input is a valid region.
59// Topics: Regions, Paths, Polygons, List Handling
60// See Also: is_region(), is_1region(), is_region_simple()
61// Usage:
62// bool = is_valid_region(region, [eps]);
63// Description:
64// Returns true if the input is a valid region, meaning that it is a list of simple polygons whose segments do not cross each other.
65// This test can be time consuming with regions that contain many points.
66// It differs from `is_region()` which simply checks that the object is a list whose first entry is a path
67// because it searches all the list polygons for any self-intersections or intersections with each other.
68// Will also return true if given a single simple polygon. Use {{make_region()}} to convert sets of self-intersecting polygons into
69// a region.
70// Arguments:
71// region = region to check
72// eps = tolerance for geometric comparisons. Default: `EPSILON` = 1e-9
73// Example(2D,NoAxes): In all of the examples each polygon in the region appears in a different color. Two non-intersecting squares make a valid region.
74// region = [square(10), right(11,square(8))];
75// rainbow(region)stroke($item, width=.2,closed=true);
76// back(11)text(is_valid_region(region) ? "region" : "non-region", size=2);
77// Example(2D,NoAxes): Nested squares form a region
78// region = [for(i=[3:2:10]) square(i,center=true)];
79// rainbow(region)stroke($item, width=.2,closed=true);
80// back(6)text(is_valid_region(region) ? "region" : "non-region", size=2,halign="center");
81// Example(2D,NoAxes): Also a region:
82// region= [square(10,center=true), square(5,center=true), right(10,square(7))];
83// rainbow(region)stroke($item, width=.2,closed=true);
84// back(8)text(is_valid_region(region) ? "region" : "non-region", size=2);
85// Example(2D,NoAxes): The squares cross each other, so not a region
86// object = [square(10), move([8,8], square(8))];
87// rainbow(object)stroke($item, width=.2,closed=true);
88// back(17)text(is_valid_region(object) ? "region" : "non-region", size=2);
89// Example(2D,NoAxes): A union is one way to fix the above example and get a region. (Note that union is run here on two simple polygons, which are valid regions themselves and hence acceptable inputs to union.
90// region = union([square(10), move([8,8], square(8))]);
91// rainbow(region)stroke($item, width=.25,closed=true);
92// back(12)text(is_valid_region(region) ? "region" : "non-region", size=2);
93// Example(2D,NoAxes): Not a region due to a self-intersecting (non-simple) hourglass polygon
94// object = [move([-2,-2],square(14)), [[0,0],[10,0],[0,10],[10,10]]];
95// rainbow(object)stroke($item, width=.2,closed=true);
96// move([-1.5,13])text(is_valid_region(object) ? "region" : "non-region", size=2);
97// Example(2D,NoAxes): Breaking hourglass in half fixes it. Now it's a region:
98// region = [move([-2,-2],square(14)), [[0,0],[10,0],[5,5]], [[5,5],[0,10],[10,10]]];
99// rainbow(region)stroke($item, width=.2,closed=true);
100// Example(2D,NoAxes): A single polygon corner touches an edge, so not a region:
101// object = [[[-10,0], [-10,10], [20,10], [20,-20], [-10,-20],
102// [-10,-10], [0,0], [10,-10], [10,0]]];
103// rainbow(object)stroke($item, width=.3,closed=true);
104// move([-4,12])text(is_valid_region(object) ? "region" : "non-region", size=3);
105// Example(2D,NoAxes): Corners touch in the same polygon, so the polygon is not simple and the object is not a region.
106// object = [[[0,0],[10,0],[10,10],[-10,10],[-10,0],[0,0],[-5,5],[5,5]]];
107// rainbow(object)stroke($item, width=.3,closed=true);
108// move([-10,12])text(is_valid_region(object) ? "region" : "non-region", size=3);
109// Example(2D,NoAxes): The shape above as a valid region with two polygons:
110// region = [ [[0,0],[10,0],[10,10],[-10,10],[-10,0]],
111// [[0,0],[5,5],[-5,5]] ];
112// rainbow(region)stroke($item, width=.3,closed=true);
113// move([-5.5,12])text(is_valid_region(region) ? "region" : "non-region", size=3);
114// Example(2D,NoAxes): As with the "broken" hourglass, Touching at corners is OK. This is a region.
115// region = [square(10), move([10,10], square(8))];
116// rainbow(region)stroke($item, width=.25,closed=true);
117// back(12)text(is_valid_region(region) ? "region" : "non-region", size=2);
118// Example(2D,NoAxes): These two squares share part of an edge, hence not a region
119// object = [square(10), move([10,2], square(7))];
120// stroke(object[0], width=0.2,closed=true);
121// color("red")dashed_stroke(object[1], width=0.25,closed=true);
122// back(12)text(is_valid_region(object) ? "region" : "non-region", size=2);
123// Example(2D,NoAxes): These two squares share a full edge, hence not a region
124// object = [square(10), right(10, square(10))];
125// stroke(object[0], width=0.2,closed=true);
126// color("red")dashed_stroke(object[1], width=0.25,closed=true);
127// back(12)text(is_valid_region(object) ? "region" : "non-region", size=2);
128// Example(2D,NoAxes): Sharing on edge on the inside, also not a regionn
129// object = [square(10), [[0,0], [2,2],[2,8],[0,10]]];
130// stroke(object[0], width=0.2,closed=true);
131// color("red")dashed_stroke(object[1], width=0.25,closed=true);
132// back(12)text(is_valid_region(object) ? "region" : "non-region", size=2);
133// Example(2D,NoAxes): Crossing at vertices is also bad
134// object = [square(10), [[10,0],[0,10],[8,13],[13,8]]];
135// rainbow(object)stroke($item, width=.2,closed=true);
136// back(14)text(is_valid_region(object) ? "region" : "non-region", size=2);
137// Example(2D,NoAxes): One polygon touches another in the middle of an edge
138// object = [square(10), [[10,5],[15,0],[15,10]]];
139// rainbow(object)stroke($item, width=.2,closed=true);
140// back(11)text(is_valid_region(object) ? "region" : "non-region", size=2);
141// Example(2D,NoAxes): The polygon touches the side, but the side has a vertex at the contact point so this is a region
142// poly1 = [ each square(30,center=true), [15,0]];
143// poly2 = right(10,circle(5,$fn=4));
144// poly3 = left(0,circle(5,$fn=4));
145// poly4 = move([0,-8],square([10,3]));
146// region = [poly1,poly2,poly3,poly4];
147// rainbow(region)stroke($item, width=.25,closed=true);
148// move([-5,16.5])text(is_valid_region(region) ? "region" : "non-region", size=3);
149// color("black")move_copies(region[0]) circle(r=.4);
150// Example(2D,NoAxes): The polygon touches the side, but not at a vertex so this is not a region
151// poly1 = fwd(4,[ each square(30,center=true), [15,0]]);
152// poly2 = right(10,circle(5,$fn=4));
153// poly3 = left(0,circle(5,$fn=4));
154// poly4 = move([0,-8],square([10,3]));
155// object = [poly1,poly2,poly3,poly4];
156// rainbow(object)stroke($item, width=.25,closed=true);
157// move([-9,12.5])text(is_valid_region(object) ? "region" : "non-region", size=3);
158// color("black")move_copies(object[0]) circle(r=.4);
159// Example(2D,NoAxes): The inner polygon touches the middle of the edges, so not a region
160// poly1 = square(20,center=true);
161// poly2 = circle(10,$fn=8);
162// object=[poly1,poly2];
163// rainbow(object)stroke($item, width=.25,closed=true);
164// move([-10,11.4])text(is_valid_region(object) ? "region" : "non-region", size=3);
165// Example(2D,NoAxes): The above shape made into a region using {{difference()}} now has four components that touch at corners
166// poly1 = square(20,center=true);
167// poly2 = circle(10,$fn=8);
168// region = difference(poly1,poly2);
169// rainbow(region)stroke($item, width=.25,closed=true);
170// move([-5,11.4])text(is_valid_region(region) ? "region" : "non-region", size=3);
171function is_valid_region(region, eps=EPSILON) =
172 let(region=force_region(region))
173 assert(is_region(region), "Input is not a region")
174 // no short paths
175 [for(p=region) if (len(p)<3) 1] == []
176 &&
177 // all paths are simple
178 [for(p=region) if (!is_path_simple(p,closed=true,eps=eps)) 1] == []
179 &&
180 // paths do not cross each other
181 [for(i=[0:1:len(region)-2])
182 if (_polygon_crosses_region(list_tail(region,i+1),region[i], eps=eps)) 1] == []
183 &&
184 // one path doesn't touch another in the middle of an edge
185 [for(i=idx(region), j=idx(region))
186 if (i!=j) for(v=region[i], edge=pair(region[j],wrap=true))
187 let(
188 v1 = edge[1]-edge[0],
189 v0 = v - edge[0],
190 t = v0*v1/(v1*v1)
191 )
192 if (abs(cross(v0,v1))<eps*norm(v1) && t>eps && t<1-eps) 1
193 ]==[];
194
195
196
197// internal function:
198// returns true if the polygon crosses the region so that part of the
199// polygon is inside the region and part is outside.
200function _polygon_crosses_region(region, poly, eps=EPSILON) =
201 let(
202 subpaths = flatten(split_region_at_region_crossings(region,[poly],eps=eps)[1])
203 )
204 [for(path=subpaths)
205 let(isect=
206 [for (subpath = subpaths)
207 let(
208 midpt = mean([subpath[0], subpath[1]]),
209 rel = point_in_region(midpt,region,eps=eps)
210 )
211 rel
212 ])
213 if (!all_equal(isect) || isect[0]==0) 1 ] != [];
214
215
216// Function: is_region_simple()
217// Synopsis: Returns true if the input is a region with no corner contact.
218// Topics: Regions, Paths, Polygons, List Handling
219// See Also: is_region(), is_valid_region(), is_1region()
220// Usage:
221// bool = is_region_simple(region, [eps]);
222// Description:
223// We extend the notion of the simple path to regions: a simple region is entirely
224// non-self-intersecting, meaning that it is formed from a list of simple polygons that
225// don't intersect each other at all—not even with corner contact points.
226// Regions with corner contact are valid but may fail CGAL. Simple regions
227// should not create problems with CGAL.
228// Arguments:
229// region = region to check
230// eps = tolerance for geometric comparisons. Default: `EPSILON` = 1e-9
231// Example(2D,NoAxes): Corner contact means it's not simple
232// region = [move([-2,-2],square(14)), [[0,0],[10,0],[5,5]], [[5,5],[0,10],[10,10]]];
233// rainbow(region)stroke($item, width=.2,closed=true);
234// move([-1,13])text(is_region_simple(region) ? "simple" : "not-simple", size=2);
235// Example(2D,NoAxes): Moving apart the triangles makes it simple:
236// region = [move([-2,-2],square(14)), [[0,0],[10,0],[5,4.5]], [[5,5.5],[0,10],[10,10]]];
237// rainbow(region)stroke($item, width=.2,closed=true);
238// move([1,13])text(is_region_simple(region) ? "simple" : "not-simple", size=2);
239function is_region_simple(region, eps=EPSILON) =
240 let(region=force_region(region))
241 assert(is_region(region), "Input is not a region")
242 [for(p=region) if (!is_path_simple(p,closed=true,eps=eps)) 1] == []
243 &&
244 [for(i=[0:1:len(region)-2])
245 if (_region_region_intersections([region[i]], list_tail(region,i+1), eps=eps)[0][0] != []) 1
246 ] ==[];
247
248
249// Function: make_region()
250// Synopsis: Converts lists of intersecting polygons into valid regions.
251// SynTags: Region
252// Topics: Regions, Paths, Polygons, List Handling
253// See Also: force_region(), region()
254//
255// Usage:
256// region = make_region(polys, [nonzero], [eps]);
257// Description:
258// Takes a list of polygons that may intersect themselves or cross each other
259// and converts it into a properly defined region without these defects.
260// Arguments:
261// polys = list of polygons to use
262// nonzero = set to true to use nonzero rule for polygon membership. Default: false
263// eps = Epsilon for geometric comparisons. Default: `EPSILON` (1e-9)
264// Example(2D,NoAxes): The pentagram is self-intersecting, so it is not a region. Here it becomes five triangles:
265// pentagram = turtle(["move",100,"left",144], repeat=4);
266// region = make_region(pentagram);
267// rainbow(region)stroke($item, width=1,closed=true);
268// Example(2D,NoAxes): Alternatively with the nonzero option you can get the perimeter:
269// pentagram = turtle(["move",100,"left",144], repeat=4);
270// region = make_region(pentagram,nonzero=true);
271// rainbow(region)stroke($item, width=1,closed=true);
272// Example(2D,NoAxes): Two crossing squares become two L-shaped components
273// region = make_region([square(10), move([5,5],square(8))]);
274// rainbow(region)stroke($item, width=.3,closed=true);
275
276function make_region(polys,nonzero=false,eps=EPSILON) =
277 let(polys=force_region(polys))
278 assert(is_region(polys), "Input is not a region")
279 exclusive_or(
280 [for(poly=polys) each polygon_parts(poly,nonzero,eps)],
281 eps=eps);
282
283// Function: force_region()
284// Synopsis: Given a polygon returns a region.
285// SynTags: Region
286// Topics: Regions, Paths, Polygons, List Handling
287// See Also: make_region(), region()
288// Usage:
289// region = force_region(poly)
290// Description:
291// If the input is a polygon then return it as a region. Otherwise return it unaltered.
292// Arguments:
293// poly = polygon to turn into a region
294function force_region(poly) = is_path(poly) ? [poly] : poly;
295
296
297// Section: Turning a region into geometry
298
299// Module: region()
300// Synopsis: Creates the 2D polygons described by the given region or list of polygons.
301// SynTags: Geom
302// Topics: Regions, Paths, Polygons, List Handling
303// See Also: make_region(), debug_region()
304// Usage:
305// region(r, [anchor], [spin=], [cp=], [atype=]) [ATTACHMENTS];
306// Description:
307// Creates the 2D polygons described by the given region or list of polygons. This module works on
308// arbitrary lists of polygons that cross each other and hence do not define a valid region. The
309// displayed result is the exclusive-or of the polygons listed in the input.
310// Arguments:
311// r = region to create as geometry
312// anchor = Translate so anchor point is at origin (0,0,0). See [anchor](attachments.scad#subsection-anchor). Default: `"origin"`
313// ---
314// spin = Rotate this many degrees after anchor. See [spin](attachments.scad#subsection-spin). Default: `0`
315// cp = Centerpoint for determining intersection anchors or centering the shape. Determintes the base of the anchor vector. Can be "centroid", "mean", "box" or a 2D point. Default: "centroid"
316// atype = Set to "hull" or "intersect" to select anchor type. Default: "hull"
317// Named Anchors:
318// "origin" = The native position of the region.
319// Anchor Types:
320// "hull" = Anchors to the virtual convex hull of the region.
321// "intersect" = Anchors to the outer edge of the region.
322// Example(2D): Displaying a region
323// region([circle(d=50), square(25,center=true)]);
324// Example(2D): Displaying a list of polygons that intersect each other, which is not a region
325// rgn = concat(
326// [for (d=[50:-10:10]) circle(d=d-5)],
327// [square([60,10], center=true)]
328// );
329// region(rgn);
330module region(r, anchor="origin", spin=0, cp="centroid", atype="hull")
331{
332 assert(in_list(atype, _ANCHOR_TYPES), "Anchor type must be \"hull\" or \"intersect\"");
333 r = force_region(r);
334 dummy=assert(is_region(r), "Input is not a region");
335 points = flatten(r);
336 lengths = [for(path=r) len(path)];
337 starts = [0,each cumsum(lengths)];
338 paths = [for(i=idx(r)) count(s=starts[i], n=lengths[i])];
339 attachable(anchor, spin, two_d=true, region=r, extent=atype=="hull", cp=cp){
340 polygon(points=points, paths=paths);
341 children();
342 }
343}
344
345
346
347// Module: debug_region()
348// Synopsis: Draws an annotated region.
349// SynTags: Geom
350// Topics: Shapes (2D)
351// See Also: region(), debug_polygon(), debug_vnf(), debug_bezier()
352//
353// Usage:
354// debug_region(region, [vertices=], [edges=], [convexity=], [size=]);
355// Description:
356// A replacement for {{region()}} that displays the region and labels the vertices and
357// edges. The region vertices and edges are labeled with letters to identify the path
358// component in the region, starting with A.
359// The start of each path is marked with a blue circle and the end with a pink diamond.
360// You can suppress the display of vertex or edge labeling using the `vertices` and `edges` arguments.
361// Arguments:
362// region = region to display
363// ---
364// vertices = if true display vertex labels and start/end markers. Default: true
365// edges = if true display edge labels. Default: true
366// convexity = The max number of walls a ray can pass through the given polygon paths.
367// size = The base size of the line and labels.
368// Example(2D,Big):
369// region = make_region([square(15), move([5,5],square(15))]);
370// debug_region(region,size=1);
371module debug_region(region, vertices=true, edges=true, convexity=2, size=1)
372{
373
374 if (is_path(region) || (is_region(region) && len(region)==1))
375 debug_polygon(force_path(region), vertices=vertices, edges=edges, convexity=convexity, size=size);
376 else {
377 for(i=idx(region))
378 echo(str("points_",chr(97+i)," = ",region[i]))
379 linear_extrude(height=0.01, convexity=convexity, center=true)
380 region(region);
381 if(vertices)
382 _debug_poly_verts(region,size);
383 for(j=idx(region)){
384 if(edges)
385 _debug_poly_edges(j,region[j],vertices=vertices,size=size);
386 }
387 }
388}
389
390
391
392// Section: Geometrical calculations with regions
393
394// Function: point_in_region()
395// Synopsis: Tests if a point is inside, outside, or on the border of a region.
396// Topics: Regions, Points, Comparison
397// See Also: region_area(), are_regions_equal()
398// Usage:
399// check = point_in_region(point, region, [eps]);
400// Description:
401// Tests if a point is inside, outside, or on the border of a region.
402// Returns -1 if the point is outside the region.
403// Returns 0 if the point is on the boundary.
404// Returns 1 if the point lies inside the region.
405// Arguments:
406// point = The point to test.
407// region = The region to test against, as a list of polygon paths.
408// eps = Acceptable variance. Default: `EPSILON` (1e-9)
409// Example(2D,Med): Red points are in the region.
410// region = [for(i=[2:4:10]) hexagon(r=i)];
411// color("#ff7") region(region);
412// for(x=[-10:10], y=[-10:10])
413// if (point_in_region([x,y], region)>=0)
414// move([x,y]) color("red") circle(0.15, $fn=12);
415// else
416// move([x,y]) color("#ddf") circle(0.1, $fn=12);
417function point_in_region(point, region, eps=EPSILON) =
418 let(region=force_region(region))
419 assert(is_region(region), "Region given to point_in_region is not a region")
420 assert(is_vector(point,2), "Point must be a 2D point in point_in_region")
421 _point_in_region(point, region, eps);
422
423function _point_in_region(point, region, eps=EPSILON, i=0, cnt=0) =
424 i >= len(region) ? ((cnt%2==1)? 1 : -1)
425 : let(
426 pip = point_in_polygon(point, region[i], eps=eps)
427 )
428 pip == 0 ? 0
429 : _point_in_region(point, region, eps=eps, i=i+1, cnt = cnt + (pip>0? 1 : 0));
430
431
432// Function: region_area()
433// Synopsis: Computes the area of the specified valid region.
434// Topics: Regions, Area
435// Usage:
436// area = region_area(region);
437// Description:
438// Computes the area of the specified valid region. (If the region is invalid and has self intersections
439// the result is meaningless.)
440// Arguments:
441// region = region whose area to compute
442// Examples:
443// area = region_area([square(10), right(20,square(8))]); // Returns 164
444function region_area(region) =
445 assert(is_region(region), "Input must be a region")
446 let(
447 parts = region_parts(region)
448 )
449 -sum([for(R=parts, poly=R) polygon_area(poly,signed=true)]);
450
451
452
453function _clockwise_region(r) = [for(p=r) clockwise_polygon(p)];
454
455// Function: are_regions_equal()
456// Synopsis: Returns true if given regions are the same polygons.
457// Topics: Regions, Polygons, Comparison
458// Usage:
459// b = are_regions_equal(region1, region2, [either_winding])
460// Description:
461// Returns true if the components of region1 and region2 are the same polygons (in any order).
462// Arguments:
463// region1 = first region
464// region2 = second region
465// either_winding = if true then two shapes test equal if they wind in opposite directions. Default: false
466function are_regions_equal(region1, region2, either_winding=false) =
467 let(
468 region1=force_region(region1),
469 region2=force_region(region2)
470 )
471 assert(is_region(region1) && is_region(region2), "One of the inputs is not a region")
472 len(region1) != len(region2)? false :
473 __are_regions_equal(either_winding?_clockwise_region(region1):region1,
474 either_winding?_clockwise_region(region2):region2,
475 0);
476
477function __are_regions_equal(region1, region2, i) =
478 i >= len(region1)? true :
479 !_is_polygon_in_list(region1[i], region2)? false :
480 __are_regions_equal(region1, region2, i+1);
481
482
483/// Internal Function: _region_region_intersections()
484/// Usage:
485/// risect = _region_region_intersections(region1, region2, [closed1], [closed2], [eps]
486/// Description:
487/// Returns a pair of sorted lists such that risect[0] is a list of intersection
488/// points for every path in region1, and similarly risect[1] is a list of intersection
489/// points for the paths in region2. For each path the intersection list is
490/// a sorted list of the form [PATHIND, SEGMENT, U]. You can specify that the paths in either
491/// region be regarded as open paths if desired. Default is to treat them as
492/// regions and hence the paths as closed polygons.
493/// .
494/// Included as intersection points are points where region1 touches itself at a vertex or
495/// region2 touches itself at a vertex. (The paths are assumed to have no self crossings.
496/// Self crossings of the paths in the regions are not returned.)
497function _region_region_intersections(region1, region2, closed1=true,closed2=true, eps=EPSILON) =
498 let(
499 intersections = [
500 for(p1=idx(region1))
501 let(
502 path = closed1?list_wrap(region1[p1]):region1[p1]
503 )
504 for(i = [0:1:len(path)-2])
505 let(
506 a1 = path[i],
507 a2 = path[i+1],
508 nrm = norm(a1-a2)
509 )
510 if( nrm>eps ) // ignore zero-length path edges
511 let(
512 seg_normal = [-(a2-a1).y, (a2-a1).x]/nrm,
513 ref = a1*seg_normal
514 )
515 // `signs[j]` is the sign of the signed distance from
516 // poly vertex j to the line [a1,a2] where near zero
517 // distances are snapped to zero; poly edges
518 // with equal signs at its vertices cannot intersect
519 // the path edge [a1,a2] or they are collinear and
520 // further tests can be discarded.
521 for(p2=idx(region2))
522 let(
523 poly = closed2?list_wrap(region2[p2]):region2[p2],
524 signs = [for(v=poly*seg_normal) abs(v-ref) < eps ? 0 : sign(v-ref) ]
525 )
526 if(max(signs)>=0 && min(signs)<=0) // some edge intersects line [a1,a2]
527 for(j=[0:1:len(poly)-2])
528 if(signs[j]!=signs[j+1])
529 let( // exclude non-crossing and collinear segments
530 b1 = poly[j],
531 b2 = poly[j+1],
532 isect = _general_line_intersection([a1,a2],[b1,b2],eps=eps)
533 )
534 if (isect
535 && isect[1]>= -eps
536 && isect[1]<= 1+eps
537 && isect[2]>= -eps
538 && isect[2]<= 1+eps)
539 [[p1,i,isect[1]], [p2,j,isect[2]]]
540 ],
541 regions=[region1,region2],
542 // Create a flattened index list corresponding to the points in region1 and region2
543 // that gives each point as an intersection point
544 ptind = [for(i=[0:1])
545 [for(p=idx(regions[i]))
546 for(j=idx(regions[i][p])) [p,j,0]]],
547 points = [for(i=[0:1]) flatten(regions[i])],
548 // Corner points are those points where the region touches itself, hence duplicate
549 // points in the region's point set
550 cornerpts = [for(i=[0:1])
551 [for(k=vector_search(points[i],eps,points[i]))
552 each if (len(k)>1) select(ptind[i],k)]],
553 risect = [for(i=[0:1]) concat(column(intersections,i), cornerpts[i])],
554 counts = [count(len(region1)), count(len(region2))],
555 pathind = [for(i=[0:1]) search(counts[i], risect[i], 0)]
556 )
557 [for(i=[0:1]) [for(j=counts[i]) _sort_vectors(select(risect[i],pathind[i][j]))]];
558
559
560// Section: Breaking up regions into subregions
561
562
563// Function: split_region_at_region_crossings()
564// Synopsis: Splits regions where polygons touch and at intersections.
565// Topics: Regions, Polygons, List Handling
566// See Also: region_parts()
567//
568// Usage:
569// split_region = split_region_at_region_crossings(region1, region2, [closed1], [closed2], [eps])
570// Description:
571// Splits region1 at the places where polygons in region1 touches each other at corners and at locations
572// where region1 intersections region2. Split region2 similarly with respect to region1.
573// The return is a pair of results of the form [split1, split2] where split1=[frags1,frags2,...]
574// and frags1 is a list of paths that when placed end to end (in the given order), give the first polygon of region1.
575// Each path in the list is either entirely inside or entirely outside region2.
576// Then frags2 is the decomposition of the second polygon into path pieces, and so on. Finally split2 is
577// the same list, but for the polygons in region2.
578// You can pass a single polygon in for either region, but the output will be a singleton list, as if
579// you passed in a singleton region. If you set the closed parameters to false then the region components
580// will be treated as open paths instead of polygons.
581// Arguments:
582// region1 = first region
583// region2 = second region
584// closed1 = if false then treat region1 as list of open paths. Default: true
585// closed2 = if false then treat region2 as list of open paths. Default: true
586// eps = Acceptable variance. Default: `EPSILON` (1e-9)
587// Example(2D):
588// path = square(50,center=false);
589// region = [circle(d=80), circle(d=40)];
590// paths = split_region_at_region_crossings(path, region);
591// color("#aaa") region(region);
592// rainbow(paths[0][0]) stroke($item, width=2);
593// right(110){
594// color("#aaa") region([path]);
595// rainbow(flatten(paths[1])) stroke($item, width=2);
596// }
597function split_region_at_region_crossings(region1, region2, closed1=true, closed2=true, eps=EPSILON) =
598 let(
599 region1=force_region(region1),
600 region2=force_region(region2)
601 )
602 assert(is_region(region1) && is_region(region2),"One of the inputs is not a region")
603 let(
604 xings = _region_region_intersections(region1, region2, closed1, closed2, eps),
605 regions = [region1,region2],
606 closed = [closed1,closed2]
607 )
608 [for(i=[0:1])
609 [for(p=idx(xings[i]))
610 let(
611 crossings = deduplicate([
612 [p,0,0],
613 each xings[i][p],
614 [p,len(regions[i][p])-(closed[i]?1:2), 1],
615 ],eps=eps),
616 subpaths = [
617 for (frag = pair(crossings))
618 deduplicate(
619 _path_select(regions[i][p], frag[0][1], frag[0][2], frag[1][1], frag[1][2], closed=closed[i]),
620 eps=eps
621 )
622 ]
623 )
624 [for(s=subpaths) if (len(s)>1) s]
625 ]
626 ];
627
628
629
630// Function: region_parts()
631// Synopsis: Splits a region into a list of connected regions.
632// SynTags: RegList
633// Topics: Regions, List Handling
634// See Also: split_region_at_region_crossings()
635// Usage:
636// rgns = region_parts(region);
637// Description:
638// Divides a region into a list of connected regions. Each connected region has exactly one clockwise outside boundary
639// and zero or more counter-clockwise outlines defining internal holes. Note that behavior is undefined on invalid regions whose
640// components cross each other.
641// Example(2D,NoAxes):
642// R = [for(i=[1:7]) square(i,center=true)];
643// region_list = region_parts(R);
644// rainbow(region_list) region($item);
645// Example(2D,NoAxes):
646// R = [back(7,square(3,center=true)),
647// square([20,10],center=true),
648// left(5,square(8,center=true)),
649// for(i=[4:2:8])
650// right(5,square(i,center=true))];
651// region_list = region_parts(R);
652// rainbow(region_list) region($item);
653function region_parts(region) =
654 let(
655 region = force_region(region)
656 )
657 assert(is_region(region), "Input is not a region")
658 let(
659 inside = [for(i=idx(region))
660 let(pt = mean([region[i][0], region[i][1]]))
661 [for(j=idx(region)) i==j ? 0
662 : point_in_polygon(pt,region[j]) >=0 ? 1 : 0]
663 ],
664 level = inside*repeat(1,len(region))
665 )
666 [ for(i=idx(region))
667 if(level[i]%2==0)
668 let(
669 possible_children = search([level[i]+1],level,0)[0],
670 keep=search([1], select(inside,possible_children), 0, i)[0]
671 )
672 [
673 clockwise_polygon(region[i]),
674 for(good=keep)
675 ccw_polygon(region[possible_children[good]])
676 ]
677 ];
678
679
680
681
682// Section: Offset and 2D Boolean Set Operations
683
684
685function _offset_chamfer(center, points, delta) =
686 is_undef(points[1])?
687 let( points = select(points,[0,2]),
688 center = mean(points),
689 dir = sign(delta)*line_normal(points),
690 halfside = tan(22.5)*abs(delta)
691 )
692 [ points[0]+dir*halfside,
693 center + dir*abs(delta) + unit(points[0]-center)*halfside,
694 center + dir*abs(delta) + unit(points[1]-center)*halfside,
695 points[1]+dir*halfside
696 ]
697 :
698 let(
699 dist = sign(delta)*norm(center-line_intersection(select(points,[0,2]), [center, points[1]])),
700 endline = _shift_segment(select(points,[0,2]), delta-dist)
701 ) [
702 line_intersection(endline, select(points,[0,1])),
703 line_intersection(endline, select(points,[1,2]))
704 ];
705
706
707function _shift_segment(segment, d) =
708 assert(!approx(segment[0],segment[1]),"Path has repeated points")
709 move(d*line_normal(segment),segment);
710
711
712// Extend to segments to their intersection point. First check if the segments already have a point in common,
713// which can happen if two colinear segments are input to the path variant of `offset()`
714function _segment_extension(s1,s2) =
715 norm(s1[1]-s2[0])<1e-6 ? s1[1] : line_intersection(s1,s2,LINE,LINE);
716
717
718function _makefaces(direction, startind, good, pointcount, closed) =
719 let(
720 lenlist = list_bset(good, pointcount),
721 numfirst = len(lenlist),
722 numsecond = sum(lenlist),
723 prelim_faces = _makefaces_recurse(startind, startind+len(lenlist), numfirst, numsecond, lenlist, closed)
724 )
725 direction? [for(entry=prelim_faces) reverse(entry)] : prelim_faces;
726
727
728function _makefaces_recurse(startind1, startind2, numfirst, numsecond, lenlist, closed, firstind=0, secondind=0, faces=[]) =
729 // We are done if *both* firstind and secondind reach their max value, which is the last point if !closed or one past
730 // the last point if closed (wrapping around). If you don't check both you can leave a triangular gap in the output.
731 ((firstind == numfirst - (closed?0:1)) && (secondind == numsecond - (closed?0:1)))? faces :
732 _makefaces_recurse(
733 startind1, startind2, numfirst, numsecond, lenlist, closed, firstind+1, secondind+lenlist[firstind],
734 lenlist[firstind]==0? (
735 // point in original path has been deleted in offset path, so it has no match. We therefore
736 // make a triangular face using the current point from the offset (second) path
737 // (The current point in the second path can be equal to numsecond if firstind is the last point)
738 concat(faces,[[secondind%numsecond+startind2, firstind+startind1, (firstind+1)%numfirst+startind1]])
739 // in this case a point or points exist in the offset path corresponding to the original path
740 ) : (
741 concat(faces,
742 // First generate triangular faces for all of the extra points (if there are any---loop may be empty)
743 [for(i=[0:1:lenlist[firstind]-2]) [firstind+startind1, secondind+i+1+startind2, secondind+i+startind2]],
744 // Finish (unconditionally) with a quadrilateral face
745 [
746 [
747 firstind+startind1,
748 (firstind+1)%numfirst+startind1,
749 (secondind+lenlist[firstind])%numsecond+startind2,
750 (secondind+lenlist[firstind]-1)%numsecond+startind2
751 ]
752 ]
753 )
754 )
755 );
756
757
758// Determine which of the shifted segments are good
759function _good_segments(path, d, shiftsegs, closed, quality) =
760 let(
761 maxind = len(path)-(closed ? 1 : 2),
762 pathseg = [for(i=[0:maxind]) select(path,i+1)-path[i]],
763 pathseg_len = [for(seg=pathseg) norm(seg)],
764 pathseg_unit = [for(i=[0:maxind]) pathseg[i]/pathseg_len[i]],
765 // Order matters because as soon as a valid point is found, the test stops
766 // This order works better for circular paths because they succeed in the center
767 alpha = concat([for(i=[1:1:quality]) i/(quality+1)],[0,1])
768 ) [
769 for (i=[0:len(shiftsegs)-1])
770 (i>maxind)? true :
771 _segment_good(path,pathseg_unit,pathseg_len, d - 1e-7, shiftsegs[i], alpha)
772 ];
773
774
775// Determine if a segment is good (approximately)
776// Input is the path, the path segments normalized to unit length, the length of each path segment
777// the distance threshold, the segment to test, and the locations on the segment to test (normalized to [0,1])
778// The last parameter, index, gives the current alpha index.
779//
780// A segment is good if any part of it is farther than distance d from the path. The test is expensive, so
781// we want to quit as soon as we find a point with distance > d, hence the recursive code structure.
782//
783// This test is approximate because it only samples the points listed in alpha. Listing more points
784// will make the test more accurate, but slower.
785function _segment_good(path,pathseg_unit,pathseg_len, d, seg,alpha ,index=0) =
786 index == len(alpha) ? false :
787 _point_dist(path,pathseg_unit,pathseg_len, alpha[index]*seg[0]+(1-alpha[index])*seg[1]) > d ? true :
788 _segment_good(path,pathseg_unit,pathseg_len,d,seg,alpha,index+1);
789
790
791// Input is the path, the path segments normalized to unit length, the length of each path segment
792// and a test point. Computes the (minimum) distance from the path to the point, taking into
793// account that the minimal distance may be anywhere along a path segment, not just at the ends.
794function _point_dist(path,pathseg_unit,pathseg_len,pt) =
795 min([
796 for(i=[0:len(pathseg_unit)-1]) let(
797 v = pt-path[i],
798 projection = v*pathseg_unit[i],
799 segdist = projection < 0? norm(pt-path[i]) :
800 projection > pathseg_len[i]? norm(pt-select(path,i+1)) :
801 norm(v-projection*pathseg_unit[i])
802 ) segdist
803 ]);
804
805
806// Function: offset()
807// Synopsis: Takes a 2D path, polygon or region and returns a path offset by an amount.
808// SynTags: Path, Region, Ext
809// Topics: Paths, Polygons, Regions
810// Usage:
811// offsetpath = offset(path, [r=|delta=], [chamfer=], [closed=], [check_valid=], [quality=], [same_length=])
812// path_faces = offset(path, return_faces=true, [r=|delta=], [chamfer=], [closed=], [check_valid=], [quality=], [firstface_index=], [flip_faces=])
813// Description:
814// Takes a 2D input path, polygon or region and returns a path offset by the specified amount. As with the built-in
815// offset() module, you can use `r` to specify rounded offset and `delta` to specify offset with
816// corners. If you used `delta` you can set `chamfer` to true to get chamfers.
817// For paths and polygons positive offsets make the polygons larger. For paths,
818// positive offsets shift the path to the left, relative to the direction of the path.
819// .
820// If you use `delta` without chamfers, the path must not include any 180 degree turns, where the path
821// reverses direction. Such reversals result in an offset with two parallel segments, so they cannot be
822// extended to an intersection point. If you select chamfering the reversals are permitted and will result
823// in a single segment connecting the parallel segments. With rounding, a semi-circle will connect the two offset segments.
824// Note also that repeated points are always illegal in the input; remove them first with {{deduplicate()}}.
825// .
826// When offsets shrink the path, segments cross and become invalid. By default `offset()` checks
827// for this situation. To test validity the code checks that segments have distance larger than (r
828// or delta) from the input path. This check takes O(N^2) time and may mistakenly eliminate
829// segments you wanted included in various situations, so you can disable it if you wish by setting
830// check_valid=false. When segments are mistakenly removed, you may get the wrong offset output, or you may
831// get an error, depending on the effect of removing the segment.
832// The erroneous removal of segments is more common when your input
833// contains very small segments and in this case can result in an invalid situation where the remaining
834// valid segments are parallel and cannot be connected to form an offset curve. If this happens, you
835// will get an error message to this effect. The only solutions are to either remove the small segments with {{deduplicate()}},
836// or if your path permits it, to set check_valid to false.
837// .
838// Another situation that can arise with validity testing is that the test is not sufficiently thorough and some
839// segments persist that should be eliminated. In this case, increase `quality` from its default of 1 to a value of 2 or 3.
840// This increases the number of samples on the segment that are checked, so it will increase run time. In
841// some situations you may be able to decrease run time by setting quality to 0, which causes only
842// segment ends to be checked.
843// .
844// When invalid segments are eliminated, the path length decreases, and multiple points on the input path map to the same point
845// on the offset path. If you use chamfering or rounding, then
846// the chamfers and roundings can increase the length of the output path. Hence points in the output may be
847// difficult to associate with the input. If you want to maintain alignment between the points you
848// can use the `same_length` option. This option requires that you use `delta=` with `chamfer=false` to ensure
849// that no points are added. with `same_length`, when points collapse to a single point in the offset, the output includes
850// that point repeated to preserve the correct length. Generally repeated points will not appear in the offset output
851// unless you set `same_length` to true, but in some rare circumstances involving very short segments, it is possible for the
852// repeated points to occur in the output, even when `same_length=false`.
853// .
854// Another way to obtain alignment information is to use the return_faces option, which can
855// provide alignment information for all offset parameters: it returns a face list which lists faces between
856// the original path and the offset path where the vertices are ordered with the original path
857// first, starting at `firstface_index` and the offset path vertices appearing afterwords. The
858// direction of the faces can be flipped using `flip_faces`. When you request faces the return
859// value is a list: [offset_path, face_list].
860// Arguments:
861// path = the path to process. A list of 2d points.
862// ---
863// r = offset radius. Distance to offset. Will round over corners.
864// delta = offset distance. Distance to offset with pointed corners.
865// chamfer = chamfer corners when you specify `delta`. Default: false
866// closed = if true path is treate as a polygon. Default: False.
867// check_valid = perform segment validity check. Default: True.
868// quality = validity check quality parameter, a small integer. Default: 1.
869// same_length = return a path with the same length as the input. Only compatible with `delta=`. Default: false
870// return_faces = return face list. Default: False.
871// firstface_index = starting index for face list. Default: 0.
872// flip_faces = flip face direction. Default: false
873// Example(2D,NoAxes): Offset the red star out by 10 units.
874// star = star(5, r=100, ir=30);
875// stroke(closed=true, star, width=3, color="red");
876// stroke(closed=true, width=3, offset(star, delta=10, closed=true));
877// Example(2D,NoAxes): Offset the star with chamfering
878// star = star(5, r=100, ir=30);
879// stroke(closed=true, star, width=3, color="red");
880// stroke(closed=true, width=3,
881// offset(star, delta=10, chamfer=true, closed=true));
882// Example(2D,NoAxes): Offset the star with rounding
883// star = star(5, r=100, ir=30);
884// stroke(closed=true, star, width=3, color="red");
885// stroke(closed=true, width=3,
886// offset(star, r=10, closed=true));
887// Example(2D,NoAxes): Offset inward
888// star = star(7, r=120, ir=50);
889// stroke(closed=true, width=3, star, color="red");
890// stroke(closed=true, width=3,
891// offset(star, delta=-15, closed=true));
892// Example(2D,NoAxes): Inward offset with chamfers
893// star = star(7, r=120, ir=50);
894// stroke(closed=true, width=3, star, color="red");
895// stroke(closed=true, width=3,
896// offset(star, delta=-15, chamfer=true, closed=true));
897// Example(2D,NoAxes): Inward offset with rounding
898// star = star(7, r=120, ir=50);
899// stroke(closed=true, width=3, star, color="red");
900// stroke(closed=true, width=3,
901// offset(star, r=-15, closed=true, $fn=20));
902// Example(2D): Open path. The red path moves from left to right as shown by the arrow and the positive offset shifts to the left of the initial red path.
903// sinpath = 2*[for(theta=[-180:5:180]) [theta/4,45*sin(theta)]];
904// stroke(sinpath, width=2, color="red", endcap2="arrow2");
905// stroke(offset(sinpath, r=17.5),width=2);
906// Example(2D,NoAxes): An open path in red with with its positive offset in yellow and its negative offset in blue.
907// seg = [[0,0],[0,50]];
908// stroke(seg,color="red",endcap2="arrow2");
909// stroke(offset(seg,r=15,closed=false));
910// stroke(offset(seg,r=-15,closed=false),color="blue");
911// Example(2D,NoAxes): Offsetting the same line segment closed=true. On the left, we use delta with chamfer=false, in the middle, chamfer=true, and on the right, rounding with r=. A "closed" path here means that the path backtracks over itself. When this happens, a flat end occurs in the first case, an end with chamfered corners if chamfering is on, or a semicircular rounding in the rounded case.
912// seg = [[0,0],[0,50]];
913// stroke(seg,color="red");
914// stroke([offset(seg,delta=15,closed=true)]);
915// right(45){
916// stroke(seg,color="red");
917// stroke([offset(seg,delta=15,chamfer=true,closed=true)]);
918// }
919// right(90){
920// stroke(seg,color="red");
921// stroke([offset(seg,r=15,closed=true)]);
922// }
923// Example(2D,NoAxes): Cutting a notch out of a square with a path reversal
924// path = [[-10,-10],[-10,10],[0,10],[0,0],[0,10],[10,10],[10,-10]];
925// stroke([path],width=.25,color="red");
926// stroke([offset(path, r=-2,$fn=32,closed=true)],width=.25);
927// Example(2D,NoAxes): A more complex example where the path turns back on itself several times.
928// $fn=32;
929// path = [
930// [0,0], [5,5],
931// [10,0],[5,5],
932// [11,8],[5,5],
933// [5,10],[5,5],
934// [-1,4],[5,5]
935// ];
936// op=offset(path, r=1.5,closed=true);
937// stroke([path],width=.1,color="red");
938// stroke([op],width=.1);
939// Example(2D,NoAxes): With the default quality value, this case produces the wrong answer. This happens because the offset edge corresponding to the long left edge (shown in green) is erroneously flagged as invalid. If you use `r=` instead of `delta=` then this will fail with an error.
940// test = [[0,0],[10,0],[10,7],[0,7], [-1,-3]];
941// polygon(offset(test,delta=-1.9, closed=true));
942// stroke([test],width=.1,color="red");
943// stroke(select(test,-2,-1), width=.1, color="green");
944// Example(2D,NoAxes): Using `quality=2` produces the correct result
945// test = [[0,0],[10,0],[10,7],[0,7], [-1,-3]];
946// polygon(offset(test,r=-1.9, closed=true, quality=2));
947// stroke([test],width=.1,color="red");
948// Example(2D,NoAxes): This case fails if `check_valid=true` when delta is large enough because segments are too close to the opposite side of the curve so they all get flagged as invalid and deleted from the output.
949// star = star(5, r=22, ir=13);
950// stroke(star,width=.3,closed=true);
951// color("green")
952// stroke(offset(star, delta=-9, closed=true),width=.3,closed=true); // Works with check_valid=true (the default)
953// color("red")
954// stroke(offset(star, delta=-10, closed=true, check_valid=false), // Fails if check_valid=true
955// width=.3,closed=true);
956// Example(2D): But if you use rounding with offset then you need `check_valid=true` when `r` is big enough. It works without the validity check as long as the offset shape retains a some of the straight edges at the star tip, but once the shape shrinks smaller than that, it fails. There is no simple way to get a correct result for the case with `r=10`, because as in the previous example, it will fail if you turn on validity checks.
957// star = star(5, r=22, ir=13);
958// color("green")
959// stroke(offset(star, r=-8, closed=true,check_valid=false), width=.1, closed=true);
960// color("red")
961// stroke(offset(star, r=-10, closed=true,check_valid=false), width=.1, closed=true);
962// Example(2D,NoAxes): The extra triangles in this example show that the validity check cannot be skipped
963// ellipse = scale([20,4], p=circle(r=1,$fn=64));
964// stroke(ellipse, closed=true, width=0.3);
965// stroke(offset(ellipse, r=-3, check_valid=false, closed=true),
966// width=0.3, closed=true);
967// Example(2D,NoAxes): The triangles are removed by the validity check
968// ellipse = scale([20,4], p=circle(r=1,$fn=64));
969// stroke(ellipse, closed=true, width=0.3);
970// stroke(offset(ellipse, r=-3, check_valid=true, closed=true),
971// width=0.3, closed=true);
972// Example(2D,NoAxes): The region shown in red has the yellow offset region.
973// rgn = difference(circle(d=100),
974// union(square([20,40], center=true),
975// square([40,20], center=true)));
976// stroke(rgn, width=1, color="red");
977// region(offset(rgn, r=-5));
978// Example(2D,NoAxes): Using `same_length=true` to align the original curve to the offset. Note that lots of points map to the corner at the top.
979// closed=false;
980// path = [for(angle=[0:5:180]) 10*[angle/100,2*sin(angle)]];
981// opath = offset(path, delta=-3,same_length=true,closed=closed);
982// stroke(path,closed=closed,width=.3);
983// stroke(opath,closed=closed,width=.3);
984// color("red") for(i=idx(path)) stroke([path[i],opath[i]],width=.3);
985
986function offset(
987 path, r=undef, delta=undef, chamfer=false,
988 closed=false, check_valid=true,
989 quality=1, return_faces=false, firstface_index=0,
990 flip_faces=false, same_length=false
991) =
992 assert(!(same_length && return_faces), "Cannot combine return_faces with same_length")
993 is_region(path)?
994 assert(!return_faces, "return_faces not supported for regions.")
995 let(
996 ofsregs = [for(R=region_parts(path))
997 difference([for(i=idx(R)) offset(R[i], r=u_mul(i>0?-1:1,r), delta=u_mul(i>0?-1:1,delta),
998 chamfer=chamfer, check_valid=check_valid, quality=quality,same_length=same_length,closed=true)])]
999 )
1000 union(ofsregs)
1001 :
1002 let(rcount = num_defined([r,delta]))
1003 assert(rcount==1,"Must define exactly one of 'delta' and 'r'")
1004 assert(!same_length || (is_def(delta) && !chamfer), "Must specify delta, with chamfer=false, when same_length=true")
1005 assert(is_path(path), "Input must be a path or region")
1006 let(
1007 chamfer = is_def(r) ? false : chamfer,
1008 quality = max(0,round(quality)),
1009 flip_dir = closed && !is_polygon_clockwise(path)? -1 : 1,
1010 d = flip_dir * (is_def(r) ? r : delta)
1011 )
1012 d==0 && !return_faces ? path :
1013 let(
1014 shiftsegs = [for(i=[0:len(path)-2]) _shift_segment([path[i],path[i+1]], d),
1015 if (closed) _shift_segment([last(path),path[0]],d)
1016 else [path[0],path[1]] // dummy segment, not used
1017 ],
1018 // good segments are ones where no point on the segment is less than distance d from any point on the path
1019 good = check_valid ? _good_segments(path, abs(d), shiftsegs, closed, quality)
1020 : repeat(true,len(shiftsegs)),
1021 goodsegs = bselect(shiftsegs, good),
1022 goodpath = bselect(path,good)
1023 )
1024 assert(len(goodsegs)-(!closed && select(good,-1)?1:0)>0,"Offset of path is degenerate")
1025 let(
1026 // Extend the shifted segments to their intersection points. For open curves the endpoints
1027 // are simply the endpoints of the shifted segments. If segments are parallel then the intersection
1028 // points will be undef
1029 sharpcorners = [for(i=[0:len(goodsegs)-1])
1030 !closed && i==0 ? goodsegs[0][0]
1031 : !closed && i==len(goodsegs)-1 ? goodsegs[len(goodsegs)-2][1]
1032 : _segment_extension(select(goodsegs,i-1), select(goodsegs,i))],
1033
1034 // true if sharpcorner has two parallel segments that go in the same direction
1035 cornercheck = [for(i=idx(goodsegs)) (!closed && (i==0 || i==len(goodsegs)-1))
1036 || is_def(sharpcorners[i])
1037 || approx(unit(deltas(select(goodsegs,i-1))[0]) * unit(deltas(goodsegs[i])[0]),-1)],
1038 dummyA = assert(len(sharpcorners)==2 || all(cornercheck),"Two consecutive valid offset segments are parallel but do not meet at their ends, maybe because path contains very short segments that were mistakenly flagged as invalid; unable to compute offset"),
1039 reversecheck =
1040 !same_length
1041 || !(is_def(delta) && !chamfer) // Reversals only a problem in delta mode without chamfers
1042 || all_defined(sharpcorners),
1043 dummyB = assert(reversecheck, "Either validity check failed and removed a valid segment or the input 'path' contains a segment that reverses direction (180 deg turn). Path reversals are not allowed when same_length is true because they increase path length."),
1044 // This is a Boolean array that indicates whether a corner is an outside or inside corner
1045 // For outside corners, the new corner is an extension (angle 0), for inside corners, it turns backward (angle 180)
1046 // If either side turns back it is an inside corner---must check both.
1047 // Outside corners can get rounded (if r is specified and there is space to round them)
1048 // We flag endpoints of open paths as inside corners so that we don't try to round
1049 outsidecorner =
1050 len(sharpcorners)==2 ? [closed,closed]
1051 : [for(i=idx(goodsegs))
1052 !closed && (i==0 || i==len(goodsegs)-1) ? false // endpoints of open path never get rounded
1053 : is_undef(sharpcorners[i]) ? true
1054 : let(prevseg=select(goodsegs,i-1))
1055 (goodsegs[i][1]-goodsegs[i][0]) * (goodsegs[i][0]-sharpcorners[i]) > 0
1056 && (prevseg[1]-prevseg[0]) * (sharpcorners[i]-prevseg[1]) > 0
1057 ],
1058 steps = is_def(delta) ? undef
1059 : [
1060 for(i=[0:len(goodsegs)-1])
1061 r==0 ? 0
1062 : !closed && (i==0 || i==len(goodsegs)-1) ? 0 // We don't round ends of open paths
1063 // floor is important here to ensure we don't generate extra segments when nearly straight paths expand outward
1064 : let(vang = vector_angle(select(goodsegs,i-1)[1]-goodpath[i],
1065 goodsegs[i][0]-goodpath[i]))
1066 assert(!outsidecorner[i] || vang!=0, // If outsidecorner[i] is true then vang>0 needed to give valid step count
1067 "Offset computation failed, probably because validity check mistakenly removed a valid segment. Increasing quality might fix this.")
1068 1+floor(segs(r)*vang/360)
1069 ],
1070 // newcorners is a list where each entry is a list of the points that correspond to a single point in the sharpcorners
1071 // list: newcorners[i] is the point list that replaces goodpath[i]. Without rounding or chamfering (or reversals),
1072 // this means each entry of newcorners is a singleton list. But in the other cases, multiple points may appear at
1073 // a given position; newcorners later gets flattened to produce the final list, but the structure is needed to
1074 // establish point alignment for creating faces, or for duplicating points if same_length is true.
1075 newcorners =
1076 [for(i=idx(goodsegs))
1077 let(
1078 basepts = [ select(goodsegs,i-1)[1], goodsegs[i][0] ]
1079 )
1080 is_def(sharpcorners[i]) &&
1081 ((is_def(steps) && steps[i] <=1) // Don't round if steps is smaller than 2
1082 || !outsidecorner[i]) // Don't round inside corners
1083 ? [sharpcorners[i]]
1084 : chamfer ? _offset_chamfer(
1085 goodpath[i], [
1086 select(goodsegs,i-1)[1],
1087 sharpcorners[i],
1088 goodsegs[i][0]
1089 ], d
1090 )
1091 : is_def(delta) ?
1092 (
1093 is_def(sharpcorners[i]) ? [sharpcorners[i]]
1094 : let(normal = d*line_normal(basepts))
1095 basepts + [normal,normal]
1096 )
1097 : // rounded case
1098 let(
1099 class =_tri_class( [ each select(goodsegs,i-1), goodsegs[i][0]]),
1100 cw = class==1,
1101 ccw = class==-1
1102 )
1103 arc(cp=goodpath[i], cw=cw, ccw=ccw,
1104 points=basepts,
1105 n=steps[i]+3)
1106 ],
1107 pointcount = [for(entry=newcorners) len(entry)],
1108 edges = flatten(newcorners),
1109 faces = !return_faces? []
1110 : _makefaces(
1111 flip_faces, firstface_index, good,
1112 pointcount, closed
1113 ),
1114 final_edges = same_length ? select(edges,
1115 [0,
1116 each list_head(cumsum([for(g=good) g?1:0]))
1117 ]
1118 )
1119 : edges
1120 ) return_faces? [edges,faces] : final_edges;
1121
1122
1123
1124/// Internal Function: _filter_region_parts()
1125///
1126/// splits region1 into subpaths where either it touches itself or crosses region2. Classifies all of the
1127/// subpaths as described below and keeps the ones listed in keep1. A similar process is performed for region2.
1128/// All of the kept subpaths are assembled into polygons and returned as a lst.
1129/// .
1130/// The four types of subpath from the region are defined relative to the second region:
1131/// "O" - the subpath is outside the second region
1132/// "I" - the subpath is in the second region's interior
1133/// "S" - the subpath is on the 2nd region's border and the two regions interiors are on the same side of the subpath
1134/// "U" - the subpath is on the 2nd region's border and the two regions meet at the subpath from opposite sides
1135/// You specify which type of subpaths to keep with a string of the desired types such as "OS".
1136function _filter_region_parts(region1, region2, keep, eps=EPSILON) =
1137 // We have to compute common vertices between paths in the region because
1138 // they can be places where the path must be cut, even though they aren't
1139 // found my the split_path function.
1140 let(
1141 subpaths = split_region_at_region_crossings(region1,region2,eps=eps),
1142 regions=[force_region(region1),
1143 force_region(region2)]
1144 )
1145 _assemble_path_fragments(
1146 [for(i=[0:1])
1147 let(
1148 keepS = search("S",keep[i])!=[],
1149 keepU = search("U",keep[i])!=[],
1150 keepoutside = search("O",keep[i]) !=[],
1151 keepinside = search("I",keep[i]) !=[],
1152 all_subpaths = flatten(subpaths[i])
1153 )
1154 for (subpath = all_subpaths)
1155 let(
1156 midpt = mean([subpath[0], subpath[1]]),
1157 rel = point_in_region(midpt,regions[1-i],eps=eps),
1158 keepthis = rel<0 ? keepoutside
1159 : rel>0 ? keepinside
1160 : !(keepS || keepU) ? false
1161 : let(
1162 sidept = midpt + 0.01*line_normal(subpath[0],subpath[1]),
1163 rel1 = point_in_region(sidept,regions[0],eps=eps)>0,
1164 rel2 = point_in_region(sidept,regions[1],eps=eps)>0
1165 )
1166 rel1==rel2 ? keepS : keepU
1167 )
1168 if (keepthis) subpath
1169 ]
1170 );
1171
1172
1173function _list_three(a,b,c) =
1174 is_undef(b) ? a :
1175 [
1176 a,
1177 if (is_def(b)) b,
1178 if (is_def(c)) c
1179 ];
1180
1181
1182
1183// Function&Module: union()
1184// Synopsis: Performs a Boolean union operation.
1185// SynTags: Geom, Region
1186// Topics: Boolean Operations, Regions, Polygons, Shapes2D, Shapes3D
1187// See Also: difference(), intersection(), diff(), intersect(), exclusive_or()
1188// Usage:
1189// union() CHILDREN;
1190// region = union(regions);
1191// region = union(REGION1,REGION2);
1192// region = union(REGION1,REGION2,REGION3);
1193// Description:
1194// When called as a function and given a list of regions or 2D polygons,
1195// returns the union of all given regions and polygons. Result is a single region.
1196// When called as the built-in module, makes the union of the given children.
1197// This function is **much** slower than the native union module acting on geometry,
1198// so you should only use it when you need a point list for further processing.
1199// Arguments:
1200// regions = List of regions to union.
1201// Example(2D):
1202// shape1 = move([-8,-8,0], p=circle(d=50));
1203// shape2 = move([ 8, 8,0], p=circle(d=50));
1204// color("green") region(union(shape1,shape2));
1205// for (shape = [shape1,shape2]) color("red") stroke(shape, width=0.5, closed=true);
1206function union(regions=[],b=undef,c=undef,eps=EPSILON) =
1207 let(regions=_list_three(regions,b,c))
1208 len(regions)==0? [] :
1209 len(regions)==1? regions[0] :
1210 let(regions=[for (r=regions) is_path(r)? [r] : r])
1211 union([
1212 _filter_region_parts(regions[0],regions[1],["OS", "O"], eps=eps),
1213 for (i=[2:1:len(regions)-1]) regions[i]
1214 ],
1215 eps=eps
1216 );
1217
1218
1219// Function&Module: difference()
1220// Synopsis: Performs a Boolean difference operation.
1221// SynTags: Geom, Region
1222// Topics: Boolean Operations, Regions, Polygons, Shapes2D, Shapes3D
1223// See Also: union(), intersection(), diff(), intersect(), exclusive_or()
1224// Usage:
1225// difference() CHILDREN;
1226// region = difference(regions);
1227// region = difference(REGION1,REGION2);
1228// region = difference(REGION1,REGION2,REGION3);
1229// Description:
1230// When called as a function, and given a list of regions or 2D polygons,
1231// takes the first region or polygon and differences away all other regions/polygons from it. The resulting
1232// region is returned.
1233// When called as the built-in module, makes the set difference of the given children.
1234// This function is **much** slower than the native difference module acting on geometry,
1235// so you should only use it when you need a point list for further processing.
1236// Arguments:
1237// regions = List of regions or polygons to difference.
1238// Example(2D):
1239// shape1 = move([-8,-8,0], p=circle(d=50));
1240// shape2 = move([ 8, 8,0], p=circle(d=50));
1241// for (shape = [shape1,shape2]) color("red") stroke(shape, width=0.5, closed=true);
1242// color("green") region(difference(shape1,shape2));
1243function difference(regions=[],b=undef,c=undef,eps=EPSILON) =
1244 let(regions = _list_three(regions,b,c))
1245 len(regions)==0? []
1246 : len(regions)==1? regions[0]
1247 : regions[0]==[] ? []
1248 : let(regions=[for (r=regions) is_path(r)? [r] : r])
1249 difference([
1250 _filter_region_parts(regions[0],regions[1],["OU", "I"], eps=eps),
1251 for (i=[2:1:len(regions)-1]) regions[i]
1252 ],
1253 eps=eps
1254 );
1255
1256
1257// Function&Module: intersection()
1258// Synopsis: Performs a Boolean intersection operation.
1259// SynTags: Geom, Region
1260// Topics: Boolean Operations, Regions, Polygons, Shapes2D, Shapes3D
1261// See Also: difference(), union(), diff(), intersect(), exclusive_or()
1262// Usage:
1263// intersection() CHILDREN;
1264// region = intersection(regions);
1265// region = intersection(REGION1,REGION2);
1266// region = intersection(REGION1,REGION2,REGION3);
1267// Description:
1268// When called as a function, and given a list of regions or polygons returns the
1269// intersection of all given regions. Result is a single region.
1270// When called as the built-in module, makes the intersection of all the given children.
1271// Arguments:
1272// regions = List of regions to intersect.
1273// Example(2D):
1274// shape1 = move([-8,-8,0], p=circle(d=50));
1275// shape2 = move([ 8, 8,0], p=circle(d=50));
1276// for (shape = [shape1,shape2]) color("red") stroke(shape, width=0.5, closed=true);
1277// color("green") region(intersection(shape1,shape2));
1278function intersection(regions=[],b=undef,c=undef,eps=EPSILON) =
1279 let(regions = _list_three(regions,b,c))
1280 len(regions)==0 ? []
1281 : len(regions)==1? regions[0]
1282 : regions[0]==[] || regions[1]==[] ? []
1283 : intersection([
1284 _filter_region_parts(regions[0],regions[1],["IS","I"],eps=eps),
1285 for (i=[2:1:len(regions)-1]) regions[i]
1286 ],
1287 eps=eps
1288 );
1289
1290
1291
1292// Function&Module: exclusive_or()
1293// Synopsis: Performs a Boolean exclusive-or operation.
1294// SynTags: Geom, Region
1295// Topics: Boolean Operations, Regions, Polygons, Shapes2D, Shapes3D
1296// See Also: union(), difference(), intersection(), diff(), intersect()
1297// Usage:
1298// exclusive_or() CHILDREN;
1299// region = exclusive_or(regions);
1300// region = exclusive_or(REGION1,REGION2);
1301// region = exclusive_or(REGION1,REGION2,REGION3);
1302// Description:
1303// When called as a function and given a list of regions or 2D polygons,
1304// returns the exclusive_or of all given regions. Result is a single region.
1305// When called as a module, performs a Boolean exclusive-or of up to 10 children. Note that when
1306// the input regions cross each other the exclusive-or operator will produce shapes that
1307// meet at corners (non-simple regions), which do not render in CGAL.
1308// This function is **much** slower than the native intersection module acting on geometry,
1309// so you should only use it when you need a point list for further processing.
1310// Arguments:
1311// regions = List of regions or polygons to exclusive_or
1312// Example(2D): As Function. A linear_sweep of this shape fails to render in CGAL.
1313// shape1 = move([-8,-8,0], p=circle(d=50));
1314// shape2 = move([ 8, 8,0], p=circle(d=50));
1315// for (shape = [shape1,shape2])
1316// color("red") stroke(shape, width=0.5, closed=true);
1317// color("green") region(exclusive_or(shape1,shape2));
1318// Example(2D): As Module. A linear_extrude() of the resulting geometry fails to render in CGAL.
1319// exclusive_or() {
1320// square(40,center=false);
1321// circle(d=40);
1322// }
1323function exclusive_or(regions=[],b=undef,c=undef,eps=EPSILON) =
1324 let(regions = _list_three(regions,b,c))
1325 len(regions)==0? []
1326 : len(regions)==1? force_region(regions[0])
1327 : regions[0]==[] ? exclusive_or(list_tail(regions))
1328 : regions[1]==[] ? exclusive_or(list_remove(regions,1))
1329 : exclusive_or([
1330 _filter_region_parts(regions[0],regions[1],["IO","IO"],eps=eps),
1331 for (i=[2:1:len(regions)-1]) regions[i]
1332 ],
1333 eps=eps
1334 );
1335
1336
1337module exclusive_or() {
1338 if ($children==1) {
1339 children();
1340 } else if ($children==2) {
1341 difference() {
1342 children(0);
1343 children(1);
1344 }
1345 difference() {
1346 children(1);
1347 children(0);
1348 }
1349 } else if ($children==3) {
1350 exclusive_or() {
1351 exclusive_or() {
1352 children(0);
1353 children(1);
1354 }
1355 children(2);
1356 }
1357 } else if ($children==4) {
1358 exclusive_or() {
1359 exclusive_or() {
1360 children(0);
1361 children(1);
1362 }
1363 exclusive_or() {
1364 children(2);
1365 children(3);
1366 }
1367 }
1368 } else if ($children==5) {
1369 exclusive_or() {
1370 exclusive_or() {
1371 children(0);
1372 children(1);
1373 children(2);
1374 children(3);
1375 }
1376 children(4);
1377 }
1378 } else if ($children==6) {
1379 exclusive_or() {
1380 exclusive_or() {
1381 children(0);
1382 children(1);
1383 children(2);
1384 children(3);
1385 }
1386 children(4);
1387 children(5);
1388 }
1389 } else if ($children==7) {
1390 exclusive_or() {
1391 exclusive_or() {
1392 children(0);
1393 children(1);
1394 children(2);
1395 children(3);
1396 }
1397 children(4);
1398 children(5);
1399 children(6);
1400 }
1401 } else if ($children==8) {
1402 exclusive_or() {
1403 exclusive_or() {
1404 children(0);
1405 children(1);
1406 children(2);
1407 children(3);
1408 }
1409 exclusive_or() {
1410 children(4);
1411 children(5);
1412 children(6);
1413 children(7);
1414 }
1415 }
1416 } else if ($children==9) {
1417 exclusive_or() {
1418 exclusive_or() {
1419 children(0);
1420 children(1);
1421 children(2);
1422 children(3);
1423 }
1424 exclusive_or() {
1425 children(4);
1426 children(5);
1427 children(6);
1428 children(7);
1429 }
1430 children(8);
1431 }
1432 } else if ($children==10) {
1433 exclusive_or() {
1434 exclusive_or() {
1435 children(0);
1436 children(1);
1437 children(2);
1438 children(3);
1439 }
1440 exclusive_or() {
1441 children(4);
1442 children(5);
1443 children(6);
1444 children(7);
1445 }
1446 children(8);
1447 children(9);
1448 }
1449 } else {
1450 assert($children<=10, "exclusive_or() can only handle up to 10 children.");
1451 }
1452}
1453
1454
1455
1456// Function&Module: hull_region()
1457// Synopsis: Compute convex hull of region or 2d path
1458// SynTags: Geom, Path
1459// Topics: Regions, Polygons, Shapes2D
1460// Usage:
1461// path = hull_region(region);
1462// hull_region(region);
1463// Description:
1464// Given a path, or a region, compute the convex hull
1465// and return it as a path. This differs from {{hull()}} and {{hull2d_path()}} which
1466// return an index list into the point list. As a module invokes the native hull() on
1467// the specified region.
1468// Arguments:
1469// region = region or path listing points to compute the hull from.
1470// Example(2D, NoAxes):
1471// data = [star(id=10,od=20,n=9),
1472// right(30, star(id=12,od=25, n=7))];
1473// stroke(data);
1474// stroke([hull_region(data)],color="red");
1475function hull_region(region) =
1476 assert(is_path(region) || is_region(region))
1477 let(
1478 pts = is_region(region) ? flatten(region)
1479 : region,
1480 order = hull2d_path(pts)
1481 )
1482 select(pts,order);
1483
1484module hull_region(region)
1485{
1486 hull()region(region);
1487}
1488
1489
1490// vim: expandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap