src/2geom/crossing.cpp

   1 #include <2geom/crossing.h>
   2 #include <2geom/path.h>
   3
   4 namespace Geom {
   5
   6 //bool edge_involved_in(Edge const &e, Crossing const &c) {
   7 //    if(e.path == c.a) {
   8 //        if(e.time == c.ta) return true;
   9 //    } else if(e.path == c.b) {
  10 //        if(e.time == c.tb) return true;
  11 //    }
  12 //    return false;
  13 //}
  14
  15 double wrap_dist(double from, double to, double size, bool rev) {
  16     if(rev) {
  17         if(to > from) {
  18             return from + (size - to);
  19         } else {
  20             return from - to;
  21         }
  22     } else {
  23         if(to < from) {
  24             return to + (size - from);
  25         } else {
  26             return to - from;
  27         }
  28     }
  29 }
  30 /*
  31 CrossingGraph create_crossing_graph(std::vector<Path> const &p, Crossings const &crs) {
  32     std::vector<Point> locs;
  33     CrossingGraph ret;
  34     for(unsigned i = 0; i < crs.size(); i++) {
  35         Point pnt = p[crs[i].a].pointAt(crs[i].ta);
  36         unsigned j = 0;
  37         for(; j < locs.size(); j++) {
  38             if(are_near(pnt, locs[j])) break;
  39         }
  40         if(j == locs.size()) {
  41             ret.push_back(CrossingNode());
  42             locs.push_back(pnt);
  43         }
  44         ret[j].add_edge(Edge(crs[i].a, crs[i].ta, false));
  45         ret[j].add_edge(Edge(crs[i].a, crs[i].ta, true));
  46         ret[j].add_edge(Edge(crs[i].b, crs[i].tb, false));
  47         ret[j].add_edge(Edge(crs[i].b, crs[i].tb, true));
  48     }
  49
  50     for(unsigned i = 0; i < ret.size(); i++) {
  51         for(unsigned j = 0; j < ret[i].edges.size(); j++) {
  52             unsigned pth = ret[i].edges[j].path;
  53             double t = ret[i].edges[j].time;
  54             bool rev = ret[i].edges[j].reverse;
  55             double size = p[pth].size()+1;
  56             double best = size;
  57             unsigned bix = ret.size();
  58             for(unsigned k = 0; k < ret.size(); k++) {
  59                 for(unsigned l = 0; l < ret[k].edges.size(); l++) {
  60                     if(ret[i].edges[j].path == ret[k].edges[l].path && (k != i || l != j)) {
  61                         double d = wrap_dist(t, ret[i].edges[j].time, size, rev);
  62                         if(d < best) {
  63                             best = d;
  64                             bix = k;
  65                         }
  66                     }
  67                 }
  68             }
  69             if(bix == ret.size()) {
  70                 std::cout << "couldn't find an adequate next-crossing node";
  71                 bix = i;
  72             }
  73             ret[i].edges[j].node = bix;
  74         }
  75     }
  76
  77     return ret;
  78  */
  79  /*  Various incoherent code bits
  80     // list of sets of edges, each set corresponding to those emanating from the path
  81     CrossingGraph ret;
  82     std::vector<Edge> edges(crs.size());
  83
  84     std::vector<std::vector<bool> > used;
  85     unsigned i, j;
  86     do {
  87         first_false(used, i, j);
  88         CrossingNode cn;
  89         do {
  90             unsigned di = i, dj = j;
  91             crossing_dual(di, dj);
  92             if(!used[di,dj]) {
  93
  94             }
  95         }
  96
  97     } while(!used[i,j])
  98
  99
 100     for(unsigned j = 0; j < crs[i].size(); j++) {
 101
 102         edges.push_back(Edge(i, crs[i][j].getOtherTime(i), false));
 103         edges.push_back(Edge(i, crs[i][j].getOtherTime(i), true));
 104     }
 105     std::sort(edges.begin(), edges.end(), TimeOrder());
 106     for(unsigned j = 0; j < edges.size(); ) {
 107         CrossingNode cn;
 108         double t = edges[j].time;
 109         while(j < edges.size() && are_near(edges[j].time, t)) {
 110             cn.edges.push_back(edges[j]);
 111         }
 112     }
 113 */
 114 //}
 115
 116 // provide specific method for Paths because paths can be closed or open. Path::size() is named somewhat wrong...
 117 std::vector<Rect> bounds(Path const &a) {
 118     std::vector<Rect> rs;
 119     for (unsigned i = 0; i < a.size_default(); i++) {
 120         OptRect bb = a[i].boundsFast();
 121         if (bb) {
 122             rs.push_back(*bb);
 123         }
 124     }
 125     return rs;
 126 }
 127
 128 void merge_crossings(Crossings &a, Crossings &b, unsigned i) {
 129     Crossings n;
 130     sort_crossings(b, i);
 131     n.resize(a.size() + b.size());
 132     std::merge(a.begin(), a.end(), b.begin(), b.end(), n.begin(), CrossingOrder(i));
 133     a = n;
 134 }
 135
 136 void offset_crossings(Crossings &cr, double a, double b) {
 137     for(unsigned i = 0; i < cr.size(); i++) {
 138         cr[i].ta += a;
 139         cr[i].tb += b;
 140     }
 141 }
 142
 143 Crossings reverse_ta(Crossings const &cr, std::vector<double> max) {
 144     Crossings ret;
 145     for(Crossings::const_iterator i = cr.begin(); i != cr.end(); ++i) {
 146         double mx = max[i->a];
 147         ret.push_back(Crossing(i->ta > mx+0.01 ? (1 - (i->ta - mx) + mx) : mx - i->ta,
 148                                i->tb, !i->dir));
 149     }
 150     return ret;
 151 }
 152
 153 Crossings reverse_tb(Crossings const &cr, unsigned split, std::vector<double> max) {
 154     Crossings ret;
 155     for(Crossings::const_iterator i = cr.begin(); i != cr.end(); ++i) {
 156         double mx = max[i->b - split];
 157         std::cout << i->b << "\n";
 158         ret.push_back(Crossing(i->ta, i->tb > mx+0.01 ? (1 - (i->tb - mx) + mx) : mx - i->tb,
 159                                !i->dir));
 160     }
 161     return ret;
 162 }
 163
 164 CrossingSet reverse_ta(CrossingSet const &cr, unsigned split, std::vector<double> max) {
 165     CrossingSet ret;
 166     for(unsigned i = 0; i < cr.size(); i++) {
 167         Crossings res = reverse_ta(cr[i], max);
 168         if(i < split) std::reverse(res.begin(), res.end());
 169         ret.push_back(res);
 170     }
 171     return ret;
 172 }
 173
 174 CrossingSet reverse_tb(CrossingSet const &cr, unsigned split, std::vector<double> max) {
 175     CrossingSet ret;
 176     for(unsigned i = 0; i < cr.size(); i++) {
 177         Crossings res = reverse_tb(cr[i], split, max);
 178         if(i >= split) std::reverse(res.begin(), res.end());
 179         ret.push_back(res);
 180     }
 181     return ret;
 182 }
 183
 184 void clean(Crossings &/*cr_a*/, Crossings &/*cr_b*/) {
 185 /*    if(cr_a.empty()) return;
 186
 187     //Remove anything with dupes
 188
 189     for(Eraser<Crossings> i(&cr_a); !i.ended(); i++) {
 190         const Crossing cur = *i;
 191         Eraser<Crossings> next(i);
 192         next++;
 193         if(are_near(cur, *next)) {
 194             cr_b.erase(std::find(cr_b.begin(), cr_b.end(), cur));
 195             for(i = next; near(*i, cur); i++) {
 196                 cr_b.erase(std::find(cr_b.begin(), cr_b.end(), *i));
 197             }
 198             continue;
 199         }
 200     }
 201 */
 202 }
 203
 204 }
 205
 206 /*
 207   Local Variables:
 208   mode:c++
 209   c-file-style:"stroustrup"
 210   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 211   indent-tabs-mode:nil
 212   fill-column:99
 213   End:
 214 */
 215 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :