1 #include <2geom/shape.h>
2 #include <2geom/utils.h>
3 #include <2geom/sweep.h>
4 #include <2geom/ord.h>
6 #include <iostream>
7 #include <algorithm>
8 #include <cstdlib>
10 namespace Geom {
12 // A little sugar for appending a list to another
13 template<typename T>
14 void append(T &a, T const &b) {
15 a.insert(a.end(), b.begin(), b.end());
16 }
18 //Orders a list of indices according to their containment within eachother.
19 struct ContainmentOrder {
20 std::vector<Region> const *rs;
21 explicit ContainmentOrder(std::vector<Region> const *r) : rs(r) {}
22 bool operator()(unsigned a, unsigned b) const { return (*rs)[b].contains((*rs)[a]); }
23 };
25 //Returns the list of regions containing a particular point. Useful in tandem with ContainmentOrder
26 std::vector<unsigned> Shape::containment_list(Point p) const {
27 std::vector<Rect> pnt;
28 pnt.push_back(Rect(p, p));
29 std::vector<std::vector<unsigned> > cull = sweep_bounds(pnt, bounds(*this));
30 std::vector<unsigned> containers;
31 if(cull[0].size() == 0) return containers;
32 for(unsigned i = 0; i < cull[0].size(); i++)
33 if(content[cull[0][i]].contains(p)) containers.push_back(cull[0][i]);
34 return containers;
35 }
37 /* Used within shape_boolean and related functions, as the name describes, finds the
38 * first false within the list of lists of booleans.
39 */
40 void first_false(std::vector<std::vector<bool> > visited, unsigned &i, unsigned &j) {
41 for(i = 0, j = 0; i < visited.size(); i++) {
42 std::vector<bool>::iterator unvisited = std::find(visited[i].begin(), visited[i].end(), false);
43 if(unvisited != visited[i].end()) {
44 j = unvisited - visited[i].begin();
45 break;
46 }
47 }
48 }
50 // Finds a crossing in a list of them, given the sorting index.
51 unsigned find_crossing(Crossings const &cr, Crossing x, unsigned i) {
52 return std::lower_bound(cr.begin(), cr.end(), x, CrossingOrder(i)) - cr.begin();
53 }
55 /* This function handles boolean ops on shapes. The first parameter is a bool
56 * which determines its behavior in each combination of cases. For proper
57 * fill information and noncrossing behavior, the fill data of the regions
58 * must be correct. The boolean parameter determines whether the operation
59 * is a union or a subtraction. Reversed paths represent inverse regions,
60 * where everything is included in the fill except for the insides.
61 *
62 * Here is a chart of the behavior under various circumstances:
63 *
64 * rev = false (union)
65 * A
66 * F H
67 * F A+B -> F A-B -> H
68 *B
69 * H B-A -> H AxB -> H
70 *
71 * rev = true (intersect)
72 * A
73 * F H
74 * F AxB -> F B-A -> F
75 *B
76 * H A-B -> F A+B -> H
77 *
78 * F/H = Fill outer / Hole outer
79 * A/B specify operands
80 * + = union, - = subtraction, x = intersection
81 * -> read as "produces"
82 *
83 * This is the main function of boolops, yet its operation isn't very complicated.
84 * It traverses the crossings, and uses the crossing direction to decide whether
85 * the next segment should be taken from A or from B. The second half of the
86 * function deals with figuring out what to do with bits that have no intersection.
87 */
88 Shape shape_boolean(bool rev, Shape const & a, Shape const & b, CrossingSet const & crs) {
89 const Regions ac = a.content, bc = b.content;
91 //Keep track of which crossings we've hit.
92 std::vector<std::vector<bool> > visited;
93 for(unsigned i = 0; i < crs.size(); i++)
94 visited.push_back(std::vector<bool>(crs[i].size(), false));
96 //Traverse the crossings, creating chunks
97 Regions chunks;
98 while(true) {
99 unsigned i, j;
100 first_false(visited, i, j);
101 if(i == visited.size()) break;
103 Path res;
104 do {
105 Crossing cur = crs[i][j];
106 visited[i][j] = true;
108 //get indices of the dual:
109 unsigned io = cur.getOther(i), jo = find_crossing(crs[io], cur, io);
110 if(jo < visited[io].size()) visited[io][jo] = true;
112 //main driving logic
113 if(logical_xor(cur.dir, rev)) {
114 if(i >= ac.size()) { i = io; j = jo; }
115 j++;
116 if(j >= crs[i].size()) j = 0;
117 Crossing next = crs[i][j];
118 ac[next.a].boundary.appendPortionTo(res, cur.ta, next.ta);
119 } else {
120 if(i < ac.size()) { i = io; j = jo; }
121 j++;
122 if(j >= crs[i].size()) j = 0;
123 Crossing next = crs[i][j];
124 bc[next.b - ac.size()].boundary.appendPortionTo(res, cur.tb, next.tb);
125 }
126 } while (!visited[i][j]);
127 if(res.size() > 0) chunks.push_back(Region(res));
128 }
130 //If true, then we are on the 'subtraction diagonal'
131 bool const on_sub = logical_xor(a.fill, b.fill);
132 //If true, outer paths are filled
133 bool const res_fill = rev ? (on_sub || (a.fill && b.fill)) : (a.fill && b.fill);
135 //Handle unintersecting portions
136 for(unsigned i = 0; i < crs.size(); i++) {
137 if(crs[i].size() == 0) {
138 bool env;
139 bool on_a = i < ac.size();
140 Region const & r(on_a ? ac[i] : bc[i - ac.size()]);
141 Shape const & other(on_a ? b : a);
143 std::vector<unsigned> containers = other.containment_list(r.boundary.initialPoint());
144 if(containers.empty()) {
145 //not included in any container, the environment fill is the opposite of the outer fill
146 env = !res_fill;
147 if(on_sub && logical_xor(other.fill, res_fill)) env = !env; //If on the subtractor, invert the environment fill
148 } else {
149 //environment fill is the same as the inner-most container
150 std::vector<unsigned>::iterator cit = std::min_element(containers.begin(), containers.end(), ContainmentOrder(&other.content));
151 env = other[*cit].isFill();
152 }
153 if(!logical_xor(rev, env)) chunks.push_back(r); //When unioning, environment must be hole for inclusion, when intersecting, it must be filled
154 }
155 }
157 return Shape(chunks, res_fill);
158 }
160 // Just a convenience wrapper for shape_boolean, which handles the crossings
161 Shape shape_boolean(bool rev, Shape const & a, Shape const & b) {
162 CrossingSet crs = crossings_between(a, b);
164 return shape_boolean(rev, a, b, crs);
165 }
168 // Some utility functions for boolop:
170 std::vector<double> region_sizes(Shape const &a) {
171 std::vector<double> ret;
172 for(unsigned i = 0; i < a.size(); i++) {
173 ret.push_back(double(a[i].size()));
174 }
175 return ret;
176 }
178 Shape shape_boolean_ra(bool rev, Shape const &a, Shape const &b, CrossingSet const &crs) {
179 return shape_boolean(rev, a.inverse(), b, reverse_ta(crs, a.size(), region_sizes(a)));
180 }
182 Shape shape_boolean_rb(bool rev, Shape const &a, Shape const &b, CrossingSet const &crs) {
183 return shape_boolean(rev, a, b.inverse(), reverse_tb(crs, a.size(), region_sizes(b)));
184 }
186 /* This is a function based on shape_boolean which allows boolean operations
187 * to be specified as a logic table. This logic table is 4 bit-flags, which
188 * correspond to the elements of the 'truth table' for a particular operation.
189 * These flags are defined with the enums starting with BOOLOP_ .
190 *
191 * NOTE: currently doesn't work, as the CrossingSet reversal functions crash
192 */
193 Shape boolop(Shape const &a, Shape const &b, unsigned flags, CrossingSet const &crs) {
194 THROW_NOTIMPLEMENTED();
195 flags &= 15;
196 if(flags <= BOOLOP_UNION) {
197 switch(flags) {
198 case BOOLOP_INTERSECT: return shape_boolean(true, a, b, crs);
199 case BOOLOP_SUBTRACT_A_B: return shape_boolean_rb(true, a, b, crs);
200 case BOOLOP_IDENTITY_A: return a;
201 case BOOLOP_SUBTRACT_B_A: return shape_boolean_ra(true, a, b, crs);
202 case BOOLOP_IDENTITY_B: return b;
203 case BOOLOP_EXCLUSION: {
204 Shape res = shape_boolean_rb(true, a, b, crs);
205 append(res.content, shape_boolean_ra(true, a, b, crs).content);
206 return res;
207 }
208 case BOOLOP_UNION: return shape_boolean(false, a, b);
209 }
210 } else {
211 flags = ~flags & 15;
212 switch(flags - BOOLOP_NEITHER) {
213 case BOOLOP_SUBTRACT_A_B: return shape_boolean_ra(false, a, b, crs);
214 case BOOLOP_SUBTRACT_B_A: return shape_boolean_rb(false, a, b, crs);
215 case BOOLOP_EXCLUSION: {
216 Shape res = shape_boolean_ra(false, a, b, CrossingSet(crs));
217 append(res.content, shape_boolean_rb(false, a, b, CrossingSet(crs)).content);
218 return res;
219 }
220 }
221 return boolop(a, b, flags, crs).inverse();
222 }
223 return Shape();
224 }
226 /* This version of the boolop function doesn't require a set of crossings, as
227 * it computes them for you. This is more efficient in some cases, as the
228 * shape can be inverted before finding crossings. In the special case of
229 * exclusion it uses the other version of boolop.
230 */
231 Shape boolop(Shape const &a, Shape const &b, unsigned flags) {
232 flags &= 15;
233 if(flags <= BOOLOP_UNION) {
234 switch(flags) {
235 case BOOLOP_INTERSECT: return shape_boolean(true, a, b);
236 case BOOLOP_SUBTRACT_A_B: return shape_boolean(true, a, b.inverse());
237 case BOOLOP_IDENTITY_A: return a;
238 case BOOLOP_SUBTRACT_B_A: return shape_boolean(true, b, a.inverse());
239 case BOOLOP_IDENTITY_B: return b;
240 case BOOLOP_EXCLUSION: {
241 Shape res = shape_boolean(true, a, b.inverse());
242 append(res.content, shape_boolean(true, b, a.inverse()).content);
243 return res;
244 } //return boolop(a, b, flags, crossings_between(a, b));
245 case BOOLOP_UNION: return shape_boolean(false, a, b);
246 }
247 } else {
248 flags = ~flags & 15;
249 switch(flags) {
250 case BOOLOP_SUBTRACT_A_B: return shape_boolean(false, b, a.inverse());
251 case BOOLOP_SUBTRACT_B_A: return shape_boolean(false, a, b.inverse());
252 case BOOLOP_EXCLUSION: {
253 Shape res = shape_boolean(false, a, b.inverse());
254 append(res.content, shape_boolean(false, b, a.inverse()).content);
255 return res;
256 } //return boolop(a, b, flags, crossings_between(a, b));
257 }
258 return boolop(a, b, flags).inverse();
259 }
260 return Shape();
261 }
263 int paths_winding(std::vector<Path> const &ps, Point p) {
264 int ret = 0;
265 for(unsigned i = 0; i < ps.size(); i++)
266 ret += winding(ps[i], p);
267 return ret;
268 }
270 void add_to_shape(Shape &s, Path const &p, bool fill) {
271 if(fill)
272 s.content.push_back(Region(p).asFill());
273 else
274 s.content.push_back(Region(p).asHole());
275 }
277 int inner_winding(Path const & p, std::vector<Path> const &ps) {
278 Point pnt = p.initialPoint();
279 return paths_winding(ps, pnt) - winding(p, pnt) + 1;
280 }
282 double fudgerize(double d, bool rev) {
283 double ret = rev ? d - 0.01 : d + 0.01;
284 if(ret < 0) ret = 0;
285 return ret;
286 }
288 unsigned pick_coincident(unsigned ix, unsigned jx, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) {
289 unsigned ex_jx = jx;
290 unsigned oix = crs[ix][jx].getOther(ix);
291 double otime = crs[ix][jx].getTime(oix);
292 Point cross_point = ps[oix].pointAt(otime),
293 along = ps[oix].pointAt(fudgerize(otime, rev)) - cross_point,
294 prev = -along;
295 bool ex_dir = rev;
296 for(unsigned k = jx; k < crs[ix].size(); k++) {
297 unsigned koix = crs[ix][k].getOther(ix);
298 if(koix == oix) {
299 if(!are_near(otime, crs[ix][k].getTime(oix))) break;
300 for(unsigned dir = 0; dir < 2; dir++) {
301 Point val = ps[ix].pointAt(fudgerize(crs[ix][k].getTime(ix), dir)) - cross_point;
302 Cmp to_prev = cmp(cross(val, prev), 0);
303 Cmp from_along = cmp(cross(along, val), 0);
304 Cmp c = cmp(from_along, to_prev);
305 if(c == EQUAL_TO && from_along == LESS_THAN) {
306 ex_jx = k;
307 prev = val;
308 ex_dir = dir;
309 }
310 }
311 }
312 }
313 rev = ex_dir;
314 return ex_jx;
315 }
317 unsigned crossing_along(double t, unsigned ix, unsigned jx, bool dir, Crossings const & crs) {
318 Crossing cur = Crossing(t, t, ix, ix, false);
319 if(jx < crs.size()) {
320 double ct = crs[jx].getTime(ix);
321 if(t == ct) {
322 cur = crs[jx];
323 if(cur.a == cur.b) {
324 if(jx+1 <= crs.size() && crs[jx+1].getOther(ix) == ix) return jx+1;
325 if(jx > 0 && crs[jx-1].getOther(ix) == ix) return jx-1;
326 }
327 }
328 }
329 if(!dir) {
330 jx = std::upper_bound(crs.begin(), crs.end(), cur, CrossingOrder(ix)) - crs.begin();
331 } else {
332 jx = std::lower_bound(crs.begin(), crs.end(), cur, CrossingOrder(ix)) - crs.begin();
333 if(jx == 0) jx = crs.size() - 1; else jx--;
334 jx = std::lower_bound(crs.begin(), crs.end(), crs[jx], CrossingOrder(ix)) - crs.begin();
335 }
336 if(jx >= crs.size()) jx = 0;
337 return jx;
338 }
340 void crossing_dual(unsigned &i, unsigned &j, CrossingSet const & crs) {
341 Crossing cur = crs[i][j];
342 i = cur.getOther(i);
343 std::cout << i << "\n";
344 if(crs[i].empty())
345 j = 0;
346 else
347 j = std::lower_bound(crs[i].begin(), crs[i].end(), cur, CrossingOrder(i)) - crs[i].begin();
348 }
350 //locate a crossing on the outside, by casting a ray through the middle of the bbox
351 void outer_crossing(unsigned &ix, unsigned &jx, bool & dir, std::vector<Path> const & ps, CrossingSet const & crs) {
352 Rect bounds = *(ps[ix].boundsFast());
353 double ry = bounds[Y].middle();
354 double max_val = bounds.left(), max_t = 0;
355 ix = ps.size();
356 for(unsigned i = 0; i < ps.size(); i++) {
357 if(!crs[i].empty()) {
358 std::vector<double> rts = ps[i].roots(ry, Y);
359 for(unsigned j = 0; j < rts.size(); j++) {
360 double val = ps[i].valueAt(rts[j], X);
361 if(val > max_val) {
362 ix = i;
363 max_val = val;
364 max_t = rts[j];
365 }
366 }
367 }
368 }
369 if(ix != ps.size()) {
370 dir = ps[ix].valueAt(max_t + 0.01, Y) >
371 ps[ix].valueAt(max_t - 0.01, Y);
372 jx = crossing_along(max_t, ix, jx, dir, crs[ix]);
373 }
374 }
376 std::vector<Path> inner_sanitize(std::vector<Path> const & ps) {
377 CrossingSet crs(crossings_among(ps));
379 Regions chunks;
381 std::vector<bool> used_path(ps.size(), false);
382 std::vector<std::vector<bool> > visited;
383 for(unsigned i = 0; i < crs.size(); i++)
384 visited.push_back(std::vector<bool>(crs[i].size(), false));
386 std::vector<Path> result_paths;
388 while(true) {
389 unsigned ix = 0, jx = 0;
390 bool dir = false;
392 //find an outer crossing by trying various paths and checking if the crossings are used
393 for(; ix < crs.size(); ix++) {
394 //TODO: optimize so it doesn't unecessarily check stuff
395 bool cont = true;
396 for(unsigned j = 0; j < crs[ix].size(); j++) {
397 if(!visited[ix][j]) { cont = false; break; }
398 }
399 if(cont) continue;
400 unsigned rix = ix, rjx = jx;
401 outer_crossing(rix, rjx, dir, ps, crs);
402 if(rix >= crs.size() || visited[rix][rjx]) continue;
403 ix = rix; jx = rjx;
404 break;
405 }
406 if(ix == crs.size()) break;
407 crossing_dual(ix, jx, crs);
409 dir = !dir;
411 Path res;
412 do {
413 visited[ix][jx] = true;
414 //unsigned nix = ix, njx = jx;
415 //crossing_dual(nix, njx, crs);
416 //visited[nix][njx] = true;
417 unsigned fix = ix, fjx = jx;
419 bool new_dir = dir;
421 jx = crossing_along(crs[ix][jx].getTime(ix), ix, jx, dir, crs[ix]);
422 if(crs[ix][jx].a != crs[ix][jx].b) crossing_dual(ix, jx, crs); else new_dir = !new_dir;
423 jx = pick_coincident(ix, jx, new_dir, ps, crs);
425 //unsigned nix = ix, njx = jx;
426 //crossing_dual(nix, njx, crs);
428 Crossing from = crs[fix][fjx],
429 to = crs[ix][jx];
430 if(dir) {
431 // backwards
432 std::cout << "r" << ix << "[" << from.getTime(ix) << ", " << to.getTime(ix) << "]\n";
433 Path p = ps[ix].portion(from.getTime(ix), to.getTime(ix)).reverse();
434 for(unsigned i = 0; i < p.size(); i++)
435 res.append(p[i], Path::STITCH_DISCONTINUOUS);
436 } else {
437 // forwards
438 std::cout << "f" << ix << "[" << from.getTime(ix) << ", " << to.getTime(ix) << "]\n";
439 ps[ix].appendPortionTo(res, from.getTime(ix), to.getTime(ix));
440 }
441 dir = new_dir;
442 } while(!visited[ix][jx]);
443 std::cout << "added " << res.size() << "\n";
444 result_paths.push_back(res);
445 }
446 for(unsigned i = 0; i < crs.size(); i++) {
447 if(crs[i].empty() && !used_path[i])
448 result_paths.push_back(ps[i]);
449 }
450 return result_paths;
451 }
453 Shape sanitize(std::vector<Path> const & ps) {
454 std::vector<Path> res;
455 for(unsigned i = 0; i < ps.size(); i++) {
456 append(res, inner_sanitize(std::vector<Path>(1, ps[i])));
457 }
458 return stopgap_cleaner(res);
459 }
461 /* WIP sanitizer:
462 unsigned pick_coincident(unsigned ix, unsigned jx, bool pref, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) {
463 unsigned ex_jx = jx;
464 unsigned oix = crs[ix][jx].getOther(ix);
465 double otime = crs[ix][jx].getTime(oix);
466 Point cross_point = ps[oix].pointAt(otime),
467 along = ps[oix].pointAt(otime + (rev ? -0.01 : 0.01)) - cross_point,
468 prev = -along;
469 bool ex_dir = rev;
470 for(unsigned k = jx; k < crs[ix].size(); k++) {
471 unsigned koix = crs[ix][k].getOther(ix);
472 if(koix == oix) {
473 if(!are_near(otime, crs[ix][k].getTime(oix))) break;
474 for(unsigned dir = 0; dir < 2; dir++) {
475 Point val = ps[ix].pointAt(crs[ix][k].getTime(ix) + (dir ? -0.01 : 0.01)) - cross_point;
476 Cmp to_prev = cmp(cross(val, prev), 0);
477 Cmp from_along = cmp(cross(along, val), 0);
478 Cmp c = cmp(from_along, to_prev);
479 if(c == EQUAL_TO && (from_along == LESS_THAN) == pref) {
480 ex_jx = k;
481 prev = val;
482 ex_dir = dir;
483 }
484 }
485 }
486 }
487 rev = ex_dir;
488 return ex_jx;
489 }
491 unsigned corner_index(unsigned &i) {
492 div_t div_res = div(i, 4);
493 i = div_res.quot;
494 return div_res.rem;
495 }
497 bool corner_direction(unsigned ix, unsigned jc, unsigned corner, CrossingSet const &crs) {
498 if(crs[ix][jc].a == ix) return corner > 1; else return corner %2 == 1;
499 }
501 Shape sanitize(std::vector<Path> const & ps) {
502 CrossingSet crs = crossings_among(ps);
504 //Keep track of which CORNERS we've hit.
505 // FF FR RF RR, first is A dir, second B dir
506 std::vector<std::vector<bool> > visited;
507 for(unsigned i = 0; i < crs.size(); i++)
508 visited.push_back(std::vector<bool>(crs[i].size()*4, false));
510 Regions chunks;
511 while(true) {
512 unsigned i, j;
513 first_false(visited, i, j);
514 unsigned corner = corner_index(j);
516 if(i == visited.size()) break;
518 bool dir = corner_direction(i, j, corner, crs);
520 //Figure out whether we hug the path cw or ccw, based on the orientation of the initial corner:
521 unsigned oix = crs[i][j].getOther(i);
522 double otime = crs[i][j].getTime(oix);
523 bool odir = (oix == crs[i][j].a) ? corner > 1 : corner % 2 == 1;
524 Point cross_point = ps[oix].pointAt(otime),
525 along = ps[oix].pointAt(otime + (odir ? -0.01 : 0.01)) - cross_point,
526 val = ps[i].pointAt(crs[i][j].getTime(i) + (dir ? -0.01 : 0.01)) - cross_point;
528 Cmp from_along = cmp(cross(along, val), 0);
529 bool cw = from_along == LESS_THAN;
530 std::cout << "cw = " << cw << "\n";
531 Path res;
532 do {
533 Crossing cur = crs[i][j];
534 visited[i][j*4+corner] = true;
536 unsigned fix = i, fjx = j;
537 crossing_dual(i, j, crs);
538 visited[i][j*4+corner] = true;
539 i = fix; j = fjx;
541 j = crossing_along(crs[i][j].getTime(i), i, j, dir, crs[i]);
543 crossing_dual(i, j, crs);
545 bool new_dir = dir;
546 pick_coincident(i, j, cw, new_dir, ps, crs);
548 Crossing from = crs[fix][fjx],
549 to = crs[i][j];
550 if(dir) {
551 // backwards
552 std::cout << "r" << i << "[" << to.getTime(i) << ", " << from.getTime(i) << "]\n";
553 Path p = ps[i].portion(to.getTime(i) + 0.001, from.getTime(i)).reverse();
554 for(unsigned k = 0; k < p.size(); k++)
555 res.append(p[k]);
556 } else {
557 // forwards
558 std::cout << "f" << i << "[" << from.getTime(i) << ", " << to.getTime(i) << "]\n";
559 ps[i].appendPortionTo(res, from.getTime(i) + 0.001, to.getTime(i));
560 }
561 if(i == to.a)
562 corner = (new_dir ? 2 : 0) + (dir ? 1 : 0);
563 else
564 corner = (new_dir ? 1 : 0) + (dir ? 2 : 0);
565 dir = new_dir;
566 } while(!visited[i][j*4+corner]);
567 chunks.push_back(Region(res));
568 // if(use) {
569 // chunks.push_back(Region(res, true));
570 // }
571 }
572 return Shape(chunks);
573 // return ret;
574 } */
576 /* This transforms a shape by a matrix. In the case that the matrix flips
577 * the shape, it reverses the paths in order to preserve the fill.
578 */
579 Shape Shape::operator*(Matrix const &m) const {
580 Shape ret;
581 for(unsigned i = 0; i < size(); i++)
582 ret.content.push_back(content[i] * m);
583 ret.fill = fill;
584 return ret;
585 }
587 // Inverse is a boolean not, and simply reverses all the paths & fill flags
588 Shape Shape::inverse() const {
589 Shape ret;
590 for(unsigned i = 0; i < size(); i++)
591 ret.content.push_back(content[i].inverse());
592 ret.fill = !fill;
593 return ret;
594 }
596 bool Shape::contains(Point const &p) const {
597 std::vector<unsigned> containers = containment_list(p);
598 if(containers.empty()) return !isFill();
599 unsigned ix = *min_element(containers.begin(), containers.end(), ContainmentOrder(&content));
600 return content[ix].isFill();
601 }
603 Shape stopgap_cleaner(std::vector<Path> const &ps) {
604 if(ps.empty()) return Shape(false);
605 Shape ret;
606 for(unsigned i = 0; i < ps.size(); i++)
607 add_to_shape(ret, ps[i], inner_winding(ps[i], ps) % 2 != 0);
608 return ret;
609 }
611 bool Shape::inside_invariants() const { //semi-slow & easy to violate
612 for(unsigned i = 0; i < size(); i++)
613 if( logical_xor(content[i].isFill(), contains(content[i].boundary.initialPoint())) ) return false;
614 return true;
615 }
616 bool Shape::region_invariants() const { //semi-slow
617 for(unsigned i = 0; i < size(); i++)
618 if(!content[i].invariants()) return false;
619 return true;
620 }
621 bool Shape::cross_invariants() const { //slow
622 CrossingSet crs; // = crossings_among(paths_from_regions(content));
623 for(unsigned i = 0; i < crs.size(); i++)
624 if(!crs[i].empty()) return false;
625 return true;
626 }
628 bool Shape::invariants() const {
629 return inside_invariants() && region_invariants() && cross_invariants();
630 }
632 }
634 /*
635 Local Variables:
636 mode:c++
637 c-file-style:"stroustrup"
638 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
639 indent-tabs-mode:nil
640 fill-column:99
641 End:
642 */
643 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :