1 files changed, 233 insertions, 0 deletions
diff --git a/src/3rdparty/2geom/src/2geom/crossing.cpp b/src/3rdparty/2geom/src/2geom/crossing.cpp
new file mode 100644
index 0000000..1159fb0
--- /dev/null
+++ b/src/3rdparty/2geom/src/2geom/crossing.cpp
@@ -0,0 +1,233 @@
+#include <2geom/crossing.h>
+#include <2geom/path.h>
+
+namespace Geom {
+
+//bool edge_involved_in(Edge const &e, Crossing const &c) {
+//    if(e.path == c.a) {
+//        if(e.time == c.ta) return true;
+//    } else if(e.path == c.b) {
+//        if(e.time == c.tb) return true;
+//    }
+//    return false;
+//}
+
+double wrap_dist(double from, double to, double size, bool rev) {
+    if(rev) {
+        if(to > from) {
+            return from + (size - to);
+        } else {
+            return from - to;
+        }
+    } else {
+        if(to < from) {
+            return to + (size - from);
+        } else {
+            return to - from;
+        }
+    }
+}
+/*
+CrossingGraph create_crossing_graph(PathVector const &p, Crossings const &crs) {
+    std::vector<Point> locs;
+    CrossingGraph ret;
+    for(unsigned i = 0; i < crs.size(); i++) {
+        Point pnt = p[crs[i].a].pointAt(crs[i].ta);
+        unsigned j = 0;
+        for(; j < locs.size(); j++) {
+            if(are_near(pnt, locs[j])) break;
+        }
+        if(j == locs.size()) {
+            ret.push_back(CrossingNode());
+            locs.push_back(pnt);
+        }
+        ret[j].add_edge(Edge(crs[i].a, crs[i].ta, false));
+        ret[j].add_edge(Edge(crs[i].a, crs[i].ta, true));
+        ret[j].add_edge(Edge(crs[i].b, crs[i].tb, false));
+        ret[j].add_edge(Edge(crs[i].b, crs[i].tb, true));
+    }
+    
+    for(unsigned i = 0; i < ret.size(); i++) {
+        for(unsigned j = 0; j < ret[i].edges.size(); j++) {
+            unsigned pth = ret[i].edges[j].path;
+            double t = ret[i].edges[j].time;
+            bool rev = ret[i].edges[j].reverse;
+            double size = p[pth].size()+1;
+            double best = size;
+            unsigned bix = ret.size();
+            for(unsigned k = 0; k < ret.size(); k++) {
+                for(unsigned l = 0; l < ret[k].edges.size(); l++) {
+            	    if(ret[i].edges[j].path == ret[k].edges[l].path && (k != i || l != j)) {
+                        double d = wrap_dist(t, ret[i].edges[j].time, size, rev);
+                        if(d < best) {
+                            best = d;
+                            bix = k;
+                        }
+                    }
+                }
+            }
+            if(bix == ret.size()) {
+                std::cout << "couldn't find an adequate next-crossing node";
+                bix = i;
+            }
+            ret[i].edges[j].node = bix;
+        }
+    }
+    
+    return ret;
+ */
+ /*  Various incoherent code bits   
+    // list of sets of edges, each set corresponding to those emanating from the path
+    CrossingGraph ret;
+    std::vector<Edge> edges(crs.size());
+    
+    std::vector<std::vector<bool> > used;
+    unsigned i, j;
+    do {
+        first_false(used, i, j);
+        CrossingNode cn;
+        do {
+            unsigned di = i, dj = j;
+            crossing_dual(di, dj);
+            if(!used[di,dj]) {
+                
+            }
+        }
+        
+    } while(!used[i,j])
+    
+    
+    for(unsigned j = 0; j < crs[i].size(); j++) {
+        
+        edges.push_back(Edge(i, crs[i][j].getOtherTime(i), false));
+        edges.push_back(Edge(i, crs[i][j].getOtherTime(i), true));
+    }
+    std::sort(edges.begin(), edges.end(), TimeOrder());
+    for(unsigned j = 0; j < edges.size(); ) {
+        CrossingNode cn;
+        double t = edges[j].time;
+        while(j < edges.size() && are_near(edges[j].time, t)) {
+            cn.edges.push_back(edges[j]);
+        }
+    }
+*/
+//}
+
+// provide specific method for Paths because paths can be closed or open. Path::size() is named somewhat wrong...
+std::vector<Rect> bounds(Path const &a) {
+    std::vector<Rect> rs;
+    for (unsigned i = 0; i < a.size_default(); i++) {
+        OptRect bb = a[i].boundsFast();
+        if (bb) {
+            rs.push_back(*bb);
+        }
+    }
+    return rs;
+}
+
+void merge_crossings(Crossings &a, Crossings &b, unsigned i) {
+    Crossings n;
+    sort_crossings(b, i);
+    n.resize(a.size() + b.size());
+    std::merge(a.begin(), a.end(), b.begin(), b.end(), n.begin(), CrossingOrder(i));
+    a = n;
+}
+
+void offset_crossings(Crossings &cr, double a, double b) {
+    for(auto & i : cr) {
+        i.ta += a;
+        i.tb += b;
+    }
+}
+
+Crossings reverse_ta(Crossings const &cr, std::vector<double> max) {
+    Crossings ret;
+    for(const auto & i : cr) {
+        double mx = max[i.a];
+        ret.push_back(Crossing(i.ta > mx+0.01 ? (1 - (i.ta - mx) + mx) : mx - i.ta,
+                               i.tb, !i.dir));
+    }
+    return ret;
+}
+
+Crossings reverse_tb(Crossings const &cr, unsigned split, std::vector<double> max) {
+    Crossings ret;
+    for(const auto & i : cr) {
+        double mx = max[i.b - split];
+        ret.push_back(Crossing(i.ta, i.tb > mx+0.01 ? (1 - (i.tb - mx) + mx) : mx - i.tb,
+                               !i.dir));
+    }
+    return ret;
+}
+
+CrossingSet reverse_ta(CrossingSet const &cr, unsigned split, std::vector<double> max) {
+    CrossingSet ret;
+    for(unsigned i = 0; i < cr.size(); i++) {
+        Crossings res = reverse_ta(cr[i], max);
+        if(i < split) std::reverse(res.begin(), res.end());
+        ret.push_back(res);
+    }
+    return ret;
+}
+
+CrossingSet reverse_tb(CrossingSet const &cr, unsigned split, std::vector<double> max) {
+    CrossingSet ret;
+    for(unsigned i = 0; i < cr.size(); i++) {
+        Crossings res = reverse_tb(cr[i], split, max);
+        if(i >= split) std::reverse(res.begin(), res.end());
+        ret.push_back(res);
+    }
+    return ret;
+}
+
+// Delete any duplicates in a vector of crossings
+// A crossing is considered to be a duplicate when it has both t_a and t_b near to another crossing's t_a and t_b
+// For example, duplicates will be found when calculating the intersections of a linesegment with a polygon, if the
+// endpoint of that line coincides with a cusp node of the polygon. In that case, an intersection will be found of
+// the linesegment with each of the polygon's linesegments extending from the cusp node (i.e. two intersections)
+void delete_duplicates(Crossings &crs) {
+    Crossings::reverse_iterator rit = crs.rbegin();
+
+    for (rit = crs.rbegin(); rit!= crs.rend(); ++rit) {
+        Crossings::reverse_iterator rit2 = rit;
+        while (++rit2 != crs.rend()) {
+            if (Geom::are_near((*rit).ta, (*rit2).ta) && Geom::are_near((*rit).tb, (*rit2).tb)) {
+                crs.erase((rit + 1).base()); // This +1 and .base() construction is needed to convert to a regular iterator
+                break; // out of while loop, and continue with next iteration of for loop
+            }
+        }
+    }
+}
+
+void clean(Crossings &/*cr_a*/, Crossings &/*cr_b*/) {
+/*    if(cr_a.empty()) return;
+    
+    //Remove anything with dupes
+    
+    for(Eraser<Crossings> i(&cr_a); !i.ended(); i++) {
+        const Crossing cur = *i;
+        Eraser<Crossings> next(i);
+        next++;
+        if(are_near(cur, *next)) {
+            cr_b.erase(std::find(cr_b.begin(), cr_b.end(), cur));
+            for(i = next; near(*i, cur); i++) {
+                cr_b.erase(std::find(cr_b.begin(), cr_b.end(), *i));
+            }
+            continue;
+        }
+    }
+*/
+}
+
+}
+
+/*
+  Local Variables:
+  mode:c++
+  c-file-style:"stroustrup"
+  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
+  indent-tabs-mode:nil
+  fill-column:99
+  End:
+*/
+// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :