GCC Code Coverage Report

Directory: ./
File: src/2geom/self-intersect.cpp
Date: 2024-03-18 17:01:34
Exec Total Coverage
Lines: 119 121 98.3%
Functions: 23 23 100.0%
Branches: 101 156 64.7%
Line Branch Exec Source
1 /**
2 * @file Implementation of Path::intersectSelf() and PathVector::intersectSelf().
3 */
4 /* An algorithm for finding self-intersections of paths and path-vectors.
5 *
6 * Authors:
7 * Rafał Siejakowski <rs@rs-math.net>
8 *
9 * (C) Copyright 2022 Authors
10 *
11 * This library is free software; you can redistribute it and/or
12 * modify it either under the terms of the GNU Lesser General Public
13 * License version 2.1 as published by the Free Software Foundation
14 * (the "LGPL") or, at your option, under the terms of the Mozilla
15 * Public License Version 1.1 (the "MPL"). If you do not alter this
16 * notice, a recipient may use your version of this file under either
17 * the MPL or the LGPL.
18 *
19 * You should have received a copy of the LGPL along with this library
20 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 * You should have received a copy of the MPL along with this library
23 * in the file COPYING-MPL-1.1
24 *
25 * The contents of this file are subject to the Mozilla Public License
26 * Version 1.1 (the "License"); you may not use this file except in
27 * compliance with the License. You may obtain a copy of the License at
28 * http://www.mozilla.org/MPL/
29 *
30 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
31 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
32 * the specific language governing rights and limitations.
33 */
34
35 #include <list>
36
37 #include <2geom/coord.h>
38 #include <2geom/curve.h>
39 #include <2geom/path.h>
40 #include <2geom/pathvector.h>
41 #include <2geom/point.h>
42 #include <2geom/sweeper.h>
43
44 namespace Geom {
45
46 /** @brief The PathSelfIntersector class is a sweepset class used for intersecting curves in the
47 * same path with one another. It is intended to be used as the template parameter of Sweeper.
48 */
49 class PathSelfIntersector
50 {
51 public:
52 using ItemIterator = Path::iterator;
53
54 private:
55 Path _path; ///< The path searched for self-crossings, cleaned of degenerate curves.
56 std::list<ItemIterator> _active; ///< List of active curves during the sweepline passage.
57 std::vector<PathIntersection> _crossings; ///< Stores the crossings found.
58 std::vector<size_t> _original_indices; ///< Curve indices before removal of degenerate curves.
59 double const _precision; ///< Numerical epsilon.
60
61 public:
62 22 PathSelfIntersector(Path const &path, double precision)
63
2/4
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 22 times.
✗ Branch 6 not taken.
 22 : _path{path.initialPoint()}
64 22 , _precision{precision}
65 {
66
2/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
 22 _original_indices.reserve(path.size());
67
3/4
✓ Branch 2 taken 97 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 75 times.
✓ Branch 5 taken 22 times.
 97 for (size_t i = 0; i < path.size(); i++) {
68
4/6
✓ Branch 1 taken 75 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 75 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 68 times.
✓ Branch 7 taken 7 times.
 75 if (!path[i].isDegenerate()) {
69
2/4
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 68 times.
✗ Branch 5 not taken.
 68 _path.append(path[i]);
70
1/2
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
 68 _original_indices.push_back(i);
71 }
72 }
73
1/2
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
 22 _path.close(path.closed());
74 22 }
75
76 // === SweepSet API ===
77 110 auto &items() { return _path; }
78
2/4
✓ Branch 2 taken 68 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 68 times.
✗ Branch 6 not taken.
 68 Interval itemBounds(ItemIterator curve) const { return curve->boundsFast()[X]; }
79 /// Callback for when the sweepline starts intersecting a new item.
80 68 void addActiveItem(ItemIterator incoming)
81 {
82 68 _intersectWithActive(incoming);
83 68 _intersectWithSelf(incoming);
84 68 _active.push_back(incoming);
85 68 }
86 /// Callback for when the sweepline stops intersecting an item.
87 68 void removeActiveItem(ItemIterator to_remove)
88 {
89
1/2
✓ Branch 4 taken 68 times.
✗ Branch 5 not taken.
 68 auto it = std::find(_active.begin(), _active.end(), to_remove);
90 68 _active.erase(it);
91 68 }
92 // ===
93
94 22 std::vector<PathIntersection> &&moveOutCrossings() { return std::move(_crossings); }
95
96 private:
97 /** Find and store all intersections of a curve with itself. */
98 68 void _intersectWithSelf(ItemIterator curve)
99 {
100 68 size_t const index = std::distance(_path.begin(), curve);
101
4/6
✓ Branch 2 taken 68 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 68 times.
✗ Branch 6 not taken.
✓ Branch 14 taken 2 times.
✓ Branch 15 taken 68 times.
 70 for (auto &&self_x : curve->intersectSelf(_precision)) {
102
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 _appendCurveCrossing(std::move(self_x), index, index);
103 68 }
104 68 }
105
106 /** Find and store all intersections of a curve with the active curves. */
107 68 void _intersectWithActive(ItemIterator curve)
108 {
109
1/2
✓ Branch 2 taken 68 times.
✗ Branch 3 not taken.
 68 size_t const index = std::distance(_path.begin(), curve);
110
2/2
✓ Branch 7 taken 73 times.
✓ Branch 8 taken 68 times.
 141 for (auto const &other : _active) {
111
7/12
✓ Branch 2 taken 73 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 73 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 73 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 73 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 73 times.
✗ Branch 16 not taken.
✓ Branch 19 taken 9 times.
✓ Branch 20 taken 64 times.
 73 if (!curve->boundsFast().intersects(other->boundsFast())) {
112 9 continue;
113 }
114
115
1/2
✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
 64 size_t const other_index = std::distance(_path.begin(), other);
116 64 auto const &[smaller, larger] = std::minmax(index, other_index);
117 /// Whether the curves meet at a common node in the path.
118 64 bool consecutive = smaller + 1 == larger;
119 /// Whether the curves meet at the closure point of the path.
120
7/8
✓ Branch 1 taken 57 times.
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 30 times.
✓ Branch 6 taken 27 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 14 times.
✓ Branch 9 taken 13 times.
 64 bool wraparound = _path.closed() && smaller == 0 && larger + 1 == _path.size();
121
5/8
✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 64 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 64 times.
✗ Branch 9 not taken.
✓ Branch 17 taken 78 times.
✓ Branch 18 taken 64 times.
 142 for (auto &&xing : curve->intersect(*other, _precision)) {
122
1/2
✓ Branch 2 taken 78 times.
✗ Branch 3 not taken.
 78 _appendCurveCrossing(std::move(xing), index, other_index, consecutive, wraparound);
123 64 }
124 }
125 68 }
126
127 /** Append a curve crossing to the store as long as it satisfies nondegeneracy criteria. */
128 80 void _appendCurveCrossing(CurveIntersection &&xing, size_t first_index, size_t second_index,
129 bool consecutive = false, bool wraparound = false)
130 {
131 // Filter out crossings that aren't real but rather represent the agreement of final
132 // and initial points of consecutive curves – a consequence of the path's continuity.
133 80 auto const should_exclude = [&](bool flipped) -> bool {
134 // Filter out spurious self-intersections by using squared geometric average.
135 74 bool const first_is_first = (first_index < second_index) ^ flipped;
136
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 35 times.
 74 double const geom2 = first_is_first ? (1.0 - xing.first) * xing.second
137 35 : (1.0 - xing.second) * xing.first;
138 74 return geom2 < EPSILON;
139 80 };
140
141
10/10
✓ Branch 0 taken 58 times.
✓ Branch 1 taken 22 times.
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 49 times.
✓ Branch 5 taken 16 times.
✓ Branch 6 taken 15 times.
✓ Branch 8 taken 15 times.
✓ Branch 9 taken 1 times.
✓ Branch 10 taken 64 times.
✓ Branch 11 taken 16 times.
 80 if ((consecutive && should_exclude(false)) || (wraparound && should_exclude(true))) {
142 64 return;
143 }
144
145 // Convert curve indices to the original ones (before the removal of degenerate curves).
146
1/2
✓ Branch 6 taken 16 times.
✗ Branch 7 not taken.
 48 _crossings.emplace_back(PathTime(_original_indices[first_index], xing.first),
147 32 PathTime(_original_indices[second_index], xing.second),
148 32 xing.point());
149 }
150 };
151
152 // Compute all crossings of a path with itself.
153 22 std::vector<PathIntersection> Path::intersectSelf(Coord precision) const
154 {
155
1/2
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
 22 auto intersector = PathSelfIntersector(*this, precision);
156
2/4
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 22 times.
✗ Branch 6 not taken.
 22 Sweeper(intersector).process();
157 22 auto result = intersector.moveOutCrossings();
158
1/2
✓ Branch 3 taken 22 times.
✗ Branch 4 not taken.
 22 std::sort(result.begin(), result.end());
159 44 return result;
160 22 }
161
162 /**
163 * @brief The PathVectorSelfIntersector class is an implementation of a SweepSet whose intended
164 * use is the search for self-intersections in a single PathVector. It's designed to be used as
165 * the template parameter for the Sweeper class template.
166 */
167 class PathVectorSelfIntersector
168 {
169 public:
170 using ItemIterator = PathVector::const_iterator;
171
172 private:
173 PathVector const &_pathvector; ///< A reference to the path-vector searched for self-crossings.
174 std::list<ItemIterator> _active; ///< A list of active paths during sweepline passage.
175 std::vector<PathVectorIntersection> _crossings; ///< Stores the crossings found.
176 double const _precision; ///< Numerical epsilon.
177
178 public:
179 12 PathVectorSelfIntersector(PathVector const &subject, double precision)
180 12 : _pathvector{subject}
181 12 , _precision{precision}
182 {
183 12 }
184
185 // == SweepSet API ===
186 58 auto const &items() { return _pathvector; }
187 14 Interval itemBounds(ItemIterator path)
188 {
189
1/2
✓ Branch 3 taken 14 times.
✗ Branch 4 not taken.
 14 auto const r = path->boundsFast();
190
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 28 return r ? (*r)[X] : Interval(); // Sweeplines are vertical
191 }
192
193 /// Callback for when the sweepline starts intersecting a new item.
194 14 void addActiveItem(ItemIterator incoming)
195 {
196 14 _intersectWithActive(incoming);
197 14 _intersectWithSelf(incoming);
198 14 _active.push_back(incoming);
199 14 }
200
201 /// Callback for when the sweepline stops intersecting an item.
202 14 void removeActiveItem(ItemIterator to_remove)
203 {
204
1/2
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
 14 auto it = std::find(_active.begin(), _active.end(), to_remove);
205 14 _active.erase(it);
206 14 }
207 // ===
208
209 12 std::vector<PathVectorIntersection> &&moveOutCrossings() { return std::move(_crossings); }
210
211 private:
212 /**
213 * @brief Find all intersections of the path pointed to by the given
214 * iterator with all currently active paths and store results
215 * in the instance of the class.
216 *
217 * @param it An iterator to a path to be intersected with the active ones.
218 */
219 void _intersectWithActive(ItemIterator &it);
220
221 /**
222 * @brief Find all intersections of the path pointed to by the given
223 * iterator with itself and store the results in the class instance.
224 *
225 * @param it An iterator to a path which will be intersected with itself.
226 */
227 void _intersectWithSelf(ItemIterator &it);
228
229 /// Append a path crossing to the store.
230 10 void _appendPathCrossing(PathIntersection const &xing, size_t first_index, size_t second_index)
231 {
232 10 auto const first_time = PathVectorTime(first_index, xing.first);
233 10 auto const second_time = PathVectorTime(second_index, xing.second);
234
1/2
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
 10 _crossings.emplace_back(first_time, second_time, xing.point());
235 10 }
236
237 public:
238
239 std::vector<PathVectorIntersection>
240 filterDeduplicate(std::vector<PathVectorIntersection> &&xings) const;
241 };
242
243 /** Remove duplicate intersections (artifacts of the path/curve crossing algorithms). */
244 std::vector<PathVectorIntersection>
245 3 PathVectorSelfIntersector::filterDeduplicate(std::vector<PathVectorIntersection> &&xings) const
246 {
247 3 std::vector<PathVectorIntersection> result;
248
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 result.reserve(xings.size());
249
250 3 auto const are_same_times = [&](Coord a1, Coord a2, Coord b1, Coord b2) -> bool {
251
5/6
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 6 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 5 times.
 15 return (are_near(a1, b1) && are_near(a2, b2)) ||
252
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 15 (are_near(a1, b2) && are_near(a2, b1));
253 };
254
255 3 Coord last_time_1 = -1.0, last_time_2 = -1.0; // Invalid path times
256
2/2
✓ Branch 6 taken 8 times.
✓ Branch 7 taken 3 times.
 11 for (auto &&x : xings) {
257 8 auto const current_1 = x.first.asFlatTime(), current_2 = x.second.asFlatTime();
258
2/2
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 3 times.
 8 if (!are_same_times(current_1, current_2, last_time_1, last_time_2)) {
259
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 result.push_back(std::move(x));
260 }
261 8 last_time_1 = current_1;
262 8 last_time_2 = current_2;
263 }
264
265 3 return result;
266 ✗ }
267
268 /** Compute and store intersections of a path with all active paths. */
269 14 void PathVectorSelfIntersector::_intersectWithActive(ItemIterator &it)
270 {
271 14 auto const start = _pathvector.begin();
272
2/2
✓ Branch 7 taken 2 times.
✓ Branch 8 taken 14 times.
 16 for (auto &path : _active) {
273
4/8
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 2 times.
✗ Branch 12 not taken.
✗ Branch 15 not taken.
✓ Branch 16 taken 2 times.
 2 if (!path->boundsFast().intersects(it->boundsFast())) {
274 ✗ continue;
275 }
276
3/4
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 13 taken 4 times.
✓ Branch 14 taken 2 times.
 6 for (auto &&xing : path->intersect(*it, _precision)) {
277
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 _appendPathCrossing(std::move(xing), std::distance(start, path),
278 4 std::distance(start, it));
279 2 }
280 }
281 14 }
282
283 /** Compute and store intersections of a constituent path with itself. */
284 14 void PathVectorSelfIntersector::_intersectWithSelf(ItemIterator &it)
285 {
286 14 size_t const path_index = std::distance(_pathvector.begin(), it);
287
3/4
✓ Branch 3 taken 14 times.
✗ Branch 4 not taken.
✓ Branch 12 taken 6 times.
✓ Branch 13 taken 14 times.
 20 for (auto &&xing : it->intersectSelf(_precision)) {
288
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 _appendPathCrossing(std::move(xing), path_index, path_index);
289 14 }
290 14 }
291
292 // Compute self-intersections in a path-vector.
293 12 std::vector<PathVectorIntersection> PathVector::intersectSelf(Coord precision) const
294 {
295 12 auto intersector = PathVectorSelfIntersector(*this, precision);
296
2/4
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 12 times.
✗ Branch 6 not taken.
 12 Sweeper(intersector).process();
297 12 auto result = intersector.moveOutCrossings();
298
1/2
✓ Branch 3 taken 12 times.
✗ Branch 4 not taken.
 12 std::sort(result.begin(), result.end());
299
4/6
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 9 times.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 9 times.
✗ Branch 9 not taken.
 24 return (result.size() > 1) ? intersector.filterDeduplicate(std::move(result)) : result;
300 12 }
301
302 } // namespace Geom
303
304 /*
305 Local Variables:
306 mode:c++
307 c-file-style:"stroustrup"
308 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
309 indent-tabs-mode:nil
310 fill-column:99
311 End:
312 */
313 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
314