merge in 2geom rev. 1154

(bzr r3756)

1 files changed, 341 insertions, 151 deletions

diff --git a/src/2geom/shape.cpp b/src/2geom/shape.cpp
index 670792521..54218d4d9 100644
--- a/src/2geom/shape.cpp
+++ b/src/2geom/shape.cpp
@@ -1,23 +1,39 @@
 #include "shape.h"
 #include "utils.h"
 #include "sweep.h"
+#include "ord.h"
 
 #include <iostream>
 #include <algorithm>
+#include <cstdlib>
 
 namespace Geom {
 
-// Utility funcs
-
-// Yes, xor is !=, but I'm pretty sure this is safer in the event of strange bools
-bool logical_xor (bool a, bool b) { return (a || b) && !(a && b); }
-
 // A little sugar for appending a list to another
 template<typename T>
 void append(T &a, T const &b) {
     a.insert(a.end(), b.begin(), b.end());
 }
 
+//Orders a list of indices according to their containment within eachother.
+struct ContainmentOrder {
+    std::vector<Region> const *rs;
+    explicit ContainmentOrder(std::vector<Region> const *r) : rs(r) {}
+    bool operator()(unsigned a, unsigned b) const { return (*rs)[b].contains((*rs)[a]); }
+};
+
+//Returns the list of regions containing a particular point.  Useful in tandem with ContainmentOrder
+std::vector<unsigned> Shape::containment_list(Point p) const {
+    std::vector<Rect> pnt;
+    pnt.push_back(Rect(p, p));
+    std::vector<std::vector<unsigned> > cull = sweep_bounds(pnt, bounds(*this));
+    std::vector<unsigned> containers;
+    if(cull[0].size() == 0) return containers;
+    for(unsigned i = 0; i < cull[0].size(); i++)
+        if(content[cull[0][i]].contains(p)) containers.push_back(cull[0][i]);
+    return containers;
+}
+
 /* Used within shape_boolean and related functions, as the name describes, finds the
  * first false within the list of lists of booleans.
  */
@@ -77,8 +93,6 @@ Shape shape_boolean(bool rev, Shape const & a, Shape const & b, CrossingSet cons
     for(unsigned i = 0; i < crs.size(); i++)
         visited.push_back(std::vector<bool>(crs[i].size(), false));
     
-    //bool const exception = 
-    
     //Traverse the crossings, creating chunks
     Regions chunks;
     while(true) {
@@ -115,35 +129,32 @@ Shape shape_boolean(bool rev, Shape const & a, Shape const & b, CrossingSet cons
     
     //If true, then we are on the 'subtraction diagonal'
     bool const on_sub = logical_xor(a.fill, b.fill);
-    //If true, then the hole must be inside the other to be included
-    bool const a_mode = logical_xor(logical_xor(!rev, a.fill), on_sub),
-               b_mode = logical_xor(logical_xor(!rev, b.fill), on_sub);
+    //If true, outer paths are filled
+    bool const res_fill = rev ? (on_sub || (a.fill && b.fill)) : (a.fill && b.fill);
     
     //Handle unintersecting portions
     for(unsigned i = 0; i < crs.size(); i++) {
         if(crs[i].size() == 0) {
-            Region    r(i < ac.size() ? ac[i] : bc[i - ac.size()]);
-            bool   mode(i < ac.size() ? a_mode : b_mode);
+            bool env;
+            bool on_a = i < ac.size();
+            Region const & r(on_a ? ac[i] : bc[i - ac.size()]);
+            Shape const & other(on_a ? b : a);
             
-            if(logical_xor(r.fill, i < ac.size() ? a.fill : b.fill)) {
-                //is an inner (fill is opposite the outside fill)
-                Point exemplar = r.boundary.initialPoint();
-                Regions const & others = i < ac.size() ? bc : ac;
-                for(unsigned j = 0; j < others.size(); j++) {
-                    if(others[j].contains(exemplar)) {
-                        //contained in another
-                        if(mode) chunks.push_back(r);
-                        goto skip;
-                    }
-                }
+            std::vector<unsigned> containers = other.containment_list(r.boundary.initialPoint());
+            if(containers.empty()) {
+                //not included in any container, the environment fill is the opposite of the outer fill
+                env = !res_fill;
+                if(on_sub && logical_xor(other.fill, res_fill)) env = !env;  //If on the subtractor, invert the environment fill
+            } else {
+                //environment fill is the same as the inner-most container
+                std::vector<unsigned>::iterator cit = std::min_element(containers.begin(), containers.end(), ContainmentOrder(&other.content));
+                env = other[*cit].isFill();
             }
-            //disjoint
-            if(!mode) chunks.push_back(r);
-            skip: (void)0;
+            if(!logical_xor(rev, env)) chunks.push_back(r); //When unioning, environment must be hole for inclusion, when intersecting, it must be filled
         }
     }
     
-    return Shape(chunks);
+    return Shape(chunks, res_fill);
 }
 
 // Just a convenience wrapper for shape_boolean, which handles the crossings
@@ -176,8 +187,11 @@ Shape shape_boolean_rb(bool rev, Shape const &a, Shape const &b, CrossingSet con
  * to be specified as a logic table.  This logic table is 4 bit-flags, which
  * correspond to the elements of the 'truth table' for a particular operation.
  * These flags are defined with the enums starting with BOOLOP_ .
+ *
+ * NOTE: currently doesn't work, as the CrossingSet reversal functions crash
  */
 Shape boolop(Shape const &a, Shape const &b, unsigned flags, CrossingSet const &crs) {
+    throw NotImplemented();
     flags &= 15;
     if(flags <= BOOLOP_UNION) {
         switch(flags) {
@@ -194,6 +208,7 @@ Shape boolop(Shape const &a, Shape const &b, unsigned flags, CrossingSet const &
             case BOOLOP_UNION:        return shape_boolean(false, a, b);
         }
     } else {
+        flags = ~flags & 15;
         switch(flags - BOOLOP_NEITHER) {
             case BOOLOP_SUBTRACT_A_B: return shape_boolean_ra(false, a, b, crs);
             case BOOLOP_SUBTRACT_B_A: return shape_boolean_rb(false, a, b, crs);
@@ -203,7 +218,7 @@ Shape boolop(Shape const &a, Shape const &b, unsigned flags, CrossingSet const &
                 return res;
             }
         }
-        return boolop(a, b, ~flags, crs).inverse();
+        return boolop(a, b, flags, crs).inverse();
     }
     return Shape();
 }
@@ -230,7 +245,8 @@ Shape boolop(Shape const &a, Shape const &b, unsigned flags) {
             case BOOLOP_UNION:        return shape_boolean(false, a, b);
         }
     } else {
-        switch(flags - BOOLOP_NEITHER) {
+        flags = ~flags & 15;
+        switch(flags) {
             case BOOLOP_SUBTRACT_A_B: return shape_boolean(false, b, a.inverse());
             case BOOLOP_SUBTRACT_B_A: return shape_boolean(false, a, b.inverse());
             case BOOLOP_EXCLUSION: {
@@ -239,150 +255,323 @@ Shape boolop(Shape const &a, Shape const &b, unsigned flags) {
                 return res;
             } //return boolop(a, b, flags, crossings_between(a, b));
         }
-        return boolop(a, b, ~flags).inverse();
+        return boolop(a, b, flags).inverse();
     }
     return Shape();
 }
 
-
 int paths_winding(std::vector<Path> const &ps, Point p) {
-    int ret;
+    int ret = 0;
     for(unsigned i = 0; i < ps.size(); i++)
         ret += winding(ps[i], p);
     return ret;
 }
 
-std::vector<double> y_of_roots(std::vector<Path> const & ps, double x) {
-    std::vector<double> res;
-    for(unsigned i = 0; i < ps.size(); i++) {
-        std::vector<double> temp = ps[i].roots(x, X);
-        for(unsigned i = 0; i < temp.size(); i++)
-            res.push_back(ps[i].valueAt(temp[i], Y));
-    }
-    std::sort(res.begin(), res.end());
-    return res;
-}
-
-struct Edge {
-    unsigned ix;
-    double from, to;
-    bool rev;
-    int wind;
-    Edge(unsigned i, double ft, double tt, bool r, unsigned w) : ix(i), from(ft), to(tt), rev(r), wind(w) {}
-    Edge(unsigned i, double ft, double tt, bool r, std::vector<Path> const &ps) : ix(i), from(ft), to(tt), rev(r) {
-        //TODO: get the edge wind data some other way
-        Point p = ps[i].pointAt(ft);
-        std::vector<double> rs = y_of_roots(ps, p[X]);
-        unsigned interv = std::lower_bound(rs.begin(), rs.end(), p[Y]) - rs.begin();
-        wind = interv % 2;
+void add_to_shape(Shape &s, Path const &p, bool fill) {
+    if(fill)
+        s.content.push_back(Region(p).asFill());
+    else
+        s.content.push_back(Region(p).asHole());
+}
+
+int inner_winding(Path const & p, std::vector<Path> const &ps) {
+    Point pnt = p.initialPoint();
+    return paths_winding(ps, pnt) - winding(p, pnt) + 1;
+}
+
+double fudgerize(double d, bool rev) {
+    double ret = rev ? d - 0.01 : d + 0.01;
+    if(ret < 0) ret = 0;
+    return ret;
+}
+
+unsigned pick_coincident(unsigned ix, unsigned jx, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) {
+    unsigned ex_jx = jx;
+    unsigned oix = crs[ix][jx].getOther(ix);
+    double otime = crs[ix][jx].getTime(oix);
+    Point cross_point = ps[oix].pointAt(otime),
+          along = ps[oix].pointAt(fudgerize(otime, rev)) - cross_point,
+          prev = -along;
+    bool ex_dir = rev;
+    for(unsigned k = jx; k < crs[ix].size(); k++) {
+        unsigned koix = crs[ix][k].getOther(ix);
+        if(koix == oix) {
+            if(!near(otime, crs[ix][k].getTime(oix))) break;
+            for(unsigned dir = 0; dir < 2; dir++) {
+                Point val = ps[ix].pointAt(fudgerize(crs[ix][k].getTime(ix), dir)) - cross_point;
+                Cmp to_prev = cmp(cross(val, prev), 0);
+                Cmp from_along = cmp(cross(along, val), 0);
+                Cmp c = cmp(from_along, to_prev);
+                if(c == EQUAL_TO && from_along == LESS_THAN) {
+                    ex_jx = k;
+                    prev = val;
+                    ex_dir = dir;
+                }
+            }
+        }
     }
-    double initial() { return rev ? to : from; }
-    double final() { return rev ? from : to; }
-    void addTo(Path &res, std::vector<Path> const &ps) {
-        if(rev) {
-            Path p = ps[ix].portion(to, from).reverse();
-            for(unsigned i = 0; i < p.size(); i++)
-                res.append(p[i]);
-        } else {
-            ps[ix].appendPortionTo(res, from, to);
+    rev = ex_dir;
+    return ex_jx;
+}
+
+unsigned crossing_along(double t, unsigned ix, unsigned jx, bool dir, Crossings const & crs) {
+    Crossing cur = Crossing(t, t, ix, ix, false);
+    if(jx < crs.size()) {
+        double ct = crs[jx].getTime(ix);
+        if(t == ct) {
+            cur = crs[jx];
+            if(cur.a == cur.b) {
+                if(jx+1 <= crs.size() && crs[jx+1].getOther(ix) == ix) return jx+1;
+                if(jx > 0 && crs[jx-1].getOther(ix) == ix) return jx-1;
+            }
         }
     }
-};
+    if(!dir) {
+        jx = std::upper_bound(crs.begin(), crs.end(), cur, CrossingOrder(ix)) - crs.begin();
+    } else {
+        jx = std::lower_bound(crs.begin(), crs.end(), cur, CrossingOrder(ix)) - crs.begin();
+        if(jx == 0) jx = crs.size() - 1; else jx--;
+        jx = std::lower_bound(crs.begin(), crs.end(), crs[jx], CrossingOrder(ix)) - crs.begin();
+    }
+    if(jx >= crs.size()) jx = 0;
+    return jx;
+}
 
-typedef std::vector<Edge> Edges;
+void crossing_dual(unsigned &i, unsigned &j, CrossingSet const & crs) {
+    Crossing cur = crs[i][j];
+    i = cur.getOther(i);
+    std::cout << i << "\n";
+    if(crs[i].empty())
+        j = 0;
+    else
+        j = std::lower_bound(crs[i].begin(), crs[i].end(), cur, CrossingOrder(i)) - crs[i].begin();
+}
 
-double point_cosine(Point a, Point b, Point c) {
-    Point db = b - a, dc = c - a;
-    return cross(db, dc) / (db.length() * dc.length());
+//locate a crossing on the outside, by casting a ray through the middle of the bbox
+void outer_crossing(unsigned &ix, unsigned &jx, bool & dir, std::vector<Path> const & ps, CrossingSet const & crs) {
+    Rect bounds = ps[ix].boundsFast();
+    double ry = bounds[Y].middle();
+    double max_val = bounds.left(), max_t = 0;
+    ix = ps.size();
+    for(unsigned i = 0; i < ps.size(); i++) {
+        if(!crs[i].empty()) {
+            std::vector<double> rts = ps[i].roots(ry, Y);
+            for(unsigned j = 0; j < rts.size(); j++) {
+                double val = ps[i].valueAt(rts[j], X);
+                if(val > max_val) {
+                    ix = i;
+                    max_val = val;
+                    max_t = rts[j];
+                }
+            }
+        }
+    }
+    if(ix != ps.size()) {
+        dir = ps[ix].valueAt(max_t + 0.01, Y) >
+              ps[ix].valueAt(max_t - 0.01, Y);
+        jx = crossing_along(max_t, ix, jx, dir, crs[ix]);
+    }
 }
 
-//sanitize
-Regions regionize_paths(std::vector<Path> const &ps, bool evenodd) {
-    CrossingSet crs = crossings_among(ps);
+std::vector<Path> inner_sanitize(std::vector<Path> const & ps) {
+    CrossingSet crs(crossings_among(ps));
     
-    Edges es;
+    Regions chunks;
     
-    for(unsigned i = 0; i < crs.size(); i++) {
-        for(unsigned j = 0; j < crs[i].size(); j++) {
-            Crossing cur = crs[i][j];
-            int io = i, jo = j;
+    std::vector<bool> used_path(ps.size(), false);
+    std::vector<std::vector<bool> > visited;
+    for(unsigned i = 0; i < crs.size(); i++)
+        visited.push_back(std::vector<bool>(crs[i].size(), false));
+    
+    std::vector<Path> result_paths;
+    
+    while(true) {
+        unsigned ix = 0, jx = 0;
+        bool dir = false;
+
+        //find an outer crossing by trying various paths and checking if the crossings are used
+        for(; ix < crs.size(); ix++) {
+            //TODO: optimize so it doesn't unecessarily check stuff
+            bool cont = true;
+            for(unsigned j = 0; j < crs[ix].size(); j++) {
+                if(!visited[ix][j]) { cont = false; break; }
+            }
+            if(cont) continue;
+            unsigned rix = ix, rjx = jx;
+            outer_crossing(rix, rjx, dir, ps, crs);
+            if(rix >= crs.size() || visited[rix][rjx]) continue;
+            ix = rix; jx = rjx;
+            break;
+        }
+        if(ix == crs.size()) break;
+        crossing_dual(ix, jx, crs);
+
+        dir = !dir;
+
+        Path res;
+        do {
+            visited[ix][jx] = true;
+            //unsigned nix = ix, njx = jx;
+            //crossing_dual(nix, njx, crs);
+            //visited[nix][njx] = true;
+            unsigned fix = ix, fjx = jx;
             
-            jo++;
-            if(jo >= crs[io].size()) jo = 0;
-            //std::cout << io << ", " << jo << "\n";
-            if(cur.a == i)
-                es.push_back(Edge(i, cur.ta, crs[io][jo].ta, false, ps));
-            else
-                es.push_back(Edge(i, cur.tb, crs[io][jo].tb, false, ps));
+            bool new_dir = dir;
             
-            jo-=2;
-            if(jo < 0) jo += crs[io].size();
-            // std::cout << io << ", " << jo << "\n";
-            if(cur.a == i)
-                es.push_back(Edge(i, crs[io][jo].ta, cur.ta, true, ps));
-            else
-                es.push_back(Edge(i, crs[io][jo].tb, cur.tb, true, ps));
-        }
+            jx = crossing_along(crs[ix][jx].getTime(ix), ix, jx, dir, crs[ix]);
+            if(crs[ix][jx].a != crs[ix][jx].b) crossing_dual(ix, jx, crs); else new_dir = !new_dir;
+            jx = pick_coincident(ix, jx, new_dir, ps, crs);
+            
+            //unsigned nix = ix, njx = jx;
+            //crossing_dual(nix, njx, crs);
+            
+            Crossing from = crs[fix][fjx],
+                     to = crs[ix][jx];
+            if(dir) {
+                // backwards
+                std::cout << "r" << ix << "[" << from.getTime(ix)  << ", " << to.getTime(ix) << "]\n";
+                Path p = ps[ix].portion(from.getTime(ix), to.getTime(ix)).reverse();
+                for(unsigned i = 0; i < p.size(); i++)
+                    res.append(p[i]);
+            } else {
+                // forwards
+                std::cout << "f" << ix << "[" << from.getTime(ix) << ", " << to.getTime(ix) << "]\n";
+                ps[ix].appendPortionTo(res, from.getTime(ix), to.getTime(ix));
+            }
+            dir = new_dir;
+        } while(!visited[ix][jx]);
+        std::cout << "added " << res.size() << "\n";
+        result_paths.push_back(res);
     }
-    for(unsigned i = 0; i<crs.size(); i++) {
-        if(crs[i].empty()) {
-            es.push_back(Edge(i, 0, ps[i].size(), false, ps));
-            es.push_back(Edge(i, ps[i].size(), 0, true, ps));
-        }
+    for(unsigned i = 0; i < crs.size(); i++) {
+        if(crs[i].empty() && !used_path[i])
+            result_paths.push_back(ps[i]);
     }
-    
-    Edges es2;
-    //filter
-    for(unsigned i = 0; i < es.size(); i++) {
-        if(true) //(evenodd && es[i].wind % 2 == 0) || (!evenodd && es[i].wind == 0))
-            es2.push_back(es[i]);
+    return result_paths;
+}
+
+Shape sanitize(std::vector<Path> const & ps) {
+    std::vector<Path> res;
+    for(unsigned i = 0; i < ps.size(); i++) {
+        append(res, inner_sanitize(std::vector<Path>(1, ps[i])));
+    }
+    return stopgap_cleaner(res);
+}
+
+/*  WIP sanitizer:
+unsigned pick_coincident(unsigned ix, unsigned jx, bool pref, bool &rev, std::vector<Path> const &ps, CrossingSet const &crs) {
+    unsigned ex_jx = jx;
+    unsigned oix = crs[ix][jx].getOther(ix);
+    double otime = crs[ix][jx].getTime(oix);
+    Point cross_point = ps[oix].pointAt(otime),
+          along = ps[oix].pointAt(otime + (rev ? -0.01 : 0.01)) - cross_point,
+          prev = -along;
+    bool ex_dir = rev;
+    for(unsigned k = jx; k < crs[ix].size(); k++) {
+        unsigned koix = crs[ix][k].getOther(ix);
+        if(koix == oix) {
+            if(!near(otime, crs[ix][k].getTime(oix))) break;
+            for(unsigned dir = 0; dir < 2; dir++) {
+                Point val = ps[ix].pointAt(crs[ix][k].getTime(ix) + (dir ? -0.01 : 0.01)) - cross_point;
+                Cmp to_prev = cmp(cross(val, prev), 0);
+                Cmp from_along = cmp(cross(along, val), 0);
+                Cmp c = cmp(from_along, to_prev);
+                if(c == EQUAL_TO && (from_along == LESS_THAN) == pref) {
+                    ex_jx = k;
+                    prev = val;
+                    ex_dir = dir;
+                }
+            }
+        }
     }
-    es = es2;
+    rev = ex_dir;
+    return ex_jx;
+}
+
+unsigned corner_index(unsigned &i) {
+    div_t div_res = div(i, 4);
+    i = div_res.quot;
+    return div_res.rem;
+}
+
+bool corner_direction(unsigned ix, unsigned jc, unsigned corner, CrossingSet const &crs) {
+    if(crs[ix][jc].a == ix) return corner > 1; else return corner %2 == 1;
+}
+
+Shape sanitize(std::vector<Path> const & ps) {
+    CrossingSet crs = crossings_among(ps);
     
-    std::cout << es.size() << " edges\n";
+    //Keep track of which CORNERS we've hit.
+    // FF FR RF RR, first is A dir, second B dir
+    std::vector<std::vector<bool> > visited;
+    for(unsigned i = 0; i < crs.size(); i++)
+        visited.push_back(std::vector<bool>(crs[i].size()*4, false));
     
     Regions chunks;
-    for(unsigned i = 0; i < es.size(); i++) {
-        Edge cur = es[i];
-        if(cur.rev)
-            chunks.push_back(Region(ps[cur.ix].portion(cur.from, cur.to).reverse(), cur.wind % 2 != 0));
-        else
-            chunks.push_back(Region(ps[cur.ix].portion(cur.from, cur.to), cur.wind % 2 != 0));
-    }
-    return chunks;
-    
-    //Regions chunks;
-    std::vector<bool> used(es2.size(), false);
     while(true) {
-        unsigned i = std::find(used.begin(), used.end(), false) - used.begin();
-        if(i == used.size()) break;
+        unsigned i, j;
+        first_false(visited, i, j);
+        unsigned corner = corner_index(j);
+        
+        if(i == visited.size()) break;
+        
+        bool dir = corner_direction(i, j, corner, crs);
+        
+        //Figure out whether we hug the path cw or ccw, based on the orientation of the initial corner:        
+        unsigned oix = crs[i][j].getOther(i);
+        double otime = crs[i][j].getTime(oix);
+        bool odir = (oix == crs[i][j].a) ? corner > 1 : corner % 2 == 1;
+        Point cross_point = ps[oix].pointAt(otime),
+              along = ps[oix].pointAt(otime + (odir ? -0.01 : 0.01)) - cross_point,
+                val = ps[i].pointAt(crs[i][j].getTime(i) + (dir ? -0.01 : 0.01)) - cross_point;
+        
+        Cmp from_along = cmp(cross(along, val), 0);
+        bool cw = from_along == LESS_THAN;
+        std::cout << "cw = " << cw << "\n";
         Path res;
         do {
-            es2[i].addTo(res, ps);
-            Point pnt = res.finalPoint();
-            std::vector<unsigned> poss;
-            for(unsigned j = 0; j < es2.size(); j++)
-                if(near(pnt, ps[es2[j].ix].pointAt(es2[j].initial()))) poss.push_back(j);
-            if(poss.empty()) break;
-            unsigned best = 0;
-            if(poss.size() > 1) {
-                double crossval = 10;
-                Point along = ps[i].pointAt(es2[i].final()+0.1);
-                for(unsigned j = 0; j < poss.size(); j++) {
-                    unsigned ix = poss[j];
-                    double val = point_cosine(pnt, along, ps[ix].pointAt(es2[ix].initial()+.01));
-                    if(val < crossval) {
-                        crossval = val;
-                        best = j;
-                    }
-                }
+            Crossing cur = crs[i][j];
+            visited[i][j*4+corner] = true;
+            
+            unsigned fix = i, fjx = j;
+            crossing_dual(i, j, crs);
+            visited[i][j*4+corner] = true;
+            i = fix; j = fjx;
+            
+            j = crossing_along(crs[i][j].getTime(i), i, j, dir, crs[i]);
+            
+            crossing_dual(i, j, crs);
+            
+            bool new_dir = dir;
+            pick_coincident(i, j, cw, new_dir, ps, crs);
+            
+            Crossing from = crs[fix][fjx],
+                     to = crs[i][j];
+            if(dir) {
+                // backwards
+                std::cout << "r" << i << "[" << to.getTime(i)  << ", " << from.getTime(i) << "]\n";
+                Path p = ps[i].portion(to.getTime(i) + 0.001, from.getTime(i)).reverse();
+                for(unsigned k = 0; k < p.size(); k++)
+                    res.append(p[k]);
+            } else {
+                // forwards
+                std::cout << "f" << i << "[" << from.getTime(i) << ", " << to.getTime(i) << "]\n";
+                ps[i].appendPortionTo(res, from.getTime(i) + 0.001, to.getTime(i));
             }
-            i = poss[best];
-        } while(!used[i]);
+            if(i == to.a)
+                corner = (new_dir ? 2 : 0) + (dir ? 1 : 0);
+            else
+                corner = (new_dir ? 1 : 0) + (dir ? 2 : 0);
+            dir = new_dir;
+        } while(!visited[i][j*4+corner]);
         chunks.push_back(Region(res));
+//        if(use) {
+//            chunks.push_back(Region(res, true));
+//        }
     }
-    return chunks;
-}
+    return Shape(chunks);
+//    return ret;
+} */
 
 /* This transforms a shape by a matrix.  In the case that the matrix flips
  * the shape, it reverses the paths in order to preserve the fill.
@@ -404,18 +593,19 @@ Shape Shape::inverse() const {
     return ret;
 }
 
-struct ContainmentOrder {
-    std::vector<Region> const *rs;
-    explicit ContainmentOrder(std::vector<Region> const *r) : rs(r) {}
-    bool operator()(unsigned a, unsigned b) const { return (*rs)[b].contains((*rs)[a]); }
-};
-
 bool Shape::contains(Point const &p) const {
-    std::vector<Rect> pnt;
-    pnt.push_back(Rect(p, p));
-    std::vector<std::vector<unsigned> > cull = sweep_bounds(pnt, bounds(*this));
-    if(cull[0].size() == 0) return !fill;
-    return content[*min_element(cull[0].begin(), cull[0].end(), ContainmentOrder(&content))].isFill();
+    std::vector<unsigned> containers = containment_list(p);
+    if(containers.empty()) return !isFill();
+    unsigned ix = *min_element(containers.begin(), containers.end(), ContainmentOrder(&content));
+    return content[ix].isFill();
+}
+
+Shape stopgap_cleaner(std::vector<Path> const &ps) {
+    if(ps.empty()) return Shape(false);
+    Shape ret;
+    for(unsigned i = 0; i < ps.size(); i++)
+        add_to_shape(ret, ps[i], inner_winding(ps[i], ps) % 2 != 0);
+    return ret;
 }
 
 bool Shape::inside_invariants() const {  //semi-slow & easy to violate