summaryrefslogtreecommitdiffstats
path: root/src/2geom/intersection-graph.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/2geom/intersection-graph.cpp')
-rw-r--r--src/2geom/intersection-graph.cpp373
1 files changed, 236 insertions, 137 deletions
diff --git a/src/2geom/intersection-graph.cpp b/src/2geom/intersection-graph.cpp
index e18561f67..d469d3ffc 100644
--- a/src/2geom/intersection-graph.cpp
+++ b/src/2geom/intersection-graph.cpp
@@ -34,6 +34,7 @@
#include <2geom/intersection-graph.h>
#include <2geom/path.h>
#include <2geom/pathvector.h>
+#include <2geom/utils.h>
#include <iostream>
#include <iterator>
@@ -56,101 +57,174 @@ struct PathIntersectionGraph::IntersectionVertexLess {
*/
PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector const &b, Coord precision)
- : _a(a)
- , _b(b)
+ : _graph_valid(true)
{
if (a.empty() || b.empty()) return;
+ _pv[0] = a;
+ _pv[1] = b;
+
+ _prepareArguments();
+ bool has_intersections = _prepareIntersectionLists(precision);
+ if (!has_intersections) return;
+
+ _assignEdgeWindingParities(precision);
+ _assignComponentStatusFromDegenerateIntersections();
+ _removeDegenerateIntersections();
+ if (_graph_valid) {
+ _verify();
+ }
+}
+
+void PathIntersectionGraph::_prepareArguments()
+{
// all paths must be closed, otherwise we will miss some intersections
- for (std::size_t i = 0; i < a.size(); ++i) {
- _a[i].close();
+ for (int w = 0; w < 2; ++w) {
+ for (std::size_t i = 0; i < _pv[w].size(); ++i) {
+ _pv[w][i].close();
+ }
}
- for (std::size_t i = 0; i < b.size(); ++i) {
- _b[i].close();
+ // remove degenerate segments
+ for (int w = 0; w < 2; ++w) {
+ for (std::size_t i = _pv[w].size(); i > 0; --i) {
+ if (_pv[w][i-1].empty()) {
+ _pv[w].erase(_pv[w].begin() + (i-1));
+ }
+ for (std::size_t j = _pv[w][i-1].size(); j > 0; --j) {
+ if (_pv[w][i-1][j-1].isDegenerate()) {
+ _pv[w][i-1].erase(_pv[w][i-1].begin() + (j-1));
+ }
+ }
+ }
}
+}
- std::vector<PVIntersection> pxs = _a.intersect(_b, precision);
+bool PathIntersectionGraph::_prepareIntersectionLists(Coord precision)
+{
+ std::vector<PVIntersection> pxs = _pv[0].intersect(_pv[1], precision);
// NOTE: this early return means that the path data structures will not be created
// if there are no intersections at all!
- if (pxs.empty()) return;
+ if (pxs.empty()) return false;
// prepare intersection lists for each path component
- for (std::size_t i = 0; i < _a.size(); ++i) {
- _apaths.push_back(new PathData());
- }
- for (std::size_t i = 0; i < _b.size(); ++i) {
- _bpaths.push_back(new PathData());
+ for (unsigned w = 0; w < 2; ++w) {
+ for (std::size_t i = 0; i < _pv[w].size(); ++i) {
+ _components[w].push_back(new PathData(w, i));
+ }
}
+ // create intersection vertices
for (std::size_t i = 0; i < pxs.size(); ++i) {
IntersectionVertex *xa, *xb;
xa = new IntersectionVertex();
xb = new IntersectionVertex();
- xa->processed = xb->processed = false;
+ //xa->processed = xb->processed = false;
+ xa->which = 0; xb->which = 1;
xa->pos = pxs[i].first;
xb->pos = pxs[i].second;
xa->p = xb->p = pxs[i].point();
xa->neighbor = xb;
xb->neighbor = xa;
+ xa->next_edge = xb->next_edge = OUTSIDE;
+ xa->defective = xb->defective = false;
_xs.push_back(xa);
_xs.push_back(xb);
- _apaths[xa->pos.path_index].xlist.push_back(*xa);
- _bpaths[xb->pos.path_index].xlist.push_back(*xb);
+ _components[0][xa->pos.path_index].xlist.push_back(*xa);
+ _components[1][xb->pos.path_index].xlist.push_back(*xb);
}
- for (std::size_t i = 0; i < _apaths.size(); ++i) {
- _apaths[i].xlist.sort(IntersectionVertexLess());
- }
- for (std::size_t i = 0; i < _bpaths.size(); ++i) {
- _bpaths[i].xlist.sort(IntersectionVertexLess());
+ // sort components according to time value of intersections
+ for (unsigned w = 0; w < 2; ++w) {
+ for (std::size_t i = 0; i < _components[w].size(); ++i) {
+ _components[w][i].xlist.sort(IntersectionVertexLess());
+ }
}
- typedef IntersectionList::iterator Iter;
-
- // determine in/out/on flags using winding
- for (unsigned npv = 0; npv < 2; ++npv) {
- boost::ptr_vector<PathData> &ls = npv ? _bpaths : _apaths;
- boost::ptr_vector<PathData> &ols = npv ? _apaths : _bpaths;
- PathVector const &pv = npv ? b : a;
- PathVector const &other = npv ? a : b;
-
- for (unsigned li = 0; li < ls.size(); ++li) {
- IntersectionList &xl = ls[li].xlist;
- for (Iter i = xl.begin(); i != xl.end(); ++i) {
- Iter n = boost::next(i);
- if (n == xl.end()) {
- n = xl.begin();
- }
+ return true;
+}
+
+void PathIntersectionGraph::_assignEdgeWindingParities(Coord precision)
+{
+ // determine the winding numbers of path portions between intersections
+ for (unsigned w = 0; w < 2; ++w) {
+ unsigned ow = (w+1) % 2;
+
+ for (unsigned li = 0; li < _components[w].size(); ++li) {
+ IntersectionList &xl = _components[w][li].xlist;
+ for (ILIter i = xl.begin(); i != xl.end(); ++i) {
+ ILIter n = cyclic_next(i, xl);
std::size_t pi = i->pos.path_index;
- PathInterval ival = forward_interval(i->pos, n->pos, pv[pi].size());
+ PathInterval ival = forward_interval(i->pos, n->pos, _pv[w][pi].size());
PathTime mid = ival.inside(precision);
- // TODO check for degenerate cases
- int w = other.winding(pv[pi].pointAt(mid));
- if (w % 2) {
- i->next = POINT_INSIDE;
- n->previous = POINT_INSIDE;
+ Point wpoint = _pv[w][pi].pointAt(mid);
+ _winding_points.push_back(wpoint);
+ int wdg = _pv[ow].winding(wpoint);
+ if (wdg % 2) {
+ i->next_edge = INSIDE;
} else {
- i->next = POINT_OUTSIDE;
- n->previous = POINT_OUTSIDE;
+ i->next_edge = OUTSIDE;
}
}
+ }
+ }
+}
+
+void PathIntersectionGraph::_assignComponentStatusFromDegenerateIntersections()
+{
+ // If a path has only degenerate intersections, assign its status now.
+ // This protects against later accidentaly picking a point for winding
+ // determination that is exactly at a removed intersection.
+ for (unsigned w = 0; w < 2; ++w) {
+ for (unsigned li = 0; li < _components[w].size(); ++li) {
+ IntersectionList &xl = _components[w][li].xlist;
+ bool has_in = false;
+ bool has_out = false;
+ for (ILIter i = xl.begin(); i != xl.end(); ++i) {
+ has_in |= (i->next_edge == INSIDE);
+ has_out |= (i->next_edge == OUTSIDE);
+ }
+ if (has_in && !has_out) {
+ _components[w][li].status = INSIDE;
+ }
+ if (!has_in && has_out) {
+ _components[w][li].status = OUTSIDE;
+ }
+ }
+ }
+}
- // remove intersections that don't change between in/out
- // and assign exit / entry flags
- for (Iter i = xl.begin(); i != xl.end();) {
- if (i->previous == i->next) {
- IntersectionList &oxl = ols[i->neighbor->pos.path_index].xlist;
- oxl.erase(oxl.iterator_to(*i->neighbor));
- xl.erase(i++);
- if (i->next == POINT_INSIDE) {
- ++ls[li].removed_in;
- } else {
- ++ls[li].removed_out;
+void PathIntersectionGraph::_removeDegenerateIntersections()
+{
+ // remove intersections that don't change between in/out
+ for (unsigned w = 0; w < 2; ++w) {
+ for (unsigned li = 0; li < _components[w].size(); ++li) {
+ IntersectionList &xl = _components[w][li].xlist;
+ for (ILIter i = xl.begin(); i != xl.end();) {
+ ILIter n = cyclic_next(i, xl);
+ if (i->next_edge == n->next_edge) {
+ bool last_node = (i == n);
+ ILIter nn = _getNeighbor(n);
+ IntersectionList &oxl = _getPathData(nn).xlist;
+
+ // When exactly 3 out of 4 edges adjacent to an intersection
+ // have the same winding, we have a defective intersection,
+ // which is neither degenerate nor normal. Those can occur in paths
+ // that contain overlapping segments. We cannot handle that case
+ // for now, so throw an exception.
+ if (cyclic_prior(nn, oxl)->next_edge != nn->next_edge) {
+ _graph_valid = false;
+ n->defective = true;
+ nn->defective = true;
+ ++i;
+ continue;
}
+
+ oxl.erase(nn);
+ xl.erase(n);
+ if (last_node) break;
} else {
- i->entry = ((i->next == POINT_INSIDE) && (i->previous == POINT_OUTSIDE));
++i;
}
}
@@ -158,6 +232,20 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con
}
}
+void PathIntersectionGraph::_verify()
+{
+ for (unsigned w = 0; w < 2; ++w) {
+ for (unsigned li = 0; li < _components[w].size(); ++li) {
+ IntersectionList &xl = _components[w][li].xlist;
+ assert(xl.size() % 2 == 0);
+ for (ILIter i = xl.begin(); i != xl.end(); ++i) {
+ ILIter j = cyclic_next(i, xl);
+ assert(i->next_edge != j->next_edge);
+ }
+ }
+ }
+}
+
PathVector PathIntersectionGraph::getUnion()
{
PathVector result = _getResult(false, false);
@@ -192,8 +280,9 @@ PathVector PathIntersectionGraph::getBminusA()
PathVector PathIntersectionGraph::getXOR()
{
- PathVector r1 = getAminusB();
- PathVector r2 = getBminusA();
+ PathVector r1, r2;
+ r1 = getAminusB();
+ r2 = getBminusA();
std::copy(r2.begin(), r2.end(), std::back_inserter(r1));
return r1;
}
@@ -201,37 +290,61 @@ PathVector PathIntersectionGraph::getXOR()
std::size_t PathIntersectionGraph::size() const
{
std::size_t result = 0;
- for (std::size_t i = 0; i < _apaths.size(); ++i) {
- result += _apaths[i].xlist.size();
+ for (std::size_t i = 0; i < _components[0].size(); ++i) {
+ result += _components[0][i].xlist.size();
}
return result;
}
-std::vector<Point> PathIntersectionGraph::intersectionPoints() const
+std::vector<Point> PathIntersectionGraph::intersectionPoints(bool defective) const
{
std::vector<Point> result;
- typedef IntersectionList::const_iterator Iter;
- for (std::size_t i = 0; i < _apaths.size(); ++i) {
- for (Iter j = _apaths[i].xlist.begin(); j != _apaths[i].xlist.end(); ++j) {
- result.push_back(j->p);
+ typedef IntersectionList::const_iterator CILIter;
+ for (std::size_t i = 0; i < _components[0].size(); ++i) {
+ for (CILIter j = _components[0][i].xlist.begin(); j != _components[0][i].xlist.end(); ++j) {
+ if (j->defective == defective) {
+ result.push_back(j->p);
+ }
}
}
return result;
}
+void PathIntersectionGraph::fragments(PathVector &in, PathVector &out) const
+{
+ typedef boost::ptr_vector<PathData>::const_iterator PIter;
+ for (unsigned w = 0; w < 2; ++w) {
+ for (PIter li = _components[w].begin(); li != _components[w].end(); ++li) {
+ for (CILIter k = li->xlist.begin(); k != li->xlist.end(); ++k) {
+ CILIter n = cyclic_next(k, li->xlist);
+ // TODO: investigate why non-contiguous paths are sometimes generated here
+ Path frag(k->p);
+ frag.setStitching(true);
+ PathInterval ival = forward_interval(k->pos, n->pos, _pv[w][k->pos.path_index].size());
+ _pv[w][k->pos.path_index].appendPortionTo(frag, ival, k->p, n->p);
+ if (k->next_edge == INSIDE) {
+ in.push_back(frag);
+ } else {
+ out.push_back(frag);
+ }
+ }
+ }
+ }
+}
+
PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b)
{
- typedef IntersectionList::iterator Iter;
+ typedef boost::ptr_vector<PathData>::iterator PIter;
PathVector result;
if (_xs.empty()) return result;
// reset processed status
- for (unsigned npv = 0; npv < 2; ++npv) {
- boost::ptr_vector<PathData> &ls = npv ? _bpaths : _apaths;
- for (std::size_t li = 0; li < ls.size(); ++li) {
- for (Iter k = ls[li].xlist.begin(); k != ls[li].xlist.end(); ++k) {
- k->processed = false;
+ _ulist.clear();
+ for (unsigned w = 0; w < 2; ++w) {
+ for (PIter li = _components[w].begin(); li != _components[w].end(); ++li) {
+ for (ILIter k = li->xlist.begin(); k != li->xlist.end(); ++k) {
+ _ulist.push_back(*k);
}
}
}
@@ -239,18 +352,17 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b)
unsigned n_processed = 0;
while (true) {
- PathVector const *cur = &_a, *other = &_b;
- boost::ptr_vector<PathData> *lscur = &_apaths, *lsother = &_bpaths;
-
- // find unprocessed intersection
- Iter i;
- if (!_findUnprocessed(i)) break;
+ // get unprocessed intersection
+ if (_ulist.empty()) break;
+ IntersectionVertex &iv = _ulist.front();
+ unsigned w = iv.which;
+ ILIter i = _components[w][iv.pos.path_index].xlist.iterator_to(iv);
result.push_back(Path(i->p));
result.back().setStitching(true);
- while (!i->processed) {
- Iter prev = i;
+ while (i->_proc_hook.is_linked()) {
+ ILIter prev = i;
std::size_t pi = i->pos.path_index;
// determine which direction to go
// union: always go outside
@@ -258,53 +370,55 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b)
// a minus b: go inside in b, outside in a
// b minus a: go inside in a, outside in b
bool reverse = false;
- if (cur == &_a) {
- reverse = i->entry ^ enter_a;
+ if (w == 0) {
+ reverse = (i->next_edge == INSIDE) ^ enter_a;
} else {
- reverse = i->entry ^ enter_b;
+ reverse = (i->next_edge == INSIDE) ^ enter_b;
}
// get next intersection
if (reverse) {
- if (i == (*lscur)[pi].xlist.begin()) {
- i = (*lscur)[pi].xlist.end();
- }
- --i;
+ i = cyclic_prior(i, _components[w][pi].xlist);
} else {
- ++i;
- if (i == (*lscur)[pi].xlist.end()) {
- i = (*lscur)[pi].xlist.begin();
- }
+ i = cyclic_next(i, _components[w][pi].xlist);
}
// append portion of path
PathInterval ival = PathInterval::from_direction(
prev->pos.asPathTime(), i->pos.asPathTime(),
- reverse, (*cur)[pi].size());
+ reverse, _pv[i->which][pi].size());
- (*cur)[pi].appendPortionTo(result.back(), ival, prev->p, i->p);
+ _pv[i->which][pi].appendPortionTo(result.back(), ival, prev->p, i->p);
// mark both vertices as processed
- prev->processed = true;
- i->processed = true;
+ //prev->processed = true;
+ //i->processed = true;
n_processed += 2;
+ if (prev->_proc_hook.is_linked()) {
+ _ulist.erase(_ulist.iterator_to(*prev));
+ }
+ if (i->_proc_hook.is_linked()) {
+ _ulist.erase(_ulist.iterator_to(*i));
+ }
// switch to the other path
- i = (*lsother)[i->neighbor->pos.path_index].xlist.iterator_to(*i->neighbor);
- std::swap(lscur, lsother);
- std::swap(cur, other);
+ i = _getNeighbor(i);
+ w = i->which;
}
result.back().close(true);
assert(!result.back().empty());
}
+ /*if (n_processed != size() * 2) {
+ std::cerr << "Processed " << n_processed << " intersections, expected " << (size() * 2) << std::endl;
+ }*/
assert(n_processed == size() * 2);
return result;
}
-void PathIntersectionGraph::_handleNonintersectingPaths(PathVector &result, int which, bool inside)
+void PathIntersectionGraph::_handleNonintersectingPaths(PathVector &result, unsigned which, bool inside)
{
/* Every component that has any intersections will be processed by _getResult.
* Here we take care of paths that don't have any intersections. They are either
@@ -312,68 +426,53 @@ void PathIntersectionGraph::_handleNonintersectingPaths(PathVector &result, int
* evaluating the winding rule at the initial point. If inside is true and
* the path is inside, we add it to the result.
*/
- boost::ptr_vector<PathData> const &ls = which ? _bpaths : _apaths;
- PathVector const &cur = which ? _b : _a;
- PathVector const &other = which ? _a : _b;
+ unsigned w = which;
+ unsigned ow = (w+1) % 2;
- for (std::size_t i = 0; i < cur.size(); ++i) {
+ for (std::size_t i = 0; i < _pv[w].size(); ++i) {
// the path data vector might have been left empty if there were no intersections at all
- bool has_path_data = !ls.empty();
+ bool has_path_data = !_components[w].empty();
// Skip if the path has intersections
- if (has_path_data && !ls[i].xlist.empty()) continue;
+ if (has_path_data && !_components[w][i].xlist.empty()) continue;
bool path_inside = false;
- // If the path had any intersections removed, use the result of that,
- // since one of those might have been at the initial point.
- // Also, it saves time.
- if (has_path_data && ls[i].removed_in != 0) {
+ // Use the in/out determination from constructor, if available
+ if (has_path_data && _components[w][i].status == INSIDE) {
path_inside = true;
- } else if (has_path_data && ls[i].removed_out != 0) {
+ } else if (has_path_data && _components[w][i].status == OUTSIDE) {
path_inside = false;
} else {
- int w = other.winding(cur[i].initialPoint());
- path_inside = w % 2 != 0;
+ int wdg = _pv[ow].winding(_pv[w][i].initialPoint());
+ path_inside = wdg % 2 != 0;
}
if (path_inside == inside) {
- result.push_back(cur[i]);
+ result.push_back(_pv[w][i]);
}
}
}
-bool PathIntersectionGraph::_findUnprocessed(IntersectionList::iterator &result)
+PathIntersectionGraph::ILIter PathIntersectionGraph::_getNeighbor(ILIter iter)
{
- typedef IntersectionList::iterator Iter;
-
- Iter it, last;
-
- for (std::size_t k = 0; k < _apaths.size(); ++k) {
- it = _apaths[k].xlist.begin();
- last = _apaths[k].xlist.end();
- for (; it != last; ++it) {
- if (!it->_hook.is_linked()) {
- // this intersection was removed since it did not change inside/outside status
- continue;
- }
- if (!it->processed) {
- result = it;
- return true;
- }
- }
- }
-
- return false;
+ unsigned ow = (iter->which + 1) % 2;
+ return _components[ow][iter->neighbor->pos.path_index].xlist.iterator_to(*iter->neighbor);
}
+PathIntersectionGraph::PathData &
+PathIntersectionGraph::_getPathData(ILIter iter)
+{
+ return _components[iter->which][iter->pos.path_index];
+}
std::ostream &operator<<(std::ostream &os, PathIntersectionGraph const &pig)
{
+ typedef PathIntersectionGraph::IntersectionList::const_iterator CILIter;
os << "Intersection graph:\n"
<< pig._xs.size()/2 << " total intersections\n"
<< pig.size() << " considered intersections\n";
- for (std::size_t i = 0; i < pig._apaths.size(); ++i) {
- typedef PathIntersectionGraph::IntersectionList::const_iterator Iter;
- for (Iter j = pig._apaths[i].xlist.begin(); j != pig._apaths[i].xlist.end(); ++j) {
+ for (std::size_t i = 0; i < pig._components[0].size(); ++i) {
+ PathIntersectionGraph::IntersectionList const &xl = pig._components[0][i].xlist;
+ for (CILIter j = xl.begin(); j != xl.end(); ++j) {
os << j->pos << " - " << j->neighbor->pos << " @ " << j->p << "\n";
}
}
generated by cgit v1.2.3 (git 2.25.1) at 2026-05-19 18:44:37 +0000