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(), 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// Example(2D): Displaying a region
318// region([circle(d=50), square(25,center=true)]);
319// Example(2D): Displaying a list of polygons that intersect each other, which is not a region
320// rgn = concat(
321// [for (d=[50:-10:10]) circle(d=d-5)],
322// [square([60,10], center=true)]
323// );
324// region(rgn);
325module region(r, anchor="origin", spin=0, cp="centroid", atype="hull")
326{
327 assert(in_list(atype, _ANCHOR_TYPES), "Anchor type must be \"hull\" or \"intersect\"");
328 r = force_region(r);
329 dummy=assert(is_region(r), "Input is not a region");
330 points = flatten(r);
331 lengths = [for(path=r) len(path)];
332 starts = [0,each cumsum(lengths)];
333 paths = [for(i=idx(r)) count(s=starts[i], n=lengths[i])];
334 attachable(anchor, spin, two_d=true, region=r, extent=atype=="hull", cp=cp){
335 polygon(points=points, paths=paths);
336 children();
337 }
338}
339
340
341
342// Section: Gometrical calculations with regions
343
344// Function: point_in_region()
345// Synopsis: Tests if a point is inside, outside, or on the border of a region.
346// Topics: Regions, Points, Comparison
347// See Also: region_area(), are_regions_equal()
348// Usage:
349// check = point_in_region(point, region, [eps]);
350// Description:
351// Tests if a point is inside, outside, or on the border of a region.
352// Returns -1 if the point is outside the region.
353// Returns 0 if the point is on the boundary.
354// Returns 1 if the point lies inside the region.
355// Arguments:
356// point = The point to test.
357// region = The region to test against, as a list of polygon paths.
358// eps = Acceptable variance. Default: `EPSILON` (1e-9)
359// Example(2D,Med): Red points are in the region.
360// region = [for(i=[2:4:10]) hexagon(r=i)];
361// color("#ff7") region(region);
362// for(x=[-10:10], y=[-10:10])
363// if (point_in_region([x,y], region)>=0)
364// move([x,y]) color("red") circle(0.15, $fn=12);
365// else
366// move([x,y]) color("#ddf") circle(0.1, $fn=12);
367function point_in_region(point, region, eps=EPSILON) =
368 let(region=force_region(region))
369 assert(is_region(region), "Region given to point_in_region is not a region")
370 assert(is_vector(point,2), "Point must be a 2D point in point_in_region")
371 _point_in_region(point, region, eps);
372
373function _point_in_region(point, region, eps=EPSILON, i=0, cnt=0) =
374 i >= len(region) ? ((cnt%2==1)? 1 : -1)
375 : let(
376 pip = point_in_polygon(point, region[i], eps=eps)
377 )
378 pip == 0 ? 0
379 : _point_in_region(point, region, eps=eps, i=i+1, cnt = cnt + (pip>0? 1 : 0));
380
381
382// Function: region_area()
383// Synopsis: Computes the area of the specified valid region.
384// Topics: Regions, Area
385// Usage:
386// area = region_area(region);
387// Description:
388// Computes the area of the specified valid region. (If the region is invalid and has self intersections
389// the result is meaningless.)
390// Arguments:
391// region = region whose area to compute
392// Examples:
393// area = region_area([square(10), right(20,square(8))]); // Returns 164
394function region_area(region) =
395 assert(is_region(region), "Input must be a region")
396 let(
397 parts = region_parts(region)
398 )
399 -sum([for(R=parts, poly=R) polygon_area(poly,signed=true)]);
400
401
402
403function _clockwise_region(r) = [for(p=r) clockwise_polygon(p)];
404
405// Function: are_regions_equal()
406// Synopsis: Returns true if given regions are the same polygons.
407// Topics: Regions, Polygons, Comparison
408// Usage:
409// b = are_regions_equal(region1, region2, [either_winding])
410// Description:
411// Returns true if the components of region1 and region2 are the same polygons (in any order).
412// Arguments:
413// region1 = first region
414// region2 = second region
415// either_winding = if true then two shapes test equal if they wind in opposite directions. Default: false
416function are_regions_equal(region1, region2, either_winding=false) =
417 let(
418 region1=force_region(region1),
419 region2=force_region(region2)
420 )
421 assert(is_region(region1) && is_region(region2), "One of the inputs is not a region")
422 len(region1) != len(region2)? false :
423 __are_regions_equal(either_winding?_clockwise_region(region1):region1,
424 either_winding?_clockwise_region(region2):region2,
425 0);
426
427function __are_regions_equal(region1, region2, i) =
428 i >= len(region1)? true :
429 !_is_polygon_in_list(region1[i], region2)? false :
430 __are_regions_equal(region1, region2, i+1);
431
432
433/// Internal Function: _region_region_intersections()
434/// Usage:
435/// risect = _region_region_intersections(region1, region2, [closed1], [closed2], [eps]
436/// Description:
437/// Returns a pair of sorted lists such that risect[0] is a list of intersection
438/// points for every path in region1, and similarly risect[1] is a list of intersection
439/// points for the paths in region2. For each path the intersection list is
440/// a sorted list of the form [PATHIND, SEGMENT, U]. You can specify that the paths in either
441/// region be regarded as open paths if desired. Default is to treat them as
442/// regions and hence the paths as closed polygons.
443/// .
444/// Included as intersection points are points where region1 touches itself at a vertex or
445/// region2 touches itself at a vertex. (The paths are assumed to have no self crossings.
446/// Self crossings of the paths in the regions are not returned.)
447function _region_region_intersections(region1, region2, closed1=true,closed2=true, eps=EPSILON) =
448 let(
449 intersections = [
450 for(p1=idx(region1))
451 let(
452 path = closed1?list_wrap(region1[p1]):region1[p1]
453 )
454 for(i = [0:1:len(path)-2])
455 let(
456 a1 = path[i],
457 a2 = path[i+1],
458 nrm = norm(a1-a2)
459 )
460 if( nrm>eps ) // ignore zero-length path edges
461 let(
462 seg_normal = [-(a2-a1).y, (a2-a1).x]/nrm,
463 ref = a1*seg_normal
464 )
465 // `signs[j]` is the sign of the signed distance from
466 // poly vertex j to the line [a1,a2] where near zero
467 // distances are snapped to zero; poly edges
468 // with equal signs at its vertices cannot intersect
469 // the path edge [a1,a2] or they are collinear and
470 // further tests can be discarded.
471 for(p2=idx(region2))
472 let(
473 poly = closed2?list_wrap(region2[p2]):region2[p2],
474 signs = [for(v=poly*seg_normal) abs(v-ref) < eps ? 0 : sign(v-ref) ]
475 )
476 if(max(signs)>=0 && min(signs)<=0) // some edge intersects line [a1,a2]
477 for(j=[0:1:len(poly)-2])
478 if(signs[j]!=signs[j+1])
479 let( // exclude non-crossing and collinear segments
480 b1 = poly[j],
481 b2 = poly[j+1],
482 isect = _general_line_intersection([a1,a2],[b1,b2],eps=eps)
483 )
484 if (isect
485 && isect[1]>= -eps
486 && isect[1]<= 1+eps
487 && isect[2]>= -eps
488 && isect[2]<= 1+eps)
489 [[p1,i,isect[1]], [p2,j,isect[2]]]
490 ],
491 regions=[region1,region2],
492 // Create a flattened index list corresponding to the points in region1 and region2
493 // that gives each point as an intersection point
494 ptind = [for(i=[0:1])
495 [for(p=idx(regions[i]))
496 for(j=idx(regions[i][p])) [p,j,0]]],
497 points = [for(i=[0:1]) flatten(regions[i])],
498 // Corner points are those points where the region touches itself, hence duplicate
499 // points in the region's point set
500 cornerpts = [for(i=[0:1])
501 [for(k=vector_search(points[i],eps,points[i]))
502 each if (len(k)>1) select(ptind[i],k)]],
503 risect = [for(i=[0:1]) concat(column(intersections,i), cornerpts[i])],
504 counts = [count(len(region1)), count(len(region2))],
505 pathind = [for(i=[0:1]) search(counts[i], risect[i], 0)]
506 )
507 [for(i=[0:1]) [for(j=counts[i]) _sort_vectors(select(risect[i],pathind[i][j]))]];
508
509
510// Section: Breaking up regions into subregions
511
512
513// Function: split_region_at_region_crossings()
514// Synopsis: Splits regions where polygons touch and at intersections.
515// Topics: Regions, Polygons, List Handling
516// See Also: region_parts()
517//
518// Usage:
519// split_region = split_region_at_region_crossings(region1, region2, [closed1], [closed2], [eps])
520// Description:
521// Splits region1 at the places where polygons in region1 touches each other at corners and at locations
522// where region1 intersections region2. Split region2 similarly with respect to region1.
523// The return is a pair of results of the form [split1, split2] where split1=[frags1,frags2,...]
524// and frags1 is a list of paths that when placed end to end (in the given order), give the first polygon of region1.
525// Each path in the list is either entirely inside or entirely outside region2.
526// Then frags2 is the decomposition of the second polygon into path pieces, and so on. Finally split2 is
527// the same list, but for the polygons in region2.
528// You can pass a single polygon in for either region, but the output will be a singleton list, as if
529// you passed in a singleton region. If you set the closed parameters to false then the region components
530// will be treated as open paths instead of polygons.
531// Arguments:
532// region1 = first region
533// region2 = second region
534// closed1 = if false then treat region1 as list of open paths. Default: true
535// closed2 = if false then treat region2 as list of open paths. Default: true
536// eps = Acceptable variance. Default: `EPSILON` (1e-9)
537// Example(2D):
538// path = square(50,center=false);
539// region = [circle(d=80), circle(d=40)];
540// paths = split_region_at_region_crossings(path, region);
541// color("#aaa") region(region);
542// rainbow(paths[0][0]) stroke($item, width=2);
543// right(110){
544// color("#aaa") region([path]);
545// rainbow(flatten(paths[1])) stroke($item, width=2);
546// }
547function split_region_at_region_crossings(region1, region2, closed1=true, closed2=true, eps=EPSILON) =
548 let(
549 region1=force_region(region1),
550 region2=force_region(region2)
551 )
552 assert(is_region(region1) && is_region(region2),"One of the inputs is not a region")
553 let(
554 xings = _region_region_intersections(region1, region2, closed1, closed2, eps),
555 regions = [region1,region2],
556 closed = [closed1,closed2]
557 )
558 [for(i=[0:1])
559 [for(p=idx(xings[i]))
560 let(
561 crossings = deduplicate([
562 [p,0,0],
563 each xings[i][p],
564 [p,len(regions[i][p])-(closed[i]?1:2), 1],
565 ],eps=eps),
566 subpaths = [
567 for (frag = pair(crossings))
568 deduplicate(
569 _path_select(regions[i][p], frag[0][1], frag[0][2], frag[1][1], frag[1][2], closed=closed[i]),
570 eps=eps
571 )
572 ]
573 )
574 [for(s=subpaths) if (len(s)>1) s]
575 ]
576 ];
577
578
579
580// Function: region_parts()
581// Synopsis: Splits a region into a list of regions.
582// SynTags: RegList
583// Topics: Regions, List Handling
584// See Also: split_region_at_region_crossings()
585// Usage:
586// rgns = region_parts(region);
587// Description:
588// Divides a region into a list of connected regions. Each connected region has exactly one clockwise outside boundary
589// and zero or more counter-clockwise outlines defining internal holes. Note that behavior is undefined on invalid regions whose
590// components cross each other.
591// Example(2D,NoAxes):
592// R = [for(i=[1:7]) square(i,center=true)];
593// region_list = region_parts(R);
594// rainbow(region_list) region($item);
595// Example(2D,NoAxes):
596// R = [back(7,square(3,center=true)),
597// square([20,10],center=true),
598// left(5,square(8,center=true)),
599// for(i=[4:2:8])
600// right(5,square(i,center=true))];
601// region_list = region_parts(R);
602// rainbow(region_list) region($item);
603function region_parts(region) =
604 let(
605 region = force_region(region)
606 )
607 assert(is_region(region), "Input is not a region")
608 let(
609 inside = [for(i=idx(region))
610 let(pt = mean([region[i][0], region[i][1]]))
611 [for(j=idx(region)) i==j ? 0
612 : point_in_polygon(pt,region[j]) >=0 ? 1 : 0]
613 ],
614 level = inside*repeat(1,len(region))
615 )
616 [ for(i=idx(region))
617 if(level[i]%2==0)
618 let(
619 possible_children = search([level[i]+1],level,0)[0],
620 keep=search([1], select(inside,possible_children), 0, i)[0]
621 )
622 [
623 clockwise_polygon(region[i]),
624 for(good=keep)
625 ccw_polygon(region[possible_children[good]])
626 ]
627 ];
628
629
630
631
632// Section: Offset and 2D Boolean Set Operations
633
634
635function _offset_chamfer(center, points, delta) =
636 let(
637 dist = sign(delta)*norm(center-line_intersection(select(points,[0,2]), [center, points[1]])),
638 endline = _shift_segment(select(points,[0,2]), delta-dist)
639 ) [
640 line_intersection(endline, select(points,[0,1])),
641 line_intersection(endline, select(points,[1,2]))
642 ];
643
644
645function _shift_segment(segment, d) =
646 assert(!approx(segment[0],segment[1]),"Path has repeated points")
647 move(d*line_normal(segment),segment);
648
649
650// Extend to segments to their intersection point. First check if the segments already have a point in common,
651// which can happen if two colinear segments are input to the path variant of `offset()`
652function _segment_extension(s1,s2) =
653 norm(s1[1]-s2[0])<1e-6 ? s1[1] : line_intersection(s1,s2,LINE,LINE);
654
655
656function _makefaces(direction, startind, good, pointcount, closed) =
657 let(
658 lenlist = list_bset(good, pointcount),
659 numfirst = len(lenlist),
660 numsecond = sum(lenlist),
661 prelim_faces = _makefaces_recurse(startind, startind+len(lenlist), numfirst, numsecond, lenlist, closed)
662 )
663 direction? [for(entry=prelim_faces) reverse(entry)] : prelim_faces;
664
665
666function _makefaces_recurse(startind1, startind2, numfirst, numsecond, lenlist, closed, firstind=0, secondind=0, faces=[]) =
667 // We are done if *both* firstind and secondind reach their max value, which is the last point if !closed or one past
668 // the last point if closed (wrapping around). If you don't check both you can leave a triangular gap in the output.
669 ((firstind == numfirst - (closed?0:1)) && (secondind == numsecond - (closed?0:1)))? faces :
670 _makefaces_recurse(
671 startind1, startind2, numfirst, numsecond, lenlist, closed, firstind+1, secondind+lenlist[firstind],
672 lenlist[firstind]==0? (
673 // point in original path has been deleted in offset path, so it has no match. We therefore
674 // make a triangular face using the current point from the offset (second) path
675 // (The current point in the second path can be equal to numsecond if firstind is the last point)
676 concat(faces,[[secondind%numsecond+startind2, firstind+startind1, (firstind+1)%numfirst+startind1]])
677 // in this case a point or points exist in the offset path corresponding to the original path
678 ) : (
679 concat(faces,
680 // First generate triangular faces for all of the extra points (if there are any---loop may be empty)
681 [for(i=[0:1:lenlist[firstind]-2]) [firstind+startind1, secondind+i+1+startind2, secondind+i+startind2]],
682 // Finish (unconditionally) with a quadrilateral face
683 [
684 [
685 firstind+startind1,
686 (firstind+1)%numfirst+startind1,
687 (secondind+lenlist[firstind])%numsecond+startind2,
688 (secondind+lenlist[firstind]-1)%numsecond+startind2
689 ]
690 ]
691 )
692 )
693 );
694
695
696// Determine which of the shifted segments are good
697function _good_segments(path, d, shiftsegs, closed, quality) =
698 let(
699 maxind = len(path)-(closed ? 1 : 2),
700 pathseg = [for(i=[0:maxind]) select(path,i+1)-path[i]],
701 pathseg_len = [for(seg=pathseg) norm(seg)],
702 pathseg_unit = [for(i=[0:maxind]) pathseg[i]/pathseg_len[i]],
703 // Order matters because as soon as a valid point is found, the test stops
704 // This order works better for circular paths because they succeed in the center
705 alpha = concat([for(i=[1:1:quality]) i/(quality+1)],[0,1])
706 ) [
707 for (i=[0:len(shiftsegs)-1])
708 (i>maxind)? true :
709 _segment_good(path,pathseg_unit,pathseg_len, d - 1e-7, shiftsegs[i], alpha)
710 ];
711
712
713// Determine if a segment is good (approximately)
714// Input is the path, the path segments normalized to unit length, the length of each path segment
715// the distance threshold, the segment to test, and the locations on the segment to test (normalized to [0,1])
716// The last parameter, index, gives the current alpha index.
717//
718// A segment is good if any part of it is farther than distance d from the path. The test is expensive, so
719// we want to quit as soon as we find a point with distance > d, hence the recursive code structure.
720//
721// This test is approximate because it only samples the points listed in alpha. Listing more points
722// will make the test more accurate, but slower.
723function _segment_good(path,pathseg_unit,pathseg_len, d, seg,alpha ,index=0) =
724 index == len(alpha) ? false :
725 _point_dist(path,pathseg_unit,pathseg_len, alpha[index]*seg[0]+(1-alpha[index])*seg[1]) > d ? true :
726 _segment_good(path,pathseg_unit,pathseg_len,d,seg,alpha,index+1);
727
728
729// Input is the path, the path segments normalized to unit length, the length of each path segment
730// and a test point. Computes the (minimum) distance from the path to the point, taking into
731// account that the minimal distance may be anywhere along a path segment, not just at the ends.
732function _point_dist(path,pathseg_unit,pathseg_len,pt) =
733 min([
734 for(i=[0:len(pathseg_unit)-1]) let(
735 v = pt-path[i],
736 projection = v*pathseg_unit[i],
737 segdist = projection < 0? norm(pt-path[i]) :
738 projection > pathseg_len[i]? norm(pt-select(path,i+1)) :
739 norm(v-projection*pathseg_unit[i])
740 ) segdist
741 ]);
742
743
744// Function: offset()
745// Synopsis: Takes a 2D path, polygon or region and returns a path offset by an amount.
746// SynTags: Path, Region
747// Topics: Paths, Polygons, Regions
748// Usage:
749// offsetpath = offset(path, [r=|delta=], [chamfer=], [closed=], [check_valid=], [quality=], [same_length=])
750// path_faces = offset(path, return_faces=true, [r=|delta=], [chamfer=], [closed=], [check_valid=], [quality=], [firstface_index=], [flip_faces=])
751// Description:
752// Takes a 2D input path, polygon or region and returns a path offset by the specified amount. As with the built-in
753// offset() module, you can use `r` to specify rounded offset and `delta` to specify offset with
754// corners. If you used `delta` you can set `chamfer` to true to get chamfers.
755// For paths and polygons positive offsets make the polygons larger. For paths,
756// positive offsets shift the path to the left, relative to the direction of the path. Note
757// that the path must not include any 180 degree turns, where the path reverses direction.
758// .
759// When offsets shrink the path, segments cross and become invalid. By default `offset()` checks
760// for this situation. To test validity the code checks that segments have distance larger than (r
761// or delta) from the input path. This check takes O(N^2) time and may mistakenly eliminate
762// segments you wanted included in various situations, so you can disable it if you wish by setting
763// check_valid=false. Another situation is that the test is not sufficiently thorough and some
764// segments persist that should be eliminated. In this case, increase `quality` to 2 or 3. (This
765// increases the number of samples on the segment that are checked.) Run time will increase. In
766// some situations you may be able to decrease run time by setting quality to 0, which causes only
767// segment ends to be checked.
768// .
769// When invalid segments are eliminated, the path length decreases. If you use chamfering or rounding, then
770// the chamfers and roundings can increase the length of the output path. Hence points in the output may be
771// difficult to associate with the input. If you want to maintain alignment between the points you
772// can use the `same_length` option. This option requires that you use `delta=` with `chamfer=false` to ensure
773// that no points are added. When points collapse to a single point in the offset, the output includes
774// that point repeated to preserve the correct length.
775// .
776// Another way to obtain alignment information is to use the return_faces option, which can
777// provide alignment information for all offset parameters: it returns a face list which lists faces between
778// the original path and the offset path where the vertices are ordered with the original path
779// first, starting at `firstface_index` and the offset path vertices appearing afterwords. The
780// direction of the faces can be flipped using `flip_faces`. When you request faces the return
781// value is a list: [offset_path, face_list].
782// Arguments:
783// path = the path to process. A list of 2d points.
784// ---
785// r = offset radius. Distance to offset. Will round over corners.
786// delta = offset distance. Distance to offset with pointed corners.
787// chamfer = chamfer corners when you specify `delta`. Default: false
788// closed = if true path is treate as a polygon. Default: False.
789// check_valid = perform segment validity check. Default: True.
790// quality = validity check quality parameter, a small integer. Default: 1.
791// same_length = return a path with the same length as the input. Only compatible with `delta=`. Default: false
792// return_faces = return face list. Default: False.
793// firstface_index = starting index for face list. Default: 0.
794// flip_faces = flip face direction. Default: false
795// Example(2D,NoAxes):
796// star = star(5, r=100, ir=30);
797// #stroke(closed=true, star, width=3);
798// stroke(closed=true, width=3, offset(star, delta=10, closed=true));
799// Example(2D,NoAxes):
800// star = star(5, r=100, ir=30);
801// #stroke(closed=true, star, width=3);
802// stroke(closed=true, width=3,
803// offset(star, delta=10, chamfer=true, closed=true));
804// Example(2D,NoAxes):
805// star = star(5, r=100, ir=30);
806// #stroke(closed=true, star, width=3);
807// stroke(closed=true, width=3,
808// offset(star, r=10, closed=true));
809// Example(2D,NoAxes):
810// star = star(7, r=120, ir=50);
811// #stroke(closed=true, width=3, star);
812// stroke(closed=true, width=3,
813// offset(star, delta=-15, closed=true));
814// Example(2D,NoAxes):
815// star = star(7, r=120, ir=50);
816// #stroke(closed=true, width=3, star);
817// stroke(closed=true, width=3,
818// offset(star, delta=-15, chamfer=true, closed=true));
819// Example(2D,NoAxes):
820// star = star(7, r=120, ir=50);
821// #stroke(closed=true, width=3, star);
822// stroke(closed=true, width=3,
823// offset(star, r=-15, closed=true, $fn=20));
824// Example(2D,NoAxes): This case needs `quality=2` for success
825// test = [[0,0],[10,0],[10,7],[0,7], [-1,-3]];
826// polygon(offset(test,r=-1.9, closed=true, quality=2));
827// //polygon(offset(test,r=-1.9, closed=true, quality=1)); // Fails with erroneous 180 deg path error
828// %down(.1)polygon(test);
829// 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.
830// star = star(5, r=22, ir=13);
831// stroke(star,width=.3,closed=true);
832// color("green")
833// stroke(offset(star, delta=-9, closed=true),width=.3,closed=true); // Works with check_valid=true (the default)
834// color("red")
835// stroke(offset(star, delta=-10, closed=true, check_valid=false), // Fails if check_valid=true
836// width=.3,closed=true);
837// 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.
838// star = star(5, r=22, ir=13);
839// color("green")
840// stroke(offset(star, r=-8, closed=true,check_valid=false), width=.1, closed=true);
841// color("red")
842// stroke(offset(star, r=-10, closed=true,check_valid=false), width=.1, closed=true);
843// Example(2D,NoAxes): The extra triangles in this example show that the validity check cannot be skipped
844// ellipse = scale([20,4], p=circle(r=1,$fn=64));
845// stroke(ellipse, closed=true, width=0.3);
846// stroke(offset(ellipse, r=-3, check_valid=false, closed=true),
847// width=0.3, closed=true);
848// Example(2D,NoAxes): The triangles are removed by the validity check
849// ellipse = scale([20,4], p=circle(r=1,$fn=64));
850// stroke(ellipse, closed=true, width=0.3);
851// stroke(offset(ellipse, r=-3, check_valid=true, closed=true),
852// width=0.3, closed=true);
853// Example(2D): Open path. The path moves from left to right and the positive offset shifts to the left of the initial red path.
854// sinpath = 2*[for(theta=[-180:5:180]) [theta/4,45*sin(theta)]];
855// #stroke(sinpath, width=2);
856// stroke(offset(sinpath, r=17.5),width=2);
857// Example(2D,NoAxes): Region
858// rgn = difference(circle(d=100),
859// union(square([20,40], center=true),
860// square([40,20], center=true)));
861// #linear_extrude(height=1.1) stroke(rgn, width=1);
862// region(offset(rgn, r=-5));
863// 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.
864// closed=false;
865// path = [for(angle=[0:5:180]) 10*[angle/100,2*sin(angle)]];
866// opath = offset(path, delta=-3,same_length=true,closed=closed);
867// stroke(path,closed=closed,width=.3);
868// stroke(opath,closed=closed,width=.3);
869// color("red") for(i=idx(path)) stroke([path[i],opath[i]],width=.3);
870
871function offset(
872 path, r=undef, delta=undef, chamfer=false,
873 closed=false, check_valid=true,
874 quality=1, return_faces=false, firstface_index=0,
875 flip_faces=false, same_length=false
876) =
877 assert(!(same_length && return_faces), "Cannot combine return_faces with same_length")
878 is_region(path)?
879 assert(!return_faces, "return_faces not supported for regions.")
880 let(
881 ofsregs = [for(R=region_parts(path))
882 difference([for(i=idx(R)) offset(R[i], r=u_mul(i>0?-1:1,r), delta=u_mul(i>0?-1:1,delta),
883 chamfer=chamfer, check_valid=check_valid, quality=quality,closed=true)])]
884 )
885 union(ofsregs)
886 :
887 let(rcount = num_defined([r,delta]))
888 assert(rcount==1,"Must define exactly one of 'delta' and 'r'")
889 assert(!same_length || (is_def(delta) && !chamfer), "Must specify delta, with chamfer=false, when same_length=true")
890 assert(is_path(path), "Input must be a path or region")
891 let(
892 chamfer = is_def(r) ? false : chamfer,
893 quality = max(0,round(quality)),
894 flip_dir = closed && !is_polygon_clockwise(path)? -1 : 1,
895 d = flip_dir * (is_def(r) ? r : delta)
896 )
897 d==0 && !return_faces ? path :
898 let(
899// shiftsegs = [for(i=[0:len(path)-1]) _shift_segment(select(path,i,i+1), d)],
900 shiftsegs = [for(i=[0:len(path)-2]) _shift_segment([path[i],path[i+1]], d),
901 if (closed) _shift_segment([last(path),path[0]],d)
902 else [path[0],path[1]] // dummy segment, not used
903 ],
904 // good segments are ones where no point on the segment is less than distance d from any point on the path
905 good = check_valid ? _good_segments(path, abs(d), shiftsegs, closed, quality) : repeat(true,len(shiftsegs)),
906 goodsegs = bselect(shiftsegs, good),
907 goodpath = bselect(path,good)
908 )
909 assert(len(goodsegs)-(!closed && select(good,-1)?1:0)>0,"Offset of path is degenerate")
910 let(
911 // Extend the shifted segments to their intersection points
912 sharpcorners = [for(i=[0:len(goodsegs)-1]) _segment_extension(select(goodsegs,i-1), select(goodsegs,i))],
913 // If some segments are parallel then the extended segments are undefined. This case is not handled
914 // Note if !closed the last corner doesn't matter, so exclude it
915 parallelcheck =
916 (len(sharpcorners)==2 && !closed) ||
917 all_defined(closed? sharpcorners : select(sharpcorners, 1,-2))
918 )
919 assert(parallelcheck, "Path contains a segment that reverses direction (180 deg turn)")
920 let(
921 // This is a Boolean array that indicates whether a corner is an outside or inside corner
922 // For outside corners, the newcorner is an extension (angle 0), for inside corners, it turns backward
923 // If either side turns back it is an inside corner---must check both.
924 // Outside corners can get rounded (if r is specified and there is space to round them)
925 outsidecorner = len(sharpcorners)==2 ? [false,false]
926 :
927 [for(i=[0:len(goodsegs)-1])
928 let(prevseg=select(goodsegs,i-1))
929 (i==0 || i==len(goodsegs)-1) && !closed ? false // In open case first entry is bogus
930 :
931 (goodsegs[i][1]-goodsegs[i][0]) * (goodsegs[i][0]-sharpcorners[i]) > 0
932 && (prevseg[1]-prevseg[0]) * (sharpcorners[i]-prevseg[1]) > 0
933 ],
934 steps = is_def(delta) ? [] : [
935 for(i=[0:len(goodsegs)-1])
936 r==0 ? 0
937 // if path is open but first and last entries match value is not used, but
938 // computation below gives error, so special case handle it
939 : i==len(goodsegs)-1 && !closed && approx(goodpath[i],goodsegs[i][0]) ? 0
940 // floor is important here to ensure we don't generate extra segments when nearly straight paths expand outward
941 : 1+floor(segs(r)*vector_angle(
942 select(goodsegs,i-1)[1]-goodpath[i],
943 goodsegs[i][0]-goodpath[i])
944 /360)
945 ],
946 // If rounding is true then newcorners replaces sharpcorners with rounded arcs where needed
947 // Otherwise it's the same as sharpcorners
948 // If rounding is on then newcorners[i] will be the point list that replaces goodpath[i] and newcorners later
949 // gets flattened. If rounding is off then we set it to [sharpcorners] so we can later flatten it and get
950 // plain sharpcorners back.
951 newcorners = is_def(delta) && !chamfer ? [sharpcorners]
952 : [for(i=[0:len(goodsegs)-1])
953 (!chamfer && steps[i] <=1) // Don't round if steps is smaller than 2
954 || !outsidecorner[i] // Don't round inside corners
955 || (!closed && (i==0 || i==len(goodsegs)-1)) // Don't round ends of an open path
956 ? [sharpcorners[i]]
957 : chamfer ? _offset_chamfer(
958 goodpath[i], [
959 select(goodsegs,i-1)[1],
960 sharpcorners[i],
961 goodsegs[i][0]
962 ], d
963 )
964 : // rounded case
965 arc(cp=goodpath[i],
966 points=[
967 select(goodsegs,i-1)[1],
968 goodsegs[i][0]
969 ],
970 n=steps[i])
971 ],
972 pointcount = (is_def(delta) && !chamfer)?
973 repeat(1,len(sharpcorners)) :
974 [for(i=[0:len(goodsegs)-1]) len(newcorners[i])],
975 start = [goodsegs[0][0]],
976 end = [goodsegs[len(goodsegs)-2][1]],
977 edges = closed?
978 flatten(newcorners) :
979 concat(start,slice(flatten(newcorners),1,-2),end),
980 faces = !return_faces? [] :
981 _makefaces(
982 flip_faces, firstface_index, good,
983 pointcount, closed
984 ),
985 final_edges = same_length ? select(edges, [0,each list_head (cumsum([for(g=good) g?1:0]))])
986 : edges
987 ) return_faces? [edges,faces] : final_edges;
988
989
990
991/// Internal Function: _filter_region_parts()
992///
993/// splits region1 into subpaths where either it touches itself or crosses region2. Classifies all of the
994/// subpaths as described below and keeps the ones listed in keep1. A similar process is performed for region2.
995/// All of the kept subpaths are assembled into polygons and returned as a lst.
996/// .
997/// The four types of subpath from the region are defined relative to the second region:
998/// "O" - the subpath is outside the second region
999/// "I" - the subpath is in the second region's interior
1000/// "S" - the subpath is on the 2nd region's border and the two regions interiors are on the same side of the subpath
1001/// "U" - the subpath is on the 2nd region's border and the two regions meet at the subpath from opposite sides
1002/// You specify which type of subpaths to keep with a string of the desired types such as "OS".
1003function _filter_region_parts(region1, region2, keep, eps=EPSILON) =
1004 // We have to compute common vertices between paths in the region because
1005 // they can be places where the path must be cut, even though they aren't
1006 // found my the split_path function.
1007 let(
1008 subpaths = split_region_at_region_crossings(region1,region2,eps=eps),
1009 regions=[force_region(region1),
1010 force_region(region2)]
1011 )
1012 _assemble_path_fragments(
1013 [for(i=[0:1])
1014 let(
1015 keepS = search("S",keep[i])!=[],
1016 keepU = search("U",keep[i])!=[],
1017 keepoutside = search("O",keep[i]) !=[],
1018 keepinside = search("I",keep[i]) !=[],
1019 all_subpaths = flatten(subpaths[i])
1020 )
1021 for (subpath = all_subpaths)
1022 let(
1023 midpt = mean([subpath[0], subpath[1]]),
1024 rel = point_in_region(midpt,regions[1-i],eps=eps),
1025 keepthis = rel<0 ? keepoutside
1026 : rel>0 ? keepinside
1027 : !(keepS || keepU) ? false
1028 : let(
1029 sidept = midpt + 0.01*line_normal(subpath[0],subpath[1]),
1030 rel1 = point_in_region(sidept,regions[0],eps=eps)>0,
1031 rel2 = point_in_region(sidept,regions[1],eps=eps)>0
1032 )
1033 rel1==rel2 ? keepS : keepU
1034 )
1035 if (keepthis) subpath
1036 ]
1037 );
1038
1039
1040function _list_three(a,b,c) =
1041 is_undef(b) ? a :
1042 [
1043 a,
1044 if (is_def(b)) b,
1045 if (is_def(c)) c
1046 ];
1047
1048
1049
1050// Function&Module: union()
1051// Synopsis: Performs a Boolean union operation.
1052// SynTags: Geom, Region
1053// Topics: Boolean Operations, Regions, Polygons, Shapes2D, Shapes3D
1054// See Also: difference(), intersection(), diff(), intersect(), exclusive_or()
1055// Usage:
1056// union() CHILDREN;
1057// region = union(regions);
1058// region = union(REGION1,REGION2);
1059// region = union(REGION1,REGION2,REGION3);
1060// Description:
1061// When called as a function and given a list of regions or 2D polygons,
1062// returns the union of all given regions and polygons. Result is a single region.
1063// When called as the built-in module, makes the union of the given children.
1064// Arguments:
1065// regions = List of regions to union.
1066// Example(2D):
1067// shape1 = move([-8,-8,0], p=circle(d=50));
1068// shape2 = move([ 8, 8,0], p=circle(d=50));
1069// color("green") region(union(shape1,shape2));
1070// for (shape = [shape1,shape2]) color("red") stroke(shape, width=0.5, closed=true);
1071function union(regions=[],b=undef,c=undef,eps=EPSILON) =
1072 let(regions=_list_three(regions,b,c))
1073 len(regions)==0? [] :
1074 len(regions)==1? regions[0] :
1075 let(regions=[for (r=regions) is_path(r)? [r] : r])
1076 union([
1077 _filter_region_parts(regions[0],regions[1],["OS", "O"], eps=eps),
1078 for (i=[2:1:len(regions)-1]) regions[i]
1079 ],
1080 eps=eps
1081 );
1082
1083
1084// Function&Module: difference()
1085// Synopsis: Performs a Boolean difference operation.
1086// SynTags: Geom, Region
1087// Topics: Boolean Operations, Regions, Polygons, Shapes2D, Shapes3D
1088// See Also: union(), intersection(), diff(), intersect(), exclusive_or()
1089// Usage:
1090// difference() CHILDREN;
1091// region = difference(regions);
1092// region = difference(REGION1,REGION2);
1093// region = difference(REGION1,REGION2,REGION3);
1094// Description:
1095// When called as a function, and given a list of regions or 2D polygons,
1096// takes the first region or polygon and differences away all other regions/polygons from it. The resulting
1097// region is returned.
1098// When called as the built-in module, makes the set difference of the given children.
1099// Arguments:
1100// regions = List of regions or polygons to difference.
1101// Example(2D):
1102// shape1 = move([-8,-8,0], p=circle(d=50));
1103// shape2 = move([ 8, 8,0], p=circle(d=50));
1104// for (shape = [shape1,shape2]) color("red") stroke(shape, width=0.5, closed=true);
1105// color("green") region(difference(shape1,shape2));
1106function difference(regions=[],b=undef,c=undef,eps=EPSILON) =
1107 let(regions = _list_three(regions,b,c))
1108 len(regions)==0? []
1109 : len(regions)==1? regions[0]
1110 : regions[0]==[] ? []
1111 : let(regions=[for (r=regions) is_path(r)? [r] : r])
1112 difference([
1113 _filter_region_parts(regions[0],regions[1],["OU", "I"], eps=eps),
1114 for (i=[2:1:len(regions)-1]) regions[i]
1115 ],
1116 eps=eps
1117 );
1118
1119
1120// Function&Module: intersection()
1121// Synopsis: Performs a Boolean intersection operation.
1122// SynTags: Geom, Region
1123// Topics: Boolean Operations, Regions, Polygons, Shapes2D, Shapes3D
1124// See Also: difference(), union(), diff(), intersect(), exclusive_or()
1125// Usage:
1126// intersection() CHILDREN;
1127// region = intersection(regions);
1128// region = intersection(REGION1,REGION2);
1129// region = intersection(REGION1,REGION2,REGION3);
1130// Description:
1131// When called as a function, and given a list of regions or polygons returns the
1132// intersection of all given regions. Result is a single region.
1133// When called as the built-in module, makes the intersection of all the given children.
1134// Arguments:
1135// regions = List of regions to intersect.
1136// Example(2D):
1137// shape1 = move([-8,-8,0], p=circle(d=50));
1138// shape2 = move([ 8, 8,0], p=circle(d=50));
1139// for (shape = [shape1,shape2]) color("red") stroke(shape, width=0.5, closed=true);
1140// color("green") region(intersection(shape1,shape2));
1141function intersection(regions=[],b=undef,c=undef,eps=EPSILON) =
1142 let(regions = _list_three(regions,b,c))
1143 len(regions)==0 ? []
1144 : len(regions)==1? regions[0]
1145 : regions[0]==[] || regions[1]==[] ? []
1146 : intersection([
1147 _filter_region_parts(regions[0],regions[1],["IS","I"],eps=eps),
1148 for (i=[2:1:len(regions)-1]) regions[i]
1149 ],
1150 eps=eps
1151 );
1152
1153
1154
1155// Function&Module: exclusive_or()
1156// Synopsis: Performs a Boolean exclusive-or operation.
1157// SynTags: Geom, Region
1158// Topics: Boolean Operations, Regions, Polygons, Shapes2D, Shapes3D
1159// See Also: union(), difference(), intersection(), diff(), intersect()
1160// Usage:
1161// exclusive_or() CHILDREN;
1162// region = exclusive_or(regions);
1163// region = exclusive_or(REGION1,REGION2);
1164// region = exclusive_or(REGION1,REGION2,REGION3);
1165// Description:
1166// When called as a function and given a list of regions or 2D polygons,
1167// returns the exclusive_or of all given regions. Result is a single region.
1168// When called as a module, performs a Boolean exclusive-or of up to 10 children. Note that when
1169// the input regions cross each other the exclusive-or operator will produce shapes that
1170// meet at corners (non-simple regions), which do not render in CGAL.
1171// Arguments:
1172// regions = List of regions or polygons to exclusive_or
1173// Example(2D): As Function. A linear_sweep of this shape fails to render in CGAL.
1174// shape1 = move([-8,-8,0], p=circle(d=50));
1175// shape2 = move([ 8, 8,0], p=circle(d=50));
1176// for (shape = [shape1,shape2])
1177// color("red") stroke(shape, width=0.5, closed=true);
1178// color("green") region(exclusive_or(shape1,shape2));
1179// Example(2D): As Module. A linear_extrude() of the resulting geometry fails to render in CGAL.
1180// exclusive_or() {
1181// square(40,center=false);
1182// circle(d=40);
1183// }
1184function exclusive_or(regions=[],b=undef,c=undef,eps=EPSILON) =
1185 let(regions = _list_three(regions,b,c))
1186 len(regions)==0? []
1187 : len(regions)==1? force_region(regions[0])
1188 : regions[0]==[] ? exclusive_or(list_tail(regions))
1189 : regions[1]==[] ? exclusive_or(list_remove(regions,1))
1190 : exclusive_or([
1191 _filter_region_parts(regions[0],regions[1],["IO","IO"],eps=eps),
1192 for (i=[2:1:len(regions)-1]) regions[i]
1193 ],
1194 eps=eps
1195 );
1196
1197
1198module exclusive_or() {
1199 if ($children==1) {
1200 children();
1201 } else if ($children==2) {
1202 difference() {
1203 children(0);
1204 children(1);
1205 }
1206 difference() {
1207 children(1);
1208 children(0);
1209 }
1210 } else if ($children==3) {
1211 exclusive_or() {
1212 exclusive_or() {
1213 children(0);
1214 children(1);
1215 }
1216 children(2);
1217 }
1218 } else if ($children==4) {
1219 exclusive_or() {
1220 exclusive_or() {
1221 children(0);
1222 children(1);
1223 }
1224 exclusive_or() {
1225 children(2);
1226 children(3);
1227 }
1228 }
1229 } else if ($children==5) {
1230 exclusive_or() {
1231 exclusive_or() {
1232 children(0);
1233 children(1);
1234 children(2);
1235 children(3);
1236 }
1237 children(4);
1238 }
1239 } else if ($children==6) {
1240 exclusive_or() {
1241 exclusive_or() {
1242 children(0);
1243 children(1);
1244 children(2);
1245 children(3);
1246 }
1247 children(4);
1248 children(5);
1249 }
1250 } else if ($children==7) {
1251 exclusive_or() {
1252 exclusive_or() {
1253 children(0);
1254 children(1);
1255 children(2);
1256 children(3);
1257 }
1258 children(4);
1259 children(5);
1260 children(6);
1261 }
1262 } else if ($children==8) {
1263 exclusive_or() {
1264 exclusive_or() {
1265 children(0);
1266 children(1);
1267 children(2);
1268 children(3);
1269 }
1270 exclusive_or() {
1271 children(4);
1272 children(5);
1273 children(6);
1274 children(7);
1275 }
1276 }
1277 } else if ($children==9) {
1278 exclusive_or() {
1279 exclusive_or() {
1280 children(0);
1281 children(1);
1282 children(2);
1283 children(3);
1284 }
1285 exclusive_or() {
1286 children(4);
1287 children(5);
1288 children(6);
1289 children(7);
1290 }
1291 children(8);
1292 }
1293 } else if ($children==10) {
1294 exclusive_or() {
1295 exclusive_or() {
1296 children(0);
1297 children(1);
1298 children(2);
1299 children(3);
1300 }
1301 exclusive_or() {
1302 children(4);
1303 children(5);
1304 children(6);
1305 children(7);
1306 }
1307 children(8);
1308 children(9);
1309 }
1310 } else {
1311 assert($children<=10, "exclusive_or() can only handle up to 10 children.");
1312 }
1313}
1314
1315
1316// vim: expandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap