1
#include <2geom/toposweep.h>
3
#include <2geom/path-intersection.h>
4
#include <2geom/basic-intersection.h>
6
//using namespace Geom;
10
TopoGraph::Edge &TopoGraph::Vertex::operator[](unsigned ix) {
12
return ix < enters.size() ? enters[ix] : exits[ix - enters.size()];
15
TopoGraph::Edge TopoGraph::Vertex::operator[](unsigned ix) const {
17
return ix < enters.size() ? enters[ix] : exits[ix - enters.size()];
20
void TopoGraph::Vertex::erase(unsigned ix) {
22
if(ix < enters.size())
23
enters.erase(enters.begin() + ix);
25
exits.erase(exits.begin() + (ix - enters.size()));
28
void TopoGraph::Vertex::insert(unsigned ix, Edge v) {
30
if(ix < enters.size())
31
enters.insert(enters.begin() + ix, v);
33
exits.insert(exits.begin() + (ix - enters.size()), v);
36
unsigned TopoGraph::Vertex::find_section(boost::shared_ptr<Section> section) const {
38
for(; i < degree(); i++)
39
if((*this)[i].section == section) return i;
43
TopoGraph::Edge TopoGraph::remove_edge(unsigned ix, unsigned jx) {
44
Vertex &v = vertices[ix];
49
v = vertices[ret.other];
51
v.erase(v.find_section(ret.section));
58
void TopoGraph::cannonize() {
59
std::vector<unsigned> vix;
61
for(unsigned i = 0; i < vertices.size(); i++) {
63
if(vertices[i].degree() != 0) vertices[ix++] = vertices[i];
66
for(unsigned i = 0; i < ix; i++)
67
for(unsigned j = 0; j < vertices[i].degree(); j++)
68
vertices[i][j].other = vix[vertices[i][j].other];
72
void TopoGraph::assert_invariants() const {
73
for(unsigned i = 0; i < vertices.size(); i++) {
74
for(unsigned j = 0; j < vertices[i].degree(); j++) {
75
Edge e = vertices[i][j];
77
assert(are_near(e.section->fp, vertices[i].avg, tol) || are_near(e.section->tp, vertices[i].avg, tol));
78
assert(!are_near(e.section->fp, e.section->tp, tol));
79
assert(e.section.get());
80
unsigned oix = vertices[e.other].find_section(e.section);
81
assert(oix != vertices[e.other].degree());
86
//near predicate utilized in process_splits
88
struct NearPredicate { bool operator()(T x, T y) { return are_near(x, y); } };
90
// ensures that f and t are elements of a vector, sorts and uniqueifies
91
// also asserts that no values fall outside of f and t
92
// if f is greater than t, the sort is in reverse
93
void process_splits(std::vector<double> &splits, double f, double t) {
95
std::sort(splits.begin(), splits.end());
96
while(are_near(splits.back(), t)) splits.erase(splits.end() - 1);
98
if(f > t) std::reverse(splits.begin(), splits.end());
100
//remove any splits which fall outside t / f
101
while(!splits.empty() && splits.front() != f) splits.erase(splits.begin());
102
while(!splits.empty() && splits.back() != t) splits.erase(splits.end() - 1);
104
std::vector<double>::iterator end = std::unique(splits.begin(), splits.end(), NearPredicate<double>());
105
splits.resize(end - splits.begin());
108
// A little sugar for appending a list to another
110
void concatenate(T &a, T const &b) { a.insert(a.end(), b.begin(), b.end()); }
112
//returns a list of monotonic sections of a path
113
//TODO: handle saddle points
114
std::vector<boost::shared_ptr<Section> > mono_sections(PathVector const &ps, Dim2 d) {
115
std::vector<boost::shared_ptr<Section> > monos;
116
for(unsigned i = 0; i < ps.size(); i++) {
117
//TODO: necessary? can we have empty paths?
119
for(unsigned j = 0; j < ps[i].size(); j++) {
120
//find the points of 0 derivative
121
Curve* deriv = ps[i][j].derivative();
122
std::vector<double> splits = deriv->roots(0, X);
123
concatenate(splits, deriv->roots(0, Y));
125
process_splits(splits, 0, 1);
126
//split on points of 0 derivative
127
for(unsigned k = 1; k < splits.size(); k++)
128
monos.push_back(boost::shared_ptr<Section>(new Section(CurveIx(i,j), splits[k-1], splits[k], ps, d)));
135
//finds the t-value on a section, which corresponds to a particular horizontal or vertical line
136
//d indicates the dimension along which the roots is performed.
137
//-1 is returned if no root is found
138
double section_root(Section const &s, PathVector const &ps, double v, Dim2 d) {
139
std::vector<double> roots = s.curve.get(ps).roots(v, d);
140
for(unsigned j = 0; j < roots.size(); j++)
141
if(Interval(s.f, s.t).contains(roots[j])) return roots[j];
145
bool SectionSorter::section_order(Section const &a, double at, Section const &b, double bt) const {
146
Point ap = a.curve.get(ps).pointAt(at);
147
Point bp = b.curve.get(ps).pointAt(bt);
148
if(are_near(ap[dim], bp[dim], tol)) {
149
// since the sections are monotonic, if the endpoints are on opposite sides of this
150
// coincidence, the order is determinable
151
if(a.tp[dim] < ap[dim] && b.tp[dim] > bp[dim]) return true;
152
if(a.tp[dim] > ap[dim] && b.tp[dim] < bp[dim]) return false;
153
//TODO: sampling / higher derivatives when unit tangents match
154
Point ad = a.curve.get(ps).unitTangentAt(a.f);
155
Point bd = b.curve.get(ps).unitTangentAt(b.f);
156
// tangent can point backwards
157
if(ad[1-dim] < 0) ad = -ad;
158
if(bd[1-dim] < 0) bd = -bd;
159
return ad[dim] < bd[dim];
161
return ap[dim] < bp[dim];
164
bool SectionSorter::operator()(Section const &a, Section const &b) const {
165
if(&a == &b) return false;
166
Rect ra = a.bbox(), rb = b.bbox();
167
//TODO: should we use tol in these conditions?
168
if(ra[dim].max() <= rb[dim].min()) return true;
169
if(rb[dim].max() <= ra[dim].min()) return false;
170
//we know that the rects intersect on dim
171
//by referencing f / t we are assuming that the section was constructed with 1-dim
172
if(ra[1-dim].intersects(rb[1-dim])) {
173
if(are_near(a.fp[1-dim], b.fp[1-dim], tol)) {
174
return section_order(a, a.f > a.t ? a.f - 0.01 : a.f + 0.01,
175
b, b.f > b.t ? b.f - 0.01 : b.f + 0.01);
176
} else if(a.fp[1-dim] < b.fp[1-dim]) {
178
double ta = section_root(a, ps, b.fp[1-dim], Dim2(1-dim));
179
//TODO: fix bug that necessitates this
180
if(ta == -1) ta = (a.t + a.f) / 2;
181
return section_order(a, ta, b, b.f);
184
double tb = section_root(b, ps, a.fp[1-dim], Dim2(1-dim));
185
//TODO: fix bug that necessitates this
186
if(tb == -1) tb = (b.t + b.f) / 2;
187
return section_order(a, a.f, b, tb);
191
return Point::LexOrderRt(dim)(a.fp, b.fp);
194
// splits a section into pieces, as specified by an array of doubles, mutating the section to
195
// represent the first part, and returning the rest
196
//TODO: output iterator?
197
std::vector<boost::shared_ptr<Section> > split_section(boost::shared_ptr<Section> s, PathVector const &ps, std::vector<double> &cuts, Dim2 d) {
198
std::vector<boost::shared_ptr<Section> > ret;
200
process_splits(cuts, s->f, s->t);
201
if(cuts.size() <= 2) return ret;
204
s->tp = s->curve.get(ps)(cuts[1]);
205
assert(Point::LexOrderRt(d)(s->fp, s->tp));
207
ret.reserve(cuts.size() - 2);
208
for(int i = cuts.size() - 1; i > 1; i--) ret.push_back(boost::shared_ptr<Section>(new Section(s->curve, cuts[i-1], cuts[i], ps, d)));
212
//merges the sorted lists a and b according to comparison z
213
template<typename X, typename Z>
214
void merge(X &a, X const &b, Z const &z) {
215
a.reserve(a.size() + b.size());
216
unsigned start = a.size();
218
std::inplace_merge(a.begin(), a.begin() + start, a.end(), z);
221
//TODO: faster than linear
222
unsigned find_vertex(std::vector<TopoGraph::Vertex> const &vertices, Point p, double tol) {
223
for(unsigned i = 0; i < vertices.size(); i++)
224
if(are_near(vertices[i].avg, p, tol)) return i;
225
return vertices.size();
228
//takes a vector of T pointers, and returns a vector of T with copies
230
std::vector<T> deref_vector(std::vector<boost::shared_ptr<T> > const &xs, unsigned from = 0) {
232
ret.reserve(xs.size() - from);
233
for(unsigned i = from; i < xs.size(); i++)
234
ret.push_back(T(*xs[i]));
238
//used to create reversed sorting predicates
240
struct ReverseAdapter {
241
typedef typename C::second_argument_type first_argument_type;
242
typedef typename C::first_argument_type second_argument_type;
243
typedef typename C::result_type result_type;
245
ReverseAdapter(const C &c) : comp(c) {}
246
result_type operator()(const first_argument_type &a, const second_argument_type &b) const { return comp(b, a); }
249
//used to sort std::vector<Section*>
251
struct DerefAdapter {
252
typedef typename boost::shared_ptr<typename C::first_argument_type> first_argument_type;
253
typedef typename boost::shared_ptr<typename C::second_argument_type> second_argument_type;
254
typedef typename C::result_type result_type;
256
DerefAdapter(const C &c) : comp(c) {}
257
result_type operator()(const first_argument_type a, const second_argument_type b) const {
265
typedef TopoGraph::Edge first_argument_type;
266
typedef TopoGraph::Edge second_argument_type;
267
typedef bool result_type;
269
EdgeSorter(const PathVector &rs, Dim2 d, double t) : s(rs, d, t) {}
270
bool operator()(TopoGraph::Edge const &e1, TopoGraph::Edge const &e2) const { return s(*e1.section, *e2.section); }
273
#ifdef SWEEP_GRAPH_DEBUG
274
//used for debugging purposes - each element represents a subsequent iteration of the algorithm.
275
std::vector<std::vector<Section> > monoss;
276
std::vector<std::vector<Section> > chopss;
277
std::vector<std::vector<Section> > contexts;
281
1) take item off sweep sorted todo
282
2) find all of the to-values before the beginning of this section
283
3) sort these lexicographically, process them in order, grouping other sections in the context, and constructing a vertex in one fell swoop.
284
4) add our section into context, splitting on intersections
286
3 is novel, we perform it by storing
289
template<typename A, typename B, typename Z>
290
struct MergeIterator {
296
MergeIterator(A const &av, B &bv, Z const &zv) : a(av), b(bv), z(zv), ai(0), on_a(b.empty() || z(a[0], b.back())) {}
297
MergeIterator &operator++() {
299
on_a = b.empty() ? true : (ai >= a.size() ? false : z(a[ai], b.back()));
302
if(ai >= a.size()) on_a = false;
305
if(b.empty()) on_a = true;
310
typename A::value_type operator*() {
312
return on_a ? a[ai] : b.back();
314
bool done() { return b.empty() && ai >= a.size() - 1; }
315
typename A::value_type operator->() { assert(!done()); return on_a ? a[ai] : b.back(); }
318
void modify_windings(std::vector<int> &windings, boost::shared_ptr<Section> sec, Dim2 d) {
319
unsigned k = sec->curve.path;
320
if(k >= windings.size() || sec->fp[d] == sec->tp[d]) return;
321
if(sec->f < sec->t) windings[k]++;
322
if(sec->f > sec->t) windings[k]--;
326
boost::shared_ptr<Section> section;
329
Context(boost::shared_ptr<Section> sect, int from) : section(sect), from_vert(from), to_vert(-1) {}
333
struct ContextAdapter {
334
typedef Context first_argument_type;
335
typedef typename C::second_argument_type second_argument_type;
336
typedef typename C::result_type result_type;
338
ContextAdapter(const C &c) : comp(c) {}
339
result_type operator()(const Context &a, const second_argument_type &b) const { return comp(a.section, b); }
342
#define DINF std::numeric_limits<double>::infinity()
344
TopoGraph::TopoGraph(PathVector const &ps, Dim2 d, double t) : dim(d), tol(t) {
345
//s_sort = vertical section order
346
ContextAdapter<DerefAdapter<SectionSorter> > s_sort = DerefAdapter<SectionSorter>(SectionSorter(ps, (Dim2)(1-d), tol));
347
//sweep_sort = horizontal sweep order
348
DerefAdapter<SweepSorter> sweep_sort = DerefAdapter<SweepSorter>(SweepSorter(d));
349
//heap_sort = reverse horizontal sweep order
350
ReverseAdapter<DerefAdapter<SweepSorter> > heap_sort = ReverseAdapter<DerefAdapter<SweepSorter> >(sweep_sort);
351
//edge_sort = sorter for edges
352
EdgeSorter edge_sort = EdgeSorter(ps, (Dim2)(1-d), tol);
354
std::vector<boost::shared_ptr<Section> > input_sections = mono_sections(ps, d), chops;
355
std::sort(input_sections.begin(), input_sections.end(), sweep_sort);
357
std::vector<Context> context;
359
vertices.reserve(input_sections.size());
361
//std::vector<unsigned> to_process;
363
std::vector<int> windings(ps.size(), 0);
364
for(MergeIterator<Area, Area, DerefAdapter<SweepSorter> > iter(input_sections, chops, sweep_sort); ; ++iter) {
365
//represents our position in the sweep, which controls what we finalize
366
//if we have no more to process, finish the rest by setting our position to infinity
368
if(iter.done()) lim[X] = lim[Y] = DINF; else lim = iter->fp;
372
for(unsigned i = 0; i < to_process.size(); i++) {
373
if(vertices[to_process[i]].avg[d] + tol < lim[d])
374
for(unsigned j = 0; j < context.size(); j++) {
379
//find all sections to remove
380
for(int i = context.size() - 1; i >= 0; i--) {
381
boost::shared_ptr<Section> sec = context[i].section;
382
if(Point::LexOrderRt(d)(lim, sec->tp)) {
383
//sec->tp is less than or equal to lim
384
if(context[i].to_vert == -1) {
385
//we need to create a new vertex; add everything that enters it
388
std::vector<Edge> enters;
389
std::fill(windings.begin(), windings.end(), 0);
390
for(unsigned j = 0; j < context.size(); j++) {
391
modify_windings(windings, context[j].section, d);
392
if(are_near(sec->tp, context[j].section->tp, tol)) {
393
assert(-1 == context[j].to_vert);
394
context[j].section->windings = windings;
395
context[j].to_vert = vertices.size();
396
enters.push_back(Edge(context[j].section, context[j].from_vert));
397
//avg += context[j].section->tp;
401
//Vertex &v(avg / (double)cnt);
402
Vertex v(context[i].section->tp);
404
vertices.push_back(v);
405
//to_process.push_back(vertices.size() - 1);
407
context.erase(context.begin() + i);
412
boost::shared_ptr<Section> s = *iter;
414
//create a new context, associate a beginning vertex, and insert it in the proper location
415
unsigned ix = find_vertex(vertices, s->fp, tol);
416
if(ix == vertices.size()) {
417
vertices.push_back(Vertex(s->fp));
418
//to_process.push_back(vertices.size() - 1);
420
unsigned context_ix = std::lower_bound(context.begin(), context.end(), s, s_sort) - context.begin();
422
context.insert(context.begin() + context_ix, Context(s, ix));
424
Interval si = Interval(s->fp[1-d], s->tp[1-d]);
426
// Now we intersect with neighbors - do a sweep!
427
std::vector<double> this_splits;
428
for(unsigned i = 0; i < context.size(); i++) {
429
if(context[i].section == context[context_ix].section) continue;
431
boost::shared_ptr<Section> sec = context[i].section;
433
if(!si.intersects(Interval(sec->fp[1-d], sec->tp[1-d]))) continue;
435
std::vector<double> other_splits;
436
Crossings xs = mono_intersect(s->curve.get(ps), Interval(s->f, s->t),
437
sec->curve.get(ps), Interval(sec->f, sec->t));
438
if(xs.empty()) continue;
440
for(unsigned j = 0; j < xs.size(); j++) {
441
this_splits.push_back(xs[j].ta);
442
other_splits.push_back(xs[j].tb);
444
merge(chops, split_section(sec, ps, other_splits, d), heap_sort);
446
if(!this_splits.empty())
447
merge(chops, split_section(context[context_ix].section, ps, this_splits, d), heap_sort);
449
std::sort(chops.begin(), chops.end(), heap_sort);
451
if(context[context_ix].section->tp[d] - context[context_ix].section->fp[d] <= tol) {
452
if(!are_near(context[context_ix].section->tp, context[context_ix].section->fp, tol)) {
453
ix = find_vertex(vertices, context[context_ix].section->tp, tol);
454
if(ix != vertices.size()) {
455
boost::shared_ptr<Section> sec = context[context_ix].section;
456
Edge e(sec, context[context_ix].from_vert);
458
std::vector<Edge>::iterator it = std::lower_bound(vertices[ix].enters.begin(), vertices[ix].enters.end(), e, edge_sort);
460
if(vertices[ix].enters.empty()) {
461
std::fill(windings.begin(), windings.end(), 0);
462
for(unsigned j = 0; j <= context_ix; j++) modify_windings(windings, context[j].section, d);
463
} else if(it == vertices[ix].enters.end()) {
464
windings = (it-1)->section->windings;
465
modify_windings(windings, (it-1)->section, d);
467
windings = it->section->windings;
470
sec->windings = windings;
471
modify_windings(windings, sec, d);
473
for(std::vector<Edge>::iterator it2 = it; it2 != vertices[ix].enters.end(); ++it2) {
474
it2->section->windings = windings;
475
modify_windings(windings, it2->section, d);
478
vertices[ix].enters.insert(it, e);
479
context.erase(context.begin() + context_ix);
481
} else context.erase(context.begin() + context_ix);
485
#ifdef SWEEP_GRAPH_DEBUG
486
std::vector<Section> rem;
487
for(unsigned i = iter.ai + 1; i < iter.a.size(); i++) rem.push_back(*iter.a[i]);
488
monoss.push_back(rem);
489
chopss.push_back(deref_vector(iter.b));
491
for(unsigned i = 0; i < context.size(); i++) rem.push_back(*context[i].section);
492
contexts.push_back(rem);
495
if(iter.done() && context.empty()) return;
499
void trim_whiskers(TopoGraph &g) {
500
std::vector<unsigned> affected;
502
for(unsigned i = 0; i < g.size(); i++)
503
if(g[i].degree() == 1) affected.push_back(i);
505
while(!affected.empty()) {
507
for(unsigned i = 0; i < affected.size(); i++)
508
if(g[affected[i]].degree() == 1)
509
affected[j++] = g.remove_edge(affected[i], 0).other;
514
void add_edge_at(TopoGraph &g, unsigned ix, boost::shared_ptr<Section> s, TopoGraph::Edge jx, bool before = true) {
515
TopoGraph::Vertex &v = g[ix];
516
for(unsigned i = 0; i < v.enters.size(); i++) {
517
if(v.enters[i].section == s) {
518
v.enters.insert(v.enters.begin() + (before ? i : i + 1), jx);
522
for(unsigned i = 0; i < v.exits.size(); i++) {
523
if(v.exits[i].section == s) {
524
v.exits.insert(v.exits.begin() + (before ? i : i + 1), jx);
528
//TODO: fix the fall through to here
532
void double_whiskers(TopoGraph &g) {
533
for(unsigned i = 0; i < g.size(); i++) {
534
if(g[i].degree() == 1) {
536
TopoGraph::Edge e = g[i][0];
538
TopoGraph::Edge next_edge = g[j][1 - g[j].find_section(e.section)];
539
boost::shared_ptr<Section> new_section = boost::shared_ptr<Section>(new Section(*e.section));
540
add_edge_at(g, j, e.section, TopoGraph::Edge(new_section, e.other), false);
541
add_edge_at(g, e.other, e.section, TopoGraph::Edge(new_section, j), true);
543
if(g[e.other].degree() == 3) {
553
void remove_degenerate(TopoGraph &g) {
554
for(unsigned i = 0; i < g.size(); i++) {
555
for(int j = g[i].degree(); j >= 0; j--) {
556
if(g[i][j].other == i)
562
void remove_vestigial(TopoGraph &g) {
563
for(unsigned i = 0; i < g.size(); i++) {
564
if(g[i].enters.size() == 1 && g[i].exits.size() == 1) {
565
TopoGraph::Edge &e1 = g[i][0], &e2 = g[i][1];
566
if(e1.section == e2.section) {
568
Section *new_section = new Section(e1.section->curve,
569
e1.section->f, e2.section->t,
570
e1.section->fp, e2.section->tp);
574
Vertex *v1 = e1.other, *v2 = e2.other;
575
v1->lookup_section(e1.section) = Edge(new_section, v2);
576
v2->lookup_section(e2.section) = Edge(new_section, v1);
577
g.erase(g.begin() + i);
583
//planar area finding
584
//linear on number of edges
585
Areas traverse_areas(TopoGraph const &g) {
588
//stores which edges we've visited
589
std::vector<std::vector<bool> > visited;
590
for(unsigned i = 0; i < g.size(); i++) visited.push_back(std::vector<bool>(g[i].degree(), false));
592
for(unsigned vix = 0; vix < g.size(); vix++) {
594
//find an unvisited edge to start on
596
unsigned e_ix = std::find(visited[vix].begin(), visited[vix].end(), false) - visited[vix].begin();
597
if(e_ix == g[vix].degree()) break;
599
unsigned start = e_ix;
603
//std::vector<std::vector<bool> > before(visited);
604
while(cur < g.size() && !visited[cur][e_ix]) {
605
visited[cur][e_ix] = true;
607
TopoGraph::Edge e = g[cur][e_ix];
609
area.push_back(e.section);
611
//go to clockwise edge
613
unsigned deg = g[cur].degree();
614
e_ix = g[cur].find_section(e.section);
616
if(deg == 1 || e_ix == deg) {
617
visited[cur][e_ix] = true;
621
e_ix = (e_ix + 1) % deg;
623
if(cur == vix && start == e_ix) break;
625
//if(vix == cur && start == e_ix) {
627
//} else visited = before;
633
void remove_area_whiskers(Areas &areas) {
634
for(int i = areas.size() - 1; i >= 0; i--)
635
if(areas[i].size() == 2 && *areas[i][0] == *areas[i][1])
636
areas.erase(areas.begin() + i);
639
Path area_to_path(PathVector const &ps, Area const &area) {
641
if(area.size() == 0) return ret;
642
Point prev = area[0]->fp;
643
for(unsigned i = 0; i < area.size(); i++) {
644
bool forward = are_near(area[i]->fp, prev, 0.01);
645
Curve *curv = area[i]->curve.get(ps).portion(
646
forward ? area[i]->f : area[i]->t,
647
forward ? area[i]->t : area[i]->f);
648
ret.append(*curv, Path::STITCH_DISCONTINUOUS);
650
prev = forward ? area[i]->tp : area[i]->fp;
655
PathVector areas_to_paths(PathVector const &ps, Areas const &areas) {
656
std::vector<Path> ret;
657
ret.reserve(areas.size());
658
for(unsigned i = 0; i < areas.size(); i++)
659
ret.push_back(area_to_path(ps, areas[i]));
663
} // end namespace Geom
added
removed
src/2geom/toposweep.cpp
