From c883d7627a479c8c5b6a9f77b9841fa5631572ad Mon Sep 17 00:00:00 2001 From: Krzysztof Kosi??ski Date: Mon, 27 Apr 2015 19:39:29 -0400 Subject: 2Geom sync - initial commit (bzr r14059.2.1) --- src/2geom/intersection-graph.cpp | 296 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 296 insertions(+) create mode 100644 src/2geom/intersection-graph.cpp (limited to 'src/2geom/intersection-graph.cpp') diff --git a/src/2geom/intersection-graph.cpp b/src/2geom/intersection-graph.cpp new file mode 100644 index 000000000..abe462e3f --- /dev/null +++ b/src/2geom/intersection-graph.cpp @@ -0,0 +1,296 @@ +/** + * \file + * \brief Intersection graph for Boolean operations + *//* + * Authors: + * Krzysztof Kosiński + * + * Copyright 2015 Authors + * + * This library is free software; you can redistribute it and/or + * modify it either under the terms of the GNU Lesser General Public + * License version 2.1 as published by the Free Software Foundation + * (the "LGPL") or, at your option, under the terms of the Mozilla + * Public License Version 1.1 (the "MPL"). If you do not alter this + * notice, a recipient may use your version of this file under either + * the MPL or the LGPL. + * + * You should have received a copy of the LGPL along with this library + * in the file COPYING-LGPL-2.1; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * You should have received a copy of the MPL along with this library + * in the file COPYING-MPL-1.1 + * + * The contents of this file are subject to the Mozilla Public License + * Version 1.1 (the "License"); you may not use this file except in + * compliance with the License. You may obtain a copy of the License at + * http://www.mozilla.org/MPL/ + * + * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY + * OF ANY KIND, either express or implied. See the LGPL or the MPL for + * the specific language governing rights and limitations. + */ + +#include <2geom/intersection-graph.h> +#include <2geom/path.h> +#include <2geom/pathvector.h> +#include + +namespace Geom { + +struct IntersectionVertexLess { + bool operator()(IntersectionVertex const &a, IntersectionVertex const &b) const { + return a.pos < b.pos; + } +}; + +/** @class PathIntersectionGraph + * @brief Intermediate data for computing Boolean operations on paths. + * + * This class implements the Greiner-Hormann clipping algorithm, + * with improvements by Foster and Overfelt. + * + * @ingroup Paths + */ + +PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector const &b, Coord precision) + : _a(a) + , _b(b) +{ + if (a.empty() || b.empty()) return; + + // 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 (std::size_t i = 0; i < b.size(); ++i) { + _b[i].close(); + } + + std::vector pxs = _a.intersect(_b, precision); + if (pxs.empty()) return; + if (pxs.size() % 2) return; + + // prepare intersection lists for each path component + for (std::size_t i = 0; i < _a.size(); ++i) { + _xalists.push_back(new IntersectionList()); + } + for (std::size_t i = 0; i < _b.size(); ++i) { + _xblists.push_back(new IntersectionList()); + } + + 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->pos = pxs[i].first; + xb->pos = pxs[i].second; + xa->p = xb->p = pxs[i].point(); + xa->neighbor = xb; + xb->neighbor = xa; + _xs.push_back(xa); + _xs.push_back(xb); + _xalists[xa->pos.path_index].push_back(*xa); + _xblists[xb->pos.path_index].push_back(*xb); + } + + for (std::size_t i = 0; i < _xalists.size(); ++i) { + _xalists[i].sort(IntersectionVertexLess()); + } + for (std::size_t i = 0; i < _xblists.size(); ++i) { + _xblists[i].sort(IntersectionVertexLess()); + } + + typedef IntersectionList::iterator Iter; + + // determine in/out/on flags using winding + for (unsigned npv = 0; npv < 2; ++npv) { + boost::ptr_vector &ls = npv ? _xblists : _xalists; + PathVector const &pv = npv ? b : a; + PathVector const &other = npv ? a : b; + + for (unsigned li = 0; li < ls.size(); ++li) { + for (Iter i = ls[li].begin(); i != ls[li].end(); ++i) { + Iter n = boost::next(i); + if (n == ls[li].end()) { + n = ls[li].begin(); + } + std::size_t pi = i->pos.path_index; + + PathInterval ival = forward_interval(i->pos, n->pos, pv[pi].size()); + PathPosition mid = ival.inside(precision); + + // TODO check for degenerate cases + // requires changes in the winding routine + int w = other.winding(pv[pi].pointAt(mid)); + if (w % 2) { + i->next = POINT_INSIDE; + n->previous = POINT_INSIDE; + } else { + i->next = POINT_OUTSIDE; + n->previous = POINT_OUTSIDE; + } + } + + // assign exit / entry flags + for (Iter i = ls[li].begin(); i != ls[li].end(); ++i) { + i->entry = ((i->next == POINT_INSIDE) && (i->previous == POINT_OUTSIDE)); + } + } + } +} + +PathVector PathIntersectionGraph::getUnion() +{ + PathVector result = _getResult(false, false); + _handleNonintersectingPaths(result, 0, false); + _handleNonintersectingPaths(result, 1, false); + return result; +} + +PathVector PathIntersectionGraph::getIntersection() +{ + PathVector result = _getResult(true, true); + _handleNonintersectingPaths(result, 0, true); + _handleNonintersectingPaths(result, 1, true); + return result; +} + +PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) +{ + typedef IntersectionList::iterator Iter; + PathVector result; + if (_xs.empty()) return result; + + // reset processed status + for (unsigned npv = 0; npv < 2; ++npv) { + boost::ptr_vector &ls = npv ? _xblists : _xalists; + for (std::size_t li = 0; li < ls.size(); ++li) { + for (Iter k = ls[li].begin(); k != ls[li].end(); ++k) { + k->processed = false; + } + } + } + + unsigned n_processed = 0; + + while (true) { + PathVector const *cur = &_a, *other = &_b; + boost::ptr_vector *lscur = &_xalists, *lsother = &_xblists; + + // find unprocessed intersection + Iter i; + if (!_findUnprocessed(i)) break; + + result.push_back(Path(i->p)); + result.back().setStitching(true); + + while (!i->processed) { + Iter prev = i; + std::size_t pi = i->pos.path_index; + // determine which direction to go + // union: always go outside + // intersection: always go inside + // 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; + } else { + reverse = i->entry ^ enter_b; + } + + // get next intersection + if (reverse) { + if (i == (*lscur)[pi].begin()) { + i = (*lscur)[pi].end(); + } + --i; + } else { + ++i; + if (i == (*lscur)[pi].end()) { + i = (*lscur)[pi].begin(); + } + } + + // append portion of path + PathInterval ival = PathInterval::from_direction( + prev->pos.asPathPosition(), i->pos.asPathPosition(), + reverse, (*cur)[pi].size()); + + (*cur)[pi].appendPortionTo(result.back(), ival, prev->p, i->p); + + // mark both vertices as processed + prev->processed = true; + i->processed = true; + n_processed += 2; + + // switch to the other path + i = (*lsother)[i->neighbor->pos.path_index].iterator_to(*i->neighbor); + std::swap(lscur, lsother); + std::swap(cur, other); + } + + assert(!result.back().empty()); + } + + assert(n_processed == _xs.size()); + + return result; +} + +void PathIntersectionGraph::_handleNonintersectingPaths(PathVector &result, int 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 + * completely inside or completely outside the other pathvector. We test this by + * 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 const &ls = which ? _xblists : _xalists; + PathVector const &cur = which ? _b : _a; + PathVector const &other = which ? _a : _b; + + for (std::size_t i = 0; i < cur.size(); ++i) { + if (!ls.empty() && !ls[i].empty()) continue; + + int w = other.winding(cur[i].initialPoint()); + bool path_inside = w % 2 != 0; + if (path_inside == inside) { + result.push_back(cur[i]); + } + } +} + +bool PathIntersectionGraph::_findUnprocessed(IntersectionList::iterator &result) +{ + typedef IntersectionList::iterator Iter; + + Iter it; + + for (std::size_t k = 0; k < _xalists.size(); ++k) { + it = _xalists[k].begin(); + for (; it != _xalists[k].end(); ++it) { + if (!it->processed) { + result = it; + return true; + } + } + } + + return false; +} + +} // namespace Geom + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 : -- cgit v1.2.3 From 6a9762c7603a32c7ec5cc0aaed8048d84daee6e8 Mon Sep 17 00:00:00 2001 From: Krzysztof Kosi??ski Date: Thu, 30 Apr 2015 11:17:07 +0200 Subject: Update 2Geom to r2347 (bzr r14059.2.3) --- src/2geom/intersection-graph.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/2geom/intersection-graph.cpp') diff --git a/src/2geom/intersection-graph.cpp b/src/2geom/intersection-graph.cpp index abe462e3f..b9e2feeed 100644 --- a/src/2geom/intersection-graph.cpp +++ b/src/2geom/intersection-graph.cpp @@ -119,7 +119,7 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con std::size_t pi = i->pos.path_index; PathInterval ival = forward_interval(i->pos, n->pos, pv[pi].size()); - PathPosition mid = ival.inside(precision); + PathTime mid = ival.inside(precision); // TODO check for degenerate cases // requires changes in the winding routine @@ -216,7 +216,7 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) // append portion of path PathInterval ival = PathInterval::from_direction( - prev->pos.asPathPosition(), i->pos.asPathPosition(), + prev->pos.asPathTime(), i->pos.asPathTime(), reverse, (*cur)[pi].size()); (*cur)[pi].appendPortionTo(result.back(), ival, prev->p, i->p); -- cgit v1.2.3 From 25fa09178b7d0d0befa708e93ea5316ef381caa0 Mon Sep 17 00:00:00 2001 From: Krzysztof Kosi??ski Date: Fri, 22 May 2015 10:23:27 +0200 Subject: Update to 2Geom revision 2396 (bzr r14059.2.16) --- src/2geom/intersection-graph.cpp | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) (limited to 'src/2geom/intersection-graph.cpp') diff --git a/src/2geom/intersection-graph.cpp b/src/2geom/intersection-graph.cpp index b9e2feeed..ff96c28a8 100644 --- a/src/2geom/intersection-graph.cpp +++ b/src/2geom/intersection-graph.cpp @@ -35,6 +35,7 @@ #include <2geom/path.h> #include <2geom/pathvector.h> #include +#include namespace Geom { @@ -157,6 +158,41 @@ PathVector PathIntersectionGraph::getIntersection() return result; } +PathVector PathIntersectionGraph::getAminusB() +{ + PathVector result = _getResult(false, true); + _handleNonintersectingPaths(result, 0, false); + return result; +} + +PathVector PathIntersectionGraph::getBminusA() +{ + PathVector result = _getResult(true, false); + _handleNonintersectingPaths(result, 1, false); + return result; +} + +PathVector PathIntersectionGraph::getXOR() +{ + PathVector r1 = getAminusB(); + PathVector r2 = getBminusA(); + std::copy(r2.begin(), r2.end(), std::back_inserter(r1)); + return r1; +} + +std::vector PathIntersectionGraph::intersectionPoints() const +{ + std::vector result; + + typedef IntersectionList::const_iterator Iter; + for (std::size_t i = 0; i < _xalists.size(); ++i) { + for (Iter j = _xalists[i].begin(); j != _xalists[i].end(); ++j) { + result.push_back(j->p); + } + } + return result; +} + PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) { typedef IntersectionList::iterator Iter; @@ -231,6 +267,7 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) std::swap(lscur, lsother); std::swap(cur, other); } + result.back().close(true); assert(!result.back().empty()); } -- cgit v1.2.3 From 60437ac397d41678daba5daece227240e8ddd364 Mon Sep 17 00:00:00 2001 From: Krzysztof Kosi??ski Date: Sat, 4 Jul 2015 17:25:59 +0200 Subject: Upgrade to 2Geom r2413 (bzr r14059.2.18) --- src/2geom/intersection-graph.cpp | 137 ++++++++++++++++++++++++++++----------- 1 file changed, 99 insertions(+), 38 deletions(-) (limited to 'src/2geom/intersection-graph.cpp') diff --git a/src/2geom/intersection-graph.cpp b/src/2geom/intersection-graph.cpp index ff96c28a8..e18561f67 100644 --- a/src/2geom/intersection-graph.cpp +++ b/src/2geom/intersection-graph.cpp @@ -39,7 +39,7 @@ namespace Geom { -struct IntersectionVertexLess { +struct PathIntersectionGraph::IntersectionVertexLess { bool operator()(IntersectionVertex const &a, IntersectionVertex const &b) const { return a.pos < b.pos; } @@ -49,7 +49,8 @@ struct IntersectionVertexLess { * @brief Intermediate data for computing Boolean operations on paths. * * This class implements the Greiner-Hormann clipping algorithm, - * with improvements by Foster and Overfelt. + * with improvements inspired by Foster and Overfelt as well as some + * original contributions. * * @ingroup Paths */ @@ -69,15 +70,16 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con } std::vector pxs = _a.intersect(_b, 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.size() % 2) return; // prepare intersection lists for each path component for (std::size_t i = 0; i < _a.size(); ++i) { - _xalists.push_back(new IntersectionList()); + _apaths.push_back(new PathData()); } for (std::size_t i = 0; i < _b.size(); ++i) { - _xblists.push_back(new IntersectionList()); + _bpaths.push_back(new PathData()); } for (std::size_t i = 0; i < pxs.size(); ++i) { @@ -92,30 +94,32 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con xb->neighbor = xa; _xs.push_back(xa); _xs.push_back(xb); - _xalists[xa->pos.path_index].push_back(*xa); - _xblists[xb->pos.path_index].push_back(*xb); + _apaths[xa->pos.path_index].xlist.push_back(*xa); + _bpaths[xb->pos.path_index].xlist.push_back(*xb); } - for (std::size_t i = 0; i < _xalists.size(); ++i) { - _xalists[i].sort(IntersectionVertexLess()); + for (std::size_t i = 0; i < _apaths.size(); ++i) { + _apaths[i].xlist.sort(IntersectionVertexLess()); } - for (std::size_t i = 0; i < _xblists.size(); ++i) { - _xblists[i].sort(IntersectionVertexLess()); + for (std::size_t i = 0; i < _bpaths.size(); ++i) { + _bpaths[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 &ls = npv ? _xblists : _xalists; + boost::ptr_vector &ls = npv ? _bpaths : _apaths; + boost::ptr_vector &ols = npv ? _apaths : _bpaths; PathVector const &pv = npv ? b : a; PathVector const &other = npv ? a : b; for (unsigned li = 0; li < ls.size(); ++li) { - for (Iter i = ls[li].begin(); i != ls[li].end(); ++i) { + IntersectionList &xl = ls[li].xlist; + for (Iter i = xl.begin(); i != xl.end(); ++i) { Iter n = boost::next(i); - if (n == ls[li].end()) { - n = ls[li].begin(); + if (n == xl.end()) { + n = xl.begin(); } std::size_t pi = i->pos.path_index; @@ -123,7 +127,6 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con PathTime mid = ival.inside(precision); // TODO check for degenerate cases - // requires changes in the winding routine int w = other.winding(pv[pi].pointAt(mid)); if (w % 2) { i->next = POINT_INSIDE; @@ -134,9 +137,22 @@ PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector con } } - // assign exit / entry flags - for (Iter i = ls[li].begin(); i != ls[li].end(); ++i) { - i->entry = ((i->next == POINT_INSIDE) && (i->previous == POINT_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; + } + } else { + i->entry = ((i->next == POINT_INSIDE) && (i->previous == POINT_OUTSIDE)); + ++i; + } } } } @@ -162,6 +178,7 @@ PathVector PathIntersectionGraph::getAminusB() { PathVector result = _getResult(false, true); _handleNonintersectingPaths(result, 0, false); + _handleNonintersectingPaths(result, 1, true); return result; } @@ -169,6 +186,7 @@ PathVector PathIntersectionGraph::getBminusA() { PathVector result = _getResult(true, false); _handleNonintersectingPaths(result, 1, false); + _handleNonintersectingPaths(result, 0, true); return result; } @@ -180,13 +198,22 @@ PathVector PathIntersectionGraph::getXOR() return r1; } +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(); + } + return result; +} + std::vector PathIntersectionGraph::intersectionPoints() const { std::vector result; typedef IntersectionList::const_iterator Iter; - for (std::size_t i = 0; i < _xalists.size(); ++i) { - for (Iter j = _xalists[i].begin(); j != _xalists[i].end(); ++j) { + 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); } } @@ -201,9 +228,9 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) // reset processed status for (unsigned npv = 0; npv < 2; ++npv) { - boost::ptr_vector &ls = npv ? _xblists : _xalists; + boost::ptr_vector &ls = npv ? _bpaths : _apaths; for (std::size_t li = 0; li < ls.size(); ++li) { - for (Iter k = ls[li].begin(); k != ls[li].end(); ++k) { + for (Iter k = ls[li].xlist.begin(); k != ls[li].xlist.end(); ++k) { k->processed = false; } } @@ -213,7 +240,7 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) while (true) { PathVector const *cur = &_a, *other = &_b; - boost::ptr_vector *lscur = &_xalists, *lsother = &_xblists; + boost::ptr_vector *lscur = &_apaths, *lsother = &_bpaths; // find unprocessed intersection Iter i; @@ -239,14 +266,14 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) // get next intersection if (reverse) { - if (i == (*lscur)[pi].begin()) { - i = (*lscur)[pi].end(); + if (i == (*lscur)[pi].xlist.begin()) { + i = (*lscur)[pi].xlist.end(); } --i; } else { ++i; - if (i == (*lscur)[pi].end()) { - i = (*lscur)[pi].begin(); + if (i == (*lscur)[pi].xlist.end()) { + i = (*lscur)[pi].xlist.begin(); } } @@ -263,7 +290,7 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) n_processed += 2; // switch to the other path - i = (*lsother)[i->neighbor->pos.path_index].iterator_to(*i->neighbor); + i = (*lsother)[i->neighbor->pos.path_index].xlist.iterator_to(*i->neighbor); std::swap(lscur, lsother); std::swap(cur, other); } @@ -272,7 +299,7 @@ PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) assert(!result.back().empty()); } - assert(n_processed == _xs.size()); + assert(n_processed == size() * 2); return result; } @@ -285,15 +312,29 @@ 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 const &ls = which ? _xblists : _xalists; + boost::ptr_vector const &ls = which ? _bpaths : _apaths; PathVector const &cur = which ? _b : _a; PathVector const &other = which ? _a : _b; for (std::size_t i = 0; i < cur.size(); ++i) { - if (!ls.empty() && !ls[i].empty()) continue; + // the path data vector might have been left empty if there were no intersections at all + bool has_path_data = !ls.empty(); + // Skip if the path has intersections + if (has_path_data && !ls[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) { + path_inside = true; + } else if (has_path_data && ls[i].removed_out != 0) { + path_inside = false; + } else { + int w = other.winding(cur[i].initialPoint()); + path_inside = w % 2 != 0; + } - int w = other.winding(cur[i].initialPoint()); - bool path_inside = w % 2 != 0; if (path_inside == inside) { result.push_back(cur[i]); } @@ -304,11 +345,16 @@ bool PathIntersectionGraph::_findUnprocessed(IntersectionList::iterator &result) { typedef IntersectionList::iterator Iter; - Iter it; + Iter it, last; - for (std::size_t k = 0; k < _xalists.size(); ++k) { - it = _xalists[k].begin(); - for (; it != _xalists[k].end(); ++it) { + 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; @@ -319,6 +365,21 @@ bool PathIntersectionGraph::_findUnprocessed(IntersectionList::iterator &result) return false; } + +std::ostream &operator<<(std::ostream &os, PathIntersectionGraph const &pig) +{ + 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) { + os << j->pos << " - " << j->neighbor->pos << " @ " << j->p << "\n"; + } + } + return os; +} + } // namespace Geom /* -- cgit v1.2.3