toposweep.cpp revision 76addc201c409e81eaaa73fe27cc0f79c4db097c
//using namespace Geom;
namespace Geom {
}
}
else
}
else
}
unsigned i = 0;
for(; i < degree(); i++)
return i;
}
if(v.degree()) {
if(v.degree()) {
return ret;
}
}
assert(0);
return v[0]; // if assert is disabled, return first Edge.
}
unsigned ix = 0;
}
for(unsigned i = 0; i < ix; i++)
}
void TopoGraph::assert_invariants() const {
assert(are_near(e.section->fp, vertices[i].avg, tol) || are_near(e.section->tp, vertices[i].avg, tol));
}
}
}
//near predicate utilized in process_splits
template<typename T>
struct NearPredicate { bool operator()(T x, T y) { return are_near(x, y); } };
// ensures that f and t are elements of a vector, sorts and uniqueifies
// also asserts that no values fall outside of f and t
// if f is greater than t, the sort is in reverse
//remove any splits which fall outside t / f
std::vector<double>::iterator end = std::unique(splits.begin(), splits.end(), NearPredicate<double>());
}
// A little sugar for appending a list to another
template<typename T>
//returns a list of monotonic sections of a path
//TODO: handle saddle points
//TODO: necessary? can we have empty paths?
//find the points of 0 derivative
delete deriv;
//split on points of 0 derivative
monos.push_back(boost::shared_ptr<Section>(new Section(CurveIx(i,j), splits[k-1], splits[k], ps, d)));
}
}
}
return monos;
}
//finds the t-value on a section, which corresponds to a particular horizontal or vertical line
//d indicates the dimension along which the roots is performed.
//-1 is returned if no root is found
return -1;
}
// since the sections are monotonic, if the endpoints are on opposite sides of this
// coincidence, the order is determinable
//TODO: sampling / higher derivatives when unit tangents match
// tangent can point backwards
}
}
if(&a == &b) return false;
//TODO: should we use tol in these conditions?
//we know that the rects intersect on dim
//by referencing f / t we are assuming that the section was constructed with 1-dim
b, b.f > b.t ? b.f - 0.01 : b.f + 0.01);
//b inside a
//TODO: fix bug that necessitates this
return section_order(a, ta, b, b.f);
} else {
//a inside b
//TODO: fix bug that necessitates this
return section_order(a, a.f, b, tb);
}
}
}
// splits a section into pieces, as specified by an array of doubles, mutating the section to
// represent the first part, and returning the rest
//TODO: output iterator?
std::vector<boost::shared_ptr<Section> > split_section(boost::shared_ptr<Section> s, PathVector const &ps, std::vector<double> &cuts, Dim2 d) {
process_splits(cuts, s->f, s->t);
s->t = cuts[1];
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)));
return ret;
}
//merges the sorted lists a and b according to comparison z
template<typename X, typename Z>
void merge(X &a, X const &b, Z const &z) {
concatenate(a, b);
}
//TODO: faster than linear
}
//takes a vector of T pointers, and returns a vector of T with copies
template<typename T>
return ret;
}
//used to create reversed sorting predicates
template<typename C>
struct ReverseAdapter {
typedef typename C::second_argument_type first_argument_type;
typedef typename C::first_argument_type second_argument_type;
typedef typename C::result_type result_type;
const C ∁
ReverseAdapter(const C &c) : comp(c) {}
result_type operator()(const first_argument_type &a, const second_argument_type &b) const { return comp(b, a); }
};
//used to sort std::vector<Section*>
template<typename C>
struct DerefAdapter {
typedef typename C::result_type result_type;
const C ∁
DerefAdapter(const C &c) : comp(c) {}
if(!a) return false;
if(!b) return true;
return comp(*a, *b);
}
};
struct EdgeSorter {
typedef bool result_type;
bool operator()(TopoGraph::Edge const &e1, TopoGraph::Edge const &e2) const { return s(*e1.section, *e2.section); }
};
#ifdef SWEEP_GRAPH_DEBUG
//used for debugging purposes - each element represents a subsequent iteration of the algorithm.
#endif
/*
1) take item off sweep sorted todo
2) find all of the to-values before the beginning of this section
3) sort these lexicographically, process them in order, grouping other sections in the context, and constructing a vertex in one fell swoop.
4) add our section into context, splitting on intersections
3 is novel, we perform it by storing
*/
template<typename A, typename B, typename Z>
struct MergeIterator {
A const &a;
B &b;
Z const &z;
unsigned ai;
bool on_a;
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())) {}
MergeIterator &operator++() {
if(!done()) {
if(on_a) {
++ai;
} else {
}
}
return *this;
}
typename A::value_type operator*() {
}
};
}
struct Context {
int from_vert;
int to_vert;
};
template<typename C>
struct ContextAdapter {
typedef Context first_argument_type;
typedef typename C::second_argument_type second_argument_type;
typedef typename C::result_type result_type;
const C ∁
ContextAdapter(const C &c) : comp(c) {}
result_type operator()(const Context &a, const second_argument_type &b) const { return comp(a.section, b); }
};
//s_sort = vertical section order
ContextAdapter<DerefAdapter<SectionSorter> > s_sort = DerefAdapter<SectionSorter>(SectionSorter(ps, (Dim2)(1-d), tol));
//sweep_sort = horizontal sweep order
//heap_sort = reverse horizontal sweep order
ReverseAdapter<DerefAdapter<SweepSorter> > heap_sort = ReverseAdapter<DerefAdapter<SweepSorter> >(sweep_sort);
//edge_sort = sorter for edges
//std::vector<unsigned> to_process;
for(MergeIterator<Area, Area, DerefAdapter<SweepSorter> > iter(input_sections, chops, sweep_sort); ; ++iter) {
//represents our position in the sweep, which controls what we finalize
//if we have no more to process, finish the rest by setting our position to infinity
/*
//finalize vertices
for(unsigned i = 0; i < to_process.size(); i++) {
if(vertices[to_process[i]].avg[d] + tol < lim[d])
for(unsigned j = 0; j < context.size(); j++) {
}
} */
//find all sections to remove
//sec->tp is less than or equal to lim
//we need to create a new vertex; add everything that enters it
//Point avg;
//unsigned cnt;
//avg += context[j].section->tp;
//cnt++;
}
}
//Vertex &v(avg / (double)cnt);
//to_process.push_back(vertices.size() - 1);
}
}
}
//create a new context, associate a beginning vertex, and insert it in the proper location
//to_process.push_back(vertices.size() - 1);
}
unsigned context_ix = std::lower_bound(context.begin(), context.end(), s, s_sort) - context.begin();
// Now we intersect with neighbors - do a sweep!
}
}
if(!this_splits.empty())
std::vector<Edge>::iterator it = std::lower_bound(vertices[ix].enters.begin(), vertices[ix].enters.end(), e, edge_sort);
} else {
}
}
}
}
}
#ifdef SWEEP_GRAPH_DEBUG
#endif
}
}
void trim_whiskers(TopoGraph &g) {
for(unsigned i = 0; i < g.size(); i++)
unsigned j = 0;
}
}
void add_edge_at(TopoGraph &g, unsigned ix, boost::shared_ptr<Section> s, TopoGraph::Edge jx, bool before = true) {
return;
}
}
return;
}
}
//TODO: fix the fall through to here
//assert(false);
}
void double_whiskers(TopoGraph &g) {
for(unsigned i = 0; i < g.size(); i++) {
if(g[i].degree() == 1) {
unsigned j = i;
while(true) {
j = e.other;
e = next_edge;
} else break;
}
}
}
}
/*
void remove_degenerate(TopoGraph &g) {
for(unsigned i = 0; i < g.size(); i++) {
for(int j = g[i].degree(); j >= 0; j--) {
if(g[i][j].other == i)
}
}
}*/
/*
void remove_vestigial(TopoGraph &g) {
for(unsigned i = 0; i < g.size(); i++) {
TopoGraph::Edge &e1 = g[i][0], &e2 = g[i][1];
//vestigial vert
Section *new_section = new Section(e1.section->curve,
e1.other
Vertex *v1 = e1.other, *v2 = e2.other;
v1->lookup_section(e1.section) = Edge(new_section, v2);
v2->lookup_section(e2.section) = Edge(new_section, v1);
g.erase(g.begin() + i);
}
}
}
}*/
//planar area finding
//linear on number of edges
//stores which edges we've visited
while(true) {
//find an unvisited edge to start on
//std::vector<std::vector<bool> > before(visited);
//go to clockwise edge
break;
}
}
//if(vix == cur && start == e_ix) {
//} else visited = before;
}
}
return ret;
}
}
ret.setStitching(true);
delete curv;
}
ret.setStitching(false);
return ret;
}
//ret.reserve(areas.size());
return ret;
}
} // end namespace Geom