| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /** | ||
| 2 | * \file | ||
| 3 | * \brief Intersection graph for Boolean operations | ||
| 4 | *//* | ||
| 5 | * Authors: | ||
| 6 | * Krzysztof Kosiński <tweenk.pl@gmail.com> | ||
| 7 | * | ||
| 8 | * Copyright 2015 Authors | ||
| 9 | * | ||
| 10 | * This library is free software; you can redistribute it and/or | ||
| 11 | * modify it either under the terms of the GNU Lesser General Public | ||
| 12 | * License version 2.1 as published by the Free Software Foundation | ||
| 13 | * (the "LGPL") or, at your option, under the terms of the Mozilla | ||
| 14 | * Public License Version 1.1 (the "MPL"). If you do not alter this | ||
| 15 | * notice, a recipient may use your version of this file under either | ||
| 16 | * the MPL or the LGPL. | ||
| 17 | * | ||
| 18 | * You should have received a copy of the LGPL along with this library | ||
| 19 | * in the file COPYING-LGPL-2.1; if not, write to the Free Software | ||
| 20 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
| 21 | * You should have received a copy of the MPL along with this library | ||
| 22 | * in the file COPYING-MPL-1.1 | ||
| 23 | * | ||
| 24 | * The contents of this file are subject to the Mozilla Public License | ||
| 25 | * Version 1.1 (the "License"); you may not use this file except in | ||
| 26 | * compliance with the License. You may obtain a copy of the License at | ||
| 27 | * http://www.mozilla.org/MPL/ | ||
| 28 | * | ||
| 29 | * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY | ||
| 30 | * OF ANY KIND, either express or implied. See the LGPL or the MPL for | ||
| 31 | * the specific language governing rights and limitations. | ||
| 32 | */ | ||
| 33 | |||
| 34 | #include <2geom/intersection-graph.h> | ||
| 35 | #include <2geom/path.h> | ||
| 36 | #include <2geom/pathvector.h> | ||
| 37 | #include <2geom/utils.h> | ||
| 38 | #include <iostream> | ||
| 39 | #include <iterator> | ||
| 40 | |||
| 41 | namespace Geom { | ||
| 42 | |||
| 43 | /// Function object for comparing intersection vertices based on the intersection time. | ||
| 44 | struct PathIntersectionGraph::IntersectionVertexLess { | ||
| 45 | 66 | bool operator()(IntersectionVertex const &a, IntersectionVertex const &b) const { | |
| 46 | 66 | return a.pos < b.pos; | |
| 47 | } | ||
| 48 | }; | ||
| 49 | |||
| 50 | 7 | PathIntersectionGraph::PathIntersectionGraph(PathVector const &a, PathVector const &b, Coord precision) | |
| 51 |
7/18✓ Branch 1 taken 14 times.
✓ Branch 2 taken 7 times.
✓ Branch 4 taken 7 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 14 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 14 times.
✓ Branch 10 taken 7 times.
✓ Branch 12 taken 7 times.
✗ Branch 13 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
|
42 | : _graph_valid(true) |
| 52 | { | ||
| 53 |
1/2✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
|
7 | _pv[0] = a; |
| 54 |
1/2✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
|
7 | _pv[1] = b; |
| 55 | |||
| 56 |
5/6✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 6 times.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 6 times.
|
7 | if (a.empty() || b.empty()) return; |
| 57 | |||
| 58 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
6 | _prepareArguments(); |
| 59 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
6 | bool has_intersections = _prepareIntersectionLists(precision); |
| 60 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
|
6 | if (!has_intersections) return; |
| 61 | |||
| 62 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
4 | _assignEdgeWindingParities(precision); |
| 63 | |||
| 64 | // If a path has only degenerate intersections, assign its status now. | ||
| 65 | // This protects against later accidentally picking a point for winding | ||
| 66 | // determination that is exactly at a removed intersection. | ||
| 67 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
4 | _assignComponentStatusFromDegenerateIntersections(); |
| 68 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
4 | _removeDegenerateIntersections(); |
| 69 |
1/2✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
|
4 | if (_graph_valid) { |
| 70 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
4 | _verify(); |
| 71 | } | ||
| 72 | ✗ | } | |
| 73 | |||
| 74 | /** Prepare the operands stored in PathIntersectionGraph::_pv by closing all of their constituent | ||
| 75 | * paths and removing degenerate segments from them. | ||
| 76 | */ | ||
| 77 | 6 | void PathIntersectionGraph::_prepareArguments() | |
| 78 | { | ||
| 79 | // all paths must be closed, otherwise we will miss some intersections | ||
| 80 |
2/2✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
|
18 | for (auto & w : _pv) { |
| 81 |
2/2✓ Branch 7 taken 12 times.
✓ Branch 8 taken 12 times.
|
24 | for (auto & i : w) { |
| 82 |
1/2✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
|
12 | i.close(); |
| 83 | } | ||
| 84 | } | ||
| 85 | // remove degenerate segments | ||
| 86 |
2/2✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
|
18 | for (auto & w : _pv) { |
| 87 |
2/2✓ Branch 1 taken 12 times.
✓ Branch 2 taken 12 times.
|
24 | for (std::size_t i = w.size(); i > 0; --i) { |
| 88 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
|
12 | if (w[i-1].empty()) { |
| 89 | ✗ | w.erase(w.begin() + (i-1)); | |
| 90 | ✗ | continue; | |
| 91 | } | ||
| 92 |
2/2✓ Branch 2 taken 73 times.
✓ Branch 3 taken 12 times.
|
85 | for (std::size_t j = w[i-1].size(); j > 0; --j) { |
| 93 |
1/2✗ Branch 3 not taken.
✓ Branch 4 taken 73 times.
|
73 | if (w[i-1][j-1].isDegenerate()) { |
| 94 | ✗ | w[i-1].erase(w[i-1].begin() + (j-1)); | |
| 95 | } | ||
| 96 | } | ||
| 97 | } | ||
| 98 | } | ||
| 99 | 6 | } | |
| 100 | |||
| 101 | /** @brief Compute the lists of intersections between the constituent paths of both operands. | ||
| 102 | * @param precision – the precision setting for the sweepline algorithm. | ||
| 103 | * @return Whether any intersections were found. | ||
| 104 | */ | ||
| 105 | 6 | bool PathIntersectionGraph::_prepareIntersectionLists(Coord precision) | |
| 106 | { | ||
| 107 |
1/2✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
|
6 | std::vector<PVIntersection> pxs = _pv[0].intersect(_pv[1], precision); |
| 108 | // NOTE: this early return means that the path data structures will not be created | ||
| 109 | // if there are no intersections at all! | ||
| 110 |
2/2✓ Branch 1 taken 2 times.
✓ Branch 2 taken 4 times.
|
6 | if (pxs.empty()) return false; |
| 111 | |||
| 112 | // prepare intersection lists for each path component | ||
| 113 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
|
12 | for (unsigned w = 0; w < 2; ++w) { |
| 114 |
2/2✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
|
16 | for (std::size_t i = 0; i < _pv[w].size(); ++i) { |
| 115 |
3/8✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
|
8 | _components[w].push_back(new PathData(w, i)); |
| 116 | } | ||
| 117 | } | ||
| 118 | |||
| 119 | // create intersection vertices | ||
| 120 |
2/2✓ Branch 7 taken 22 times.
✓ Branch 8 taken 4 times.
|
26 | for (auto & px : pxs) { |
| 121 | IntersectionVertex *xa, *xb; | ||
| 122 |
2/6✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
22 | xa = new IntersectionVertex(); |
| 123 |
2/6✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
|
22 | xb = new IntersectionVertex(); |
| 124 | //xa->processed = xb->processed = false; | ||
| 125 | 22 | xa->which = 0; xb->which = 1; | |
| 126 | 22 | xa->pos = px.first; | |
| 127 | 22 | xb->pos = px.second; | |
| 128 | 22 | xa->p = xb->p = px.point(); | |
| 129 | 22 | xa->neighbor = xb; | |
| 130 | 22 | xb->neighbor = xa; | |
| 131 | 22 | xa->next_edge = xb->next_edge = OUTSIDE; | |
| 132 | 22 | xa->defective = xb->defective = false; | |
| 133 |
1/2✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
|
22 | _xs.push_back(xa); |
| 134 |
1/2✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
|
22 | _xs.push_back(xb); |
| 135 |
2/4✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
|
22 | _components[0][xa->pos.path_index].xlist.push_back(*xa); |
| 136 |
2/4✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
|
22 | _components[1][xb->pos.path_index].xlist.push_back(*xb); |
| 137 | } | ||
| 138 | |||
| 139 | // sort intersections in each component according to time value | ||
| 140 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
|
12 | for (auto & _component : _components) { |
| 141 |
2/2✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
|
16 | for (std::size_t i = 0; i < _component.size(); ++i) { |
| 142 |
2/4✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
|
8 | _component[i].xlist.sort(IntersectionVertexLess()); |
| 143 | } | ||
| 144 | } | ||
| 145 | |||
| 146 | 4 | return true; | |
| 147 | 6 | } | |
| 148 | |||
| 149 | /** Determine whether path portions between consecutive intersections lie inside or outside | ||
| 150 | * of the other path-vector. | ||
| 151 | */ | ||
| 152 | 4 | void PathIntersectionGraph::_assignEdgeWindingParities(Coord precision) | |
| 153 | { | ||
| 154 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
|
12 | for (unsigned w = 0; w < 2; ++w) { |
| 155 | 8 | unsigned ow = (w+1) % 2; ///< The index of the other operand | |
| 156 | |||
| 157 |
2/2✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
|
16 | for (unsigned li = 0; li < _components[w].size(); ++li) { // Traverse all paths in the component |
| 158 | 8 | IntersectionList &xl = _components[w][li].xlist; | |
| 159 |
4/6✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 52 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 44 times.
✓ Branch 10 taken 8 times.
|
104 | for (ILIter i = xl.begin(); i != xl.end(); ++i) { // Traverse all intersections in the path |
| 160 |
1/2✓ Branch 3 taken 44 times.
✗ Branch 4 not taken.
|
88 | ILIter n = cyclic_next(i, xl); |
| 161 | 44 | std::size_t pi = i->pos.path_index; | |
| 162 | |||
| 163 | /// Path time interval from the current crossing to the next one | ||
| 164 |
2/4✓ Branch 3 taken 44 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 44 times.
✗ Branch 7 not taken.
|
132 | PathInterval ival = forward_interval(i->pos, n->pos, _pv[w][pi].size()); |
| 165 |
1/2✓ Branch 2 taken 44 times.
✗ Branch 3 not taken.
|
44 | PathTime mid = ival.inside(precision); |
| 166 | |||
| 167 |
1/2✓ Branch 3 taken 44 times.
✗ Branch 4 not taken.
|
44 | Point wpoint = _pv[w][pi].pointAt(mid); |
| 168 |
1/2✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
|
44 | _winding_points.push_back(wpoint); |
| 169 |
1/2✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
|
44 | int wdg = _pv[ow].winding(wpoint); |
| 170 |
2/2✓ Branch 0 taken 22 times.
✓ Branch 1 taken 22 times.
|
44 | if (wdg % 2) { |
| 171 | 22 | i->next_edge = INSIDE; | |
| 172 | } else { | ||
| 173 | 22 | i->next_edge = OUTSIDE; | |
| 174 | } | ||
| 175 | } | ||
| 176 | } | ||
| 177 | } | ||
| 178 | 4 | } | |
| 179 | |||
| 180 | /** Detect the situation where a path is either entirely inside or entirely outside of the other | ||
| 181 | * path-vector and set the status flag accordingly. | ||
| 182 | */ | ||
| 183 | 4 | void PathIntersectionGraph::_assignComponentStatusFromDegenerateIntersections() | |
| 184 | { | ||
| 185 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
|
12 | for (auto & _component : _components) { |
| 186 |
2/2✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
|
16 | for (unsigned li = 0; li < _component.size(); ++li) { |
| 187 | 8 | IntersectionList &xl = _component[li].xlist; | |
| 188 | 8 | bool has_in = false; | |
| 189 | 8 | bool has_out = false; | |
| 190 |
4/6✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 44 times.
✓ Branch 9 taken 8 times.
|
60 | for (auto & i : xl) { |
| 191 | 44 | has_in |= (i.next_edge == INSIDE); | |
| 192 | 44 | has_out |= (i.next_edge == OUTSIDE); | |
| 193 | } | ||
| 194 |
4/4✓ Branch 0 taken 7 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 6 times.
|
8 | if (has_in && !has_out) { |
| 195 | 1 | _component[li].status = INSIDE; | |
| 196 | } | ||
| 197 |
3/4✓ Branch 0 taken 1 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
|
8 | if (!has_in && has_out) { |
| 198 | 1 | _component[li].status = OUTSIDE; | |
| 199 | } | ||
| 200 | } | ||
| 201 | } | ||
| 202 | 4 | } | |
| 203 | |||
| 204 | /** Remove intersections that don't change between in/out. | ||
| 205 | * | ||
| 206 | * In general, a degenerate intersection can happen at a point where | ||
| 207 | * two shapes "kiss" (are tangent) but do not cross into each other. | ||
| 208 | */ | ||
| 209 | 4 | void PathIntersectionGraph::_removeDegenerateIntersections() | |
| 210 | { | ||
| 211 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
|
12 | for (auto & _component : _components) { |
| 212 |
2/2✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
|
16 | for (unsigned li = 0; li < _component.size(); ++li) { |
| 213 | 8 | IntersectionList &xl = _component[li].xlist; | |
| 214 |
4/6✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 47 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 40 times.
✓ Branch 10 taken 7 times.
|
94 | for (ILIter i = xl.begin(); i != xl.end();) { |
| 215 |
1/2✓ Branch 3 taken 40 times.
✗ Branch 4 not taken.
|
80 | ILIter n = cyclic_next(i, xl); |
| 216 |
2/2✓ Branch 0 taken 4 times.
✓ Branch 1 taken 36 times.
|
80 | if (i->next_edge == n->next_edge) { // Both edges inside or both outside |
| 217 | 4 | bool last_node = (i == n); ///< Whether this is the last remaining crossing. | |
| 218 |
1/2✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
|
8 | ILIter nn = _getNeighbor(n); |
| 219 |
1/2✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
|
8 | IntersectionList &oxl = _getPathData(nn).xlist; |
| 220 | |||
| 221 | // When exactly 3 out of 4 edges adjacent to an intersection | ||
| 222 | // have the same winding, we have a defective intersection, | ||
| 223 | // which is neither degenerate nor normal. Those can occur in paths | ||
| 224 | // that contain overlapping segments. | ||
| 225 |
2/4✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 4 times.
|
16 | if (cyclic_prior(nn, oxl)->next_edge != nn->next_edge) { |
| 226 | // Not a backtrack - set the defective flag. | ||
| 227 | ✗ | _graph_valid = false; | |
| 228 | ✗ | n->defective = true; | |
| 229 | ✗ | nn->defective = true; | |
| 230 | ++i; | ||
| 231 | ✗ | continue; | |
| 232 | } | ||
| 233 | // Erase the degenerate or defective crossings | ||
| 234 |
1/2✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
|
8 | oxl.erase(nn); |
| 235 |
1/2✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
|
8 | xl.erase(n); |
| 236 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
|
4 | if (last_node) break; |
| 237 | } else { | ||
| 238 | ++i; | ||
| 239 | } | ||
| 240 | } | ||
| 241 | } | ||
| 242 | } | ||
| 243 | 4 | } | |
| 244 | |||
| 245 | /** Verify that all paths contain an even number of intersections and that | ||
| 246 | * the intersection graph does not contain leaves (degree one vertices). | ||
| 247 | */ | ||
| 248 | 4 | void PathIntersectionGraph::_verify() | |
| 249 | { | ||
| 250 | #ifndef NDEBUG | ||
| 251 |
2/2✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
|
12 | for (auto & _component : _components) { |
| 252 |
2/2✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
|
16 | for (unsigned li = 0; li < _component.size(); ++li) { |
| 253 | 8 | IntersectionList &xl = _component[li].xlist; | |
| 254 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
|
8 | assert(xl.size() % 2 == 0); |
| 255 |
4/6✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 44 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 36 times.
✓ Branch 10 taken 8 times.
|
88 | for (ILIter i = xl.begin(); i != xl.end(); ++i) { |
| 256 |
1/2✓ Branch 3 taken 36 times.
✗ Branch 4 not taken.
|
72 | ILIter j = cyclic_next(i, xl); |
| 257 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 36 times.
|
72 | assert(i->next_edge != j->next_edge); |
| 258 | } | ||
| 259 | } | ||
| 260 | } | ||
| 261 | #endif | ||
| 262 | 4 | } | |
| 263 | |||
| 264 | 6 | PathVector PathIntersectionGraph::getUnion() | |
| 265 | { | ||
| 266 | 6 | PathVector result = _getResult(false, false); | |
| 267 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
6 | _handleNonintersectingPaths(result, 0, false); |
| 268 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
6 | _handleNonintersectingPaths(result, 1, false); |
| 269 | 6 | return result; | |
| 270 | ✗ | } | |
| 271 | |||
| 272 | 3 | PathVector PathIntersectionGraph::getIntersection() | |
| 273 | { | ||
| 274 | 3 | PathVector result = _getResult(true, true); | |
| 275 |
1/2✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
|
3 | _handleNonintersectingPaths(result, 0, true); |
| 276 |
1/2✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
|
3 | _handleNonintersectingPaths(result, 1, true); |
| 277 | 3 | return result; | |
| 278 | ✗ | } | |
| 279 | |||
| 280 | 6 | PathVector PathIntersectionGraph::getAminusB() | |
| 281 | { | ||
| 282 | 6 | PathVector result = _getResult(false, true); | |
| 283 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
6 | _handleNonintersectingPaths(result, 0, false); |
| 284 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
6 | _handleNonintersectingPaths(result, 1, true); |
| 285 | 6 | return result; | |
| 286 | ✗ | } | |
| 287 | |||
| 288 | 6 | PathVector PathIntersectionGraph::getBminusA() | |
| 289 | { | ||
| 290 | 6 | PathVector result = _getResult(true, false); | |
| 291 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
6 | _handleNonintersectingPaths(result, 1, false); |
| 292 |
1/2✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
|
6 | _handleNonintersectingPaths(result, 0, true); |
| 293 | 6 | return result; | |
| 294 | ✗ | } | |
| 295 | |||
| 296 | 2 | PathVector PathIntersectionGraph::getXOR() | |
| 297 | { | ||
| 298 | 2 | PathVector r1, r2; | |
| 299 |
1/2✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
2 | r1 = getAminusB(); |
| 300 |
1/2✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
2 | r2 = getBminusA(); |
| 301 |
2/4✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
|
2 | std::copy(r2.begin(), r2.end(), std::back_inserter(r1)); |
| 302 | 4 | return r1; | |
| 303 | 2 | } | |
| 304 | |||
| 305 | 15 | std::size_t PathIntersectionGraph::size() const | |
| 306 | { | ||
| 307 | 15 | std::size_t result = 0; | |
| 308 |
2/2✓ Branch 1 taken 15 times.
✓ Branch 2 taken 15 times.
|
30 | for (std::size_t i = 0; i < _components[0].size(); ++i) { |
| 309 | 15 | result += _components[0][i].xlist.size(); | |
| 310 | } | ||
| 311 | 15 | return result; | |
| 312 | } | ||
| 313 | |||
| 314 | ✗ | std::vector<Point> PathIntersectionGraph::intersectionPoints(bool defective) const | |
| 315 | { | ||
| 316 | ✗ | std::vector<Point> result; | |
| 317 | |||
| 318 | ✗ | for (std::size_t i = 0; i < _components[0].size(); ++i) { | |
| 319 | ✗ | for (const auto & j : _components[0][i].xlist) { | |
| 320 | ✗ | if (j.defective == defective) { | |
| 321 | ✗ | result.push_back(j.p); | |
| 322 | } | ||
| 323 | } | ||
| 324 | } | ||
| 325 | ✗ | return result; | |
| 326 | ✗ | } | |
| 327 | |||
| 328 | ✗ | void PathIntersectionGraph::fragments(PathVector &in, PathVector &out) const | |
| 329 | { | ||
| 330 | typedef boost::ptr_vector<PathData>::const_iterator PIter; | ||
| 331 | ✗ | for (unsigned w = 0; w < 2; ++w) { | |
| 332 | ✗ | for (PIter li = _components[w].begin(); li != _components[w].end(); ++li) { | |
| 333 | ✗ | for (CILIter k = li->xlist.begin(); k != li->xlist.end(); ++k) { | |
| 334 | ✗ | CILIter n = cyclic_next(k, li->xlist); | |
| 335 | // TODO: investigate why non-contiguous paths are sometimes generated here | ||
| 336 | ✗ | Path frag(k->p); | |
| 337 | ✗ | frag.setStitching(true); | |
| 338 | ✗ | PathInterval ival = forward_interval(k->pos, n->pos, _pv[w][k->pos.path_index].size()); | |
| 339 | ✗ | _pv[w][k->pos.path_index].appendPortionTo(frag, ival, k->p, n->p); | |
| 340 | ✗ | if (k->next_edge == INSIDE) { | |
| 341 | ✗ | in.push_back(frag); | |
| 342 | } else { | ||
| 343 | ✗ | out.push_back(frag); | |
| 344 | } | ||
| 345 | ✗ | } | |
| 346 | } | ||
| 347 | } | ||
| 348 | ✗ | } | |
| 349 | |||
| 350 | /** @brief Compute the partial result of a boolean operation by looking at components containing | ||
| 351 | * intersections and stitching the correct path portions between them, depending on the truth | ||
| 352 | * table of the operation. | ||
| 353 | * | ||
| 354 | * @param enter_a – whether the path portions contained inside operand A should be part of the boundary | ||
| 355 | * of the boolean operation's result. | ||
| 356 | * @param enter_b – whether the path portions contained inside operand B should be part of the boundary | ||
| 357 | * of the boolean operation's result. | ||
| 358 | * | ||
| 359 | * These two flags completely determine how to resolve the crossings when building the result | ||
| 360 | * and therefore encode which boolean operation we are performing. For example, the boolean intersection | ||
| 361 | * corresponds to enter_a == true and enter_b == true, as can be seen by looking at a Venn diagram. | ||
| 362 | */ | ||
| 363 | 21 | PathVector PathIntersectionGraph::_getResult(bool enter_a, bool enter_b) | |
| 364 | { | ||
| 365 | 21 | PathVector result; | |
| 366 |
2/2✓ Branch 1 taken 6 times.
✓ Branch 2 taken 15 times.
|
21 | if (_xs.empty()) return result; |
| 367 | |||
| 368 | // Create the list of intersections to process | ||
| 369 |
1/2✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
|
15 | _ulist.clear(); |
| 370 |
2/2✓ Branch 0 taken 30 times.
✓ Branch 1 taken 15 times.
|
45 | for (auto & _component : _components) { |
| 371 |
5/8✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 30 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 60 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 30 times.
✓ Branch 14 taken 30 times.
|
60 | for (auto & li : _component) { |
| 372 |
4/6✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 30 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 104 times.
✓ Branch 9 taken 30 times.
|
164 | for (auto & k : li.xlist) { |
| 373 |
1/2✓ Branch 1 taken 104 times.
✗ Branch 2 not taken.
|
104 | _ulist.push_back(k); |
| 374 | } | ||
| 375 | } | ||
| 376 | } | ||
| 377 | |||
| 378 | 15 | unsigned n_processed = 0; | |
| 379 | |||
| 380 | while (true) { | ||
| 381 | // get unprocessed intersection | ||
| 382 |
3/4✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 23 times.
|
38 | if (_ulist.empty()) break; |
| 383 |
1/2✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
|
23 | IntersectionVertex &iv = _ulist.front(); |
| 384 | 23 | unsigned w = iv.which; | |
| 385 |
2/4✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 23 times.
✗ Branch 6 not taken.
|
23 | ILIter i = _components[w][iv.pos.path_index].xlist.iterator_to(iv); |
| 386 | |||
| 387 |
2/4✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 23 times.
✗ Branch 6 not taken.
|
46 | result.push_back(Path(i->p)); |
| 388 | 23 | result.back().setStitching(true); | |
| 389 | 23 | bool reverse = false; ///< Whether to traverse the current component in the backwards direction. | |
| 390 |
2/2✓ Branch 1 taken 52 times.
✓ Branch 2 taken 23 times.
|
173 | while (i->_proc_hook.is_linked()) { |
| 391 | 52 | ILIter prev = i; | |
| 392 | 52 | std::size_t pi = i->pos.path_index; ///< Index of the path in its PathVector | |
| 393 | // determine which direction to go | ||
| 394 | // union: always go outside | ||
| 395 | // intersection: always go inside | ||
| 396 | // a minus b: go inside in b, outside in a | ||
| 397 | // b minus a: go inside in a, outside in b | ||
| 398 |
2/2✓ Branch 0 taken 26 times.
✓ Branch 1 taken 26 times.
|
52 | if (w == 0) { // The path we're on is a part of A |
| 399 | 26 | reverse = (i->next_edge == INSIDE) ^ enter_a; | |
| 400 | } else { // The path we're on is a part of B | ||
| 401 | 26 | reverse = (i->next_edge == INSIDE) ^ enter_b; | |
| 402 | } | ||
| 403 | |||
| 404 | // get next intersection | ||
| 405 |
2/2✓ Branch 0 taken 30 times.
✓ Branch 1 taken 22 times.
|
52 | if (reverse) { |
| 406 |
2/4✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 30 times.
✗ Branch 7 not taken.
|
90 | i = cyclic_prior(i, _components[w][pi].xlist); |
| 407 | } else { | ||
| 408 |
2/4✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 22 times.
✗ Branch 7 not taken.
|
66 | i = cyclic_next(i, _components[w][pi].xlist); |
| 409 | } | ||
| 410 | |||
| 411 | // append portion of path to the result | ||
| 412 |
2/4✓ Branch 2 taken 52 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 52 times.
✗ Branch 6 not taken.
|
156 | PathInterval ival = PathInterval::from_direction( |
| 413 | 104 | prev->pos.asPathTime(), i->pos.asPathTime(), | |
| 414 | 52 | reverse, _pv[i->which][pi].size()); | |
| 415 | |||
| 416 |
1/2✓ Branch 7 taken 52 times.
✗ Branch 8 not taken.
|
156 | _pv[i->which][pi].appendPortionTo(result.back(), ival, prev->p, i->p); |
| 417 | |||
| 418 | // count both vertices as processed | ||
| 419 | 52 | n_processed += 2; | |
| 420 |
1/2✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
|
104 | if (prev->_proc_hook.is_linked()) { |
| 421 |
2/4✓ Branch 4 taken 52 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 52 times.
✗ Branch 8 not taken.
|
156 | _ulist.erase(_ulist.iterator_to(*prev)); |
| 422 | } | ||
| 423 |
1/2✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
|
104 | if (i->_proc_hook.is_linked()) { |
| 424 |
2/4✓ Branch 4 taken 52 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 52 times.
✗ Branch 8 not taken.
|
156 | _ulist.erase(_ulist.iterator_to(*i)); |
| 425 | } | ||
| 426 | |||
| 427 | // switch to the other path | ||
| 428 |
1/2✓ Branch 3 taken 52 times.
✗ Branch 4 not taken.
|
156 | i = _getNeighbor(i); |
| 429 | 52 | w = i->which; | |
| 430 | } | ||
| 431 |
1/2✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
|
23 | result.back().close(true); |
| 432 |
2/2✓ Branch 0 taken 18 times.
✓ Branch 1 taken 5 times.
|
23 | if (reverse){ |
| 433 |
1/2✓ Branch 3 taken 18 times.
✗ Branch 4 not taken.
|
18 | result.back() = result.back().reversed(); |
| 434 | } | ||
| 435 |
2/4✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 23 times.
|
23 | if (result.back().empty()) { |
| 436 | // std::cerr << "Path is empty" << std::endl; | ||
| 437 | ✗ | throw GEOM_ERR_INTERSECGRAPH; | |
| 438 | } | ||
| 439 | 23 | } | |
| 440 | |||
| 441 |
2/4✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 15 times.
|
15 | if (n_processed != size() * 2) { |
| 442 | // std::cerr << "Processed " << n_processed << " intersections, expected " << (size() * 2) << std::endl; | ||
| 443 | ✗ | throw GEOM_ERR_INTERSECGRAPH; | |
| 444 | } | ||
| 445 | |||
| 446 | 15 | return result; | |
| 447 | ✗ | } | |
| 448 | |||
| 449 | /** @brief Select intersection-free path components ahead of a boolean operation based on whether | ||
| 450 | * they should be a part of that operation's result. | ||
| 451 | * | ||
| 452 | * Every component that has intersections will be processed by _getResult(). | ||
| 453 | * Here we take care of paths that don't have any intersections. They are either | ||
| 454 | * completely inside or completely outside the other path-vector. | ||
| 455 | * | ||
| 456 | * @param result – output parameter to store the selected components. | ||
| 457 | * @param which – which of the two operands to search for intersection-free paths. | ||
| 458 | * @param inside – If set to true, add paths entirely contained inside the other path-vector to | ||
| 459 | * the result. If set to false, add paths entirely outside of the other path-vector instead. | ||
| 460 | */ | ||
| 461 | 42 | void PathIntersectionGraph::_handleNonintersectingPaths(PathVector &result, unsigned which, bool inside) | |
| 462 | { | ||
| 463 | 42 | unsigned w = which; | |
| 464 | 42 | unsigned ow = (w+1) % 2; | |
| 465 | |||
| 466 |
2/2✓ Branch 1 taken 38 times.
✓ Branch 2 taken 42 times.
|
80 | for (std::size_t i = 0; i < _pv[w].size(); ++i) { |
| 467 | // the path data vector might have been left empty if there were no intersections at all | ||
| 468 | 38 | bool has_path_data = !_components[w].empty(); | |
| 469 | // Skip if the path has intersections | ||
| 470 |
6/6✓ Branch 0 taken 30 times.
✓ Branch 1 taken 8 times.
✓ Branch 4 taken 22 times.
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 22 times.
✓ Branch 7 taken 16 times.
|
38 | if (has_path_data && !_components[w][i].xlist.empty()) continue; |
| 471 | 16 | bool path_inside = false; | |
| 472 | |||
| 473 | // Use the status flag set in the constructor if available. | ||
| 474 |
6/6✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 4 times.
✓ Branch 5 taken 4 times.
✓ Branch 6 taken 12 times.
|
16 | if (has_path_data && _components[w][i].status == INSIDE) { |
| 475 | 4 | path_inside = true; | |
| 476 |
5/6✓ Branch 0 taken 4 times.
✓ Branch 1 taken 8 times.
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 4 times.
✓ Branch 6 taken 8 times.
|
12 | } else if (has_path_data && _components[w][i].status == OUTSIDE) { |
| 477 | 4 | path_inside = false; | |
| 478 | } else { | ||
| 479 | // The status flag is ambiguous: we evaluate the winding number of the initial point. | ||
| 480 |
2/4✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
|
8 | int wdg = _pv[ow].winding(_pv[w][i].initialPoint()); |
| 481 | 8 | path_inside = wdg % 2 != 0; | |
| 482 | } | ||
| 483 | |||
| 484 |
2/2✓ Branch 0 taken 9 times.
✓ Branch 1 taken 7 times.
|
16 | if (path_inside == inside) { |
| 485 | 9 | result.push_back(_pv[w][i]); | |
| 486 | } | ||
| 487 | } | ||
| 488 | 42 | } | |
| 489 | |||
| 490 | /** @brief Get an iterator to the corresponding crossing on the other path-vector. | ||
| 491 | * | ||
| 492 | * @param ILIter – an iterator to a list of intersections in one of the path-vectors. | ||
| 493 | * @return An iterator to the corresponding intersection in the other path-vector. | ||
| 494 | */ | ||
| 495 | 56 | PathIntersectionGraph::ILIter PathIntersectionGraph::_getNeighbor(ILIter iter) | |
| 496 | { | ||
| 497 | 56 | unsigned ow = (iter->which + 1) % 2; | |
| 498 | 168 | return _components[ow][iter->neighbor->pos.path_index].xlist.iterator_to(*iter->neighbor); | |
| 499 | } | ||
| 500 | |||
| 501 | /** Get the path data for the path containing the intersection given an iterator to the intersection */ | ||
| 502 | PathIntersectionGraph::PathData & | ||
| 503 | 4 | PathIntersectionGraph::_getPathData(ILIter iter) | |
| 504 | { | ||
| 505 | 8 | return _components[iter->which][iter->pos.path_index]; | |
| 506 | } | ||
| 507 | |||
| 508 | /** Format the PathIntersectionGraph for output. */ | ||
| 509 | ✗ | std::ostream &operator<<(std::ostream &os, PathIntersectionGraph const &pig) | |
| 510 | { | ||
| 511 | ✗ | os << "Intersection graph:\n" | |
| 512 | ✗ | << pig._xs.size()/2 << " total intersections\n" | |
| 513 | ✗ | << pig.size() << " considered intersections\n"; | |
| 514 | ✗ | for (std::size_t i = 0; i < pig._components[0].size(); ++i) { | |
| 515 | ✗ | PathIntersectionGraph::IntersectionList const &xl = pig._components[0][i].xlist; | |
| 516 | ✗ | for (const auto & j : xl) { | |
| 517 | ✗ | os << j.pos << " - " << j.neighbor->pos << " @ " << j.p << "\n"; | |
| 518 | } | ||
| 519 | } | ||
| 520 | ✗ | return os; | |
| 521 | } | ||
| 522 | |||
| 523 | } // namespace Geom | ||
| 524 | |||
| 525 | /* | ||
| 526 | Local Variables: | ||
| 527 | mode:c++ | ||
| 528 | c-file-style:"stroustrup" | ||
| 529 | c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) | ||
| 530 | indent-tabs-mode:nil | ||
| 531 | fill-column:99 | ||
| 532 | End: | ||
| 533 | */ | ||
| 534 | // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : | ||
| 535 | |||
| 536 |