| Line | Branch | Exec | Source |
|---|---|---|---|
| 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(PathVector 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(auto & i : cr) { | |
| 138 | ✗ | i.ta += a; | |
| 139 | ✗ | i.tb += b; | |
| 140 | } | ||
| 141 | ✗ | } | |
| 142 | |||
| 143 | ✗ | Crossings reverse_ta(Crossings const &cr, std::vector<double> max) { | |
| 144 | ✗ | Crossings ret; | |
| 145 | ✗ | for(const auto & i : cr) { | |
| 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(const auto & i : cr) { | |
| 156 | ✗ | double mx = max[i.b - split]; | |
| 157 | ✗ | ret.push_back(Crossing(i.ta, i.tb > mx+0.01 ? (1 - (i.tb - mx) + mx) : mx - i.tb, | |
| 158 | ✗ | !i.dir)); | |
| 159 | } | ||
| 160 | ✗ | return ret; | |
| 161 | ✗ | } | |
| 162 | |||
| 163 | ✗ | CrossingSet reverse_ta(CrossingSet const &cr, unsigned split, std::vector<double> max) { | |
| 164 | ✗ | CrossingSet ret; | |
| 165 | ✗ | for(unsigned i = 0; i < cr.size(); i++) { | |
| 166 | ✗ | Crossings res = reverse_ta(cr[i], max); | |
| 167 | ✗ | if(i < split) std::reverse(res.begin(), res.end()); | |
| 168 | ✗ | ret.push_back(res); | |
| 169 | ✗ | } | |
| 170 | ✗ | return ret; | |
| 171 | ✗ | } | |
| 172 | |||
| 173 | ✗ | CrossingSet reverse_tb(CrossingSet const &cr, unsigned split, std::vector<double> max) { | |
| 174 | ✗ | CrossingSet ret; | |
| 175 | ✗ | for(unsigned i = 0; i < cr.size(); i++) { | |
| 176 | ✗ | Crossings res = reverse_tb(cr[i], split, max); | |
| 177 | ✗ | if(i >= split) std::reverse(res.begin(), res.end()); | |
| 178 | ✗ | ret.push_back(res); | |
| 179 | ✗ | } | |
| 180 | ✗ | return ret; | |
| 181 | ✗ | } | |
| 182 | |||
| 183 | // Delete any duplicates in a vector of crossings | ||
| 184 | // 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 | ||
| 185 | // For example, duplicates will be found when calculating the intersections of a linesegment with a polygon, if the | ||
| 186 | // endpoint of that line coincides with a cusp node of the polygon. In that case, an intersection will be found of | ||
| 187 | // the linesegment with each of the polygon's linesegments extending from the cusp node (i.e. two intersections) | ||
| 188 | ✗ | void delete_duplicates(Crossings &crs) { | |
| 189 | ✗ | Crossings::reverse_iterator rit = crs.rbegin(); | |
| 190 | |||
| 191 | ✗ | for (rit = crs.rbegin(); rit!= crs.rend(); ++rit) { | |
| 192 | ✗ | Crossings::reverse_iterator rit2 = rit; | |
| 193 | ✗ | while (++rit2 != crs.rend()) { | |
| 194 | ✗ | if (Geom::are_near((*rit).ta, (*rit2).ta) && Geom::are_near((*rit).tb, (*rit2).tb)) { | |
| 195 | ✗ | crs.erase((rit + 1).base()); // This +1 and .base() construction is needed to convert to a regular iterator | |
| 196 | ✗ | break; // out of while loop, and continue with next iteration of for loop | |
| 197 | } | ||
| 198 | } | ||
| 199 | } | ||
| 200 | ✗ | } | |
| 201 | |||
| 202 | ✗ | void clean(Crossings &/*cr_a*/, Crossings &/*cr_b*/) { | |
| 203 | /* if(cr_a.empty()) return; | ||
| 204 | |||
| 205 | //Remove anything with dupes | ||
| 206 | |||
| 207 | for(Eraser<Crossings> i(&cr_a); !i.ended(); i++) { | ||
| 208 | const Crossing cur = *i; | ||
| 209 | Eraser<Crossings> next(i); | ||
| 210 | next++; | ||
| 211 | if(are_near(cur, *next)) { | ||
| 212 | cr_b.erase(std::find(cr_b.begin(), cr_b.end(), cur)); | ||
| 213 | for(i = next; near(*i, cur); i++) { | ||
| 214 | cr_b.erase(std::find(cr_b.begin(), cr_b.end(), *i)); | ||
| 215 | } | ||
| 216 | continue; | ||
| 217 | } | ||
| 218 | } | ||
| 219 | */ | ||
| 220 | ✗ | } | |
| 221 | |||
| 222 | } | ||
| 223 | |||
| 224 | /* | ||
| 225 | Local Variables: | ||
| 226 | mode:c++ | ||
| 227 | c-file-style:"stroustrup" | ||
| 228 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 229 | indent-tabs-mode:nil | ||
| 230 | fill-column:99 | ||
| 231 | End: | ||
| 232 | */ | ||
| 233 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 234 |