src/2geom/shape.cpp

   1 #include "shape.h"
   2 #include "utils.h"
   3 #include "sweep.h"
   4 #include "ord.h"
   5
   6 #include <iostream>
   7 #include <algorithm>
   8 #include <cstdlib>
   9
  10 namespace Geom {
  11
  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 }
  17
  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 };
  24
  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 }
  36
  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 }
  49
  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 }
  54
  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;
  90
  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));
  95
  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;
 102
 103         Path res;
 104         do {
 105             Crossing cur = crs[i][j];
 106             visited[i][j] = true;
 107
 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;
 111
 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     }
 129
 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);
 134
 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);
 142
 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     }
 156
 157     return Shape(chunks, res_fill);
 158 }
 159
 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);
 163
 164     return shape_boolean(rev, a, b, crs);
 165 }
 166
 167
 168 // Some utility functions for boolop:
 169
 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 }
 177
 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 }
 181
 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 }
 185
 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 }
 225
 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 }
 262
 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 }
 269
 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 }
 276
 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 }
 281
 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 }
 287
 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 }
 316
 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 }
 339
 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 }
 349
 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 }
 375
 376 std::vector<Path> inner_sanitize(std::vector<Path> const & ps) {
 377     CrossingSet crs(crossings_among(ps));
 378
 379     Regions chunks;
 380
 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));
 385
 386     std::vector<Path> result_paths;
 387
 388     while(true) {
 389         unsigned ix = 0, jx = 0;
 390         bool dir = false;
 391
 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);
 408
 409         dir = !dir;
 410
 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;
 418
 419             bool new_dir = dir;
 420
 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);
 424
 425             //unsigned nix = ix, njx = jx;
 426             //crossing_dual(nix, njx, crs);
 427
 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]);
 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 }
 452
 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 }
 460
 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 }
 490
 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 }
 496
 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 }
 500
 501 Shape sanitize(std::vector<Path> const & ps) {
 502     CrossingSet crs = crossings_among(ps);
 503
 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));
 509
 510     Regions chunks;
 511     while(true) {
 512         unsigned i, j;
 513         first_false(visited, i, j);
 514         unsigned corner = corner_index(j);
 515
 516         if(i == visited.size()) break;
 517
 518         bool dir = corner_direction(i, j, corner, crs);
 519
 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;
 527
 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;
 535
 536             unsigned fix = i, fjx = j;
 537             crossing_dual(i, j, crs);
 538             visited[i][j*4+corner] = true;
 539             i = fix; j = fjx;
 540
 541             j = crossing_along(crs[i][j].getTime(i), i, j, dir, crs[i]);
 542
 543             crossing_dual(i, j, crs);
 544
 545             bool new_dir = dir;
 546             pick_coincident(i, j, cw, new_dir, ps, crs);
 547
 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 } */
 575
 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 }
 586
 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 }
 595
 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 }
 602
 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 }
 610
 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 }
 627
 628 bool Shape::invariants() const {
 629     return inside_invariants() && region_invariants() && cross_invariants();
 630 }
 631
 632 }
 633
 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 :