GCC Code Coverage Report

Directory: ./
File: include/2geom/path.h
Date: 2024-03-18 17:01:34
Exec Total Coverage
Lines: 112 164 68.3%
Functions: 60 77 77.9%
Branches: 49 196 25.0%
Line Branch Exec Source
1 /** @file
2 * @brief Path - a sequence of contiguous curves
3 *//*
4 * Authors:
5 * MenTaLguY <mental@rydia.net>
6 * Marco Cecchetti <mrcekets at gmail.com>
7 * Krzysztof Kosiński <tweenk.pl@gmail.com>
8 *
9 * Copyright 2007-2014 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 #ifndef LIB2GEOM_SEEN_PATH_H
36 #define LIB2GEOM_SEEN_PATH_H
37
38 #include <cstddef>
39 #include <iterator>
40 #include <algorithm>
41 #include <iostream>
42 #include <memory>
43 #include <optional>
44 #include <utility>
45 #include <vector>
46
47 #include <boost/operators.hpp>
48 #include <boost/ptr_container/ptr_vector.hpp>
49
50 #include <2geom/intersection.h>
51 #include <2geom/curve.h>
52 #include <2geom/bezier-curve.h>
53 #include <2geom/transforms.h>
54
55 namespace Geom {
56
57 class Path;
58 class ConvexHull;
59
60 namespace PathInternal {
61
62 typedef boost::ptr_vector<Curve> Sequence;
63
64 struct PathData {
65 Sequence curves;
66 OptRect fast_bounds;
67 };
68
69 template <typename P>
70 class BaseIterator
71 : public boost::random_access_iterator_helper
72 < BaseIterator<P>
73 , Curve const
74 , std::ptrdiff_t
75 , Curve const *
76 , Curve const &
77 >
78 {
79 protected:
80 313 BaseIterator(P &p, unsigned i) : path(&p), index(i) {}
81 // default copy, default assign
82 typedef BaseIterator<P> Self;
83
84 public:
85 44 BaseIterator() : path(NULL), index(0) {}
86
87 bool operator<(BaseIterator const &other) const {
88 return path == other.path && index < other.index;
89 }
90 480 bool operator==(BaseIterator const &other) const {
91
3/4
✓ Branch 0 taken 480 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 110 times.
✓ Branch 3 taken 370 times.
 480 return path == other.path && index == other.index;
92 }
93 885 Curve const &operator*() const {
94 885 return (*path)[index];
95 }
96
97 341 Self &operator++() {
98 341 ++index;
99 341 return *this;
100 }
101 ✗ Self &operator--() {
102 ✗ --index;
103 ✗ return *this;
104 }
105 ✗ Self &operator+=(std::ptrdiff_t d) {
106 ✗ index += d;
107 ✗ return *this;
108 }
109 Self &operator-=(std::ptrdiff_t d) {
110 index -= d;
111 return *this;
112 }
113 222 std::ptrdiff_t operator-(Self const &other) const {
114
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 222 times.
 222 assert(path == other.path);
115 222 return (std::ptrdiff_t)index - (std::ptrdiff_t)other.index;
116 }
117
118 private:
119 P *path;
120 unsigned index;
121
122 friend class ::Geom::Path;
123 };
124
125 }
126
127 /** @brief Generalized time value in the path.
128 *
129 * This class exists because when mapping the range of multiple curves onto the same interval
130 * as the curve index, we lose some precision. For instance, a path with 16 curves will
131 * have 4 bits less precision than a path with 1 curve. If you need high precision results
132 * in long paths, either use this class and related methods instead of the standard methods
133 * pointAt(), nearestTime() and so on, or use curveAt() to first obtain the curve, then
134 * call the method again to obtain a high precision result.
135 *
136 * @ingroup Paths */
137 struct PathTime
138 : boost::totally_ordered<PathTime>
139 {
140 typedef PathInternal::Sequence::size_type size_type;
141
142 Coord t; ///< Time value in the curve
143 size_type curve_index; ///< Index of the curve in the path
144
145 236 PathTime() : t(0), curve_index(0) {}
146 404 PathTime(size_type idx, Coord tval) : t(tval), curve_index(idx) {}
147
148 719 bool operator<(PathTime const &other) const {
149
2/2
✓ Branch 0 taken 174 times.
✓ Branch 1 taken 545 times.
 719 if (curve_index < other.curve_index) return true;
150
2/2
✓ Branch 0 taken 271 times.
✓ Branch 1 taken 274 times.
 545 if (curve_index == other.curve_index) {
151 271 return t < other.t;
152 }
153 274 return false;
154 }
155 542 bool operator==(PathTime const &other) const {
156
4/4
✓ Branch 0 taken 221 times.
✓ Branch 1 taken 321 times.
✓ Branch 2 taken 41 times.
✓ Branch 3 taken 180 times.
 542 return curve_index == other.curve_index && t == other.t;
157 }
158 /// Convert times at or beyond 1 to 0 on the next curve.
159 222 void normalizeForward(size_type path_size) {
160
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 204 times.
 222 if (t >= 1) {
161 18 curve_index = (curve_index + 1) % path_size;
162 18 t = 0;
163 }
164 222 }
165 /// Convert times at or before 0 to 1 on the previous curve.
166 146 void normalizeBackward(size_type path_size) {
167
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 125 times.
 146 if (t <= 0) {
168 21 curve_index = (curve_index - 1) % path_size;
169 21 t = 1;
170 }
171 146 }
172
173 16 Coord asFlatTime() const { return curve_index + t; }
174 };
175
176 ✗ inline std::ostream &operator<<(std::ostream &os, PathTime const &pos) {
177 ✗ os << pos.curve_index << ": " << format_coord_nice(pos.t);
178 ✗ return os;
179 }
180
181
182 /** @brief Contiguous subset of the path's parameter domain.
183 * This is a directed interval, which allows one to specify any contiguous subset
184 * of the path's domain, including subsets that wrap around the initial point
185 * of the path.
186 * @ingroup Paths */
187 class PathInterval {
188 public:
189 typedef PathInternal::Sequence::size_type size_type;
190
191 /** @brief Default interval.
192 * Default-constructed PathInterval includes only the initial point of the initial segment. */
193 PathInterval();
194
195 /** @brief Construct an interval in the path's parameter domain.
196 * @param from Initial time
197 * @param to Final time
198 * @param cross_start If true, the interval will proceed from the initial to final
199 * time through the initial point of the path, wrapping around the closing segment;
200 * otherwise it will not wrap around the closing segment.
201 * @param path_size Size of the path to which this interval applies, required
202 * to clean up degenerate cases */
203 PathInterval(PathTime const &from, PathTime const &to, bool cross_start, size_type path_size);
204
205 /// Get the time value of the initial point.
206 PathTime const &initialTime() const { return _from; }
207 /// Get the time value of the final point.
208 PathTime const &finalTime() const { return _to; }
209
210 82 PathTime const &from() const { return _from; }
211 82 PathTime const &to() const { return _to; }
212
213 /// Check whether the interval has only one point.
214 102 bool isDegenerate() const { return _from == _to; }
215 /// True if the interval goes in the direction of decreasing time values.
216 59 bool reverse() const { return _reverse; }
217 /// True if the interior of the interval contains the initial point of the path.
218 82 bool crossesStart() const { return _cross_start; }
219
220 /// Test a path time for inclusion.
221 bool contains(PathTime const &pos) const;
222
223 /// Get a time at least @a min_dist away in parameter space from the ends.
224 /// If no such time exists, the middle point is returned.
225 PathTime inside(Coord min_dist = EPSILON) const;
226
227 /// Select one of two intervals with given endpoints by parameter direction.
228 static PathInterval from_direction(PathTime const &from, PathTime const &to,
229 bool reversed, size_type path_size);
230
231 /// Select one of two intervals with given endpoints by whether it includes the initial point.
232 static PathInterval from_start_crossing(PathTime const &from, PathTime const &to,
233 bool cross_start, size_type path_size) {
234 PathInterval result(from, to, cross_start, path_size);
235 return result;
236 }
237
238 82 size_type pathSize() const { return _path_size; }
239 size_type curveCount() const;
240
241 private:
242 PathTime _from, _to;
243 size_type _path_size;
244 bool _cross_start, _reverse;
245 };
246
247 /// Create an interval in the direction of increasing time value.
248 /// @relates PathInterval
249 44 inline PathInterval forward_interval(PathTime const &from, PathTime const &to,
250 PathInterval::size_type path_size)
251 {
252 44 PathInterval result = PathInterval::from_direction(from, to, false, path_size);
253 44 return result;
254 }
255
256 /// Create an interval in the direction of decreasing time value.
257 /// @relates PathInterval
258 inline PathInterval backward_interval(PathTime const &from, PathTime const &to,
259 PathInterval::size_type path_size)
260 {
261 PathInterval result = PathInterval::from_direction(from, to, true, path_size);
262 return result;
263 }
264
265 /// Output an interval in the path's domain.
266 /// @relates PathInterval
267 inline std::ostream &operator<<(std::ostream &os, PathInterval const &ival) {
268 os << "PathInterval[";
269 if (ival.crossesStart()) {
270 os << ival.from() << " -> 0: 0.0 -> " << ival.to();
271 } else {
272 os << ival.from() << " -> " << ival.to();
273 }
274 os << "]";
275 return os;
276 }
277
278 typedef Intersection<PathTime> PathIntersection;
279
280 template <>
281 struct ShapeTraits<Path> {
282 typedef PathTime TimeType;
283 typedef PathInterval IntervalType;
284 typedef Path AffineClosureType;
285 typedef PathIntersection IntersectionType;
286 };
287
288 /** @brief Stores information about the extremum points on a path, with respect
289 * to one of the coordinate axes.
290 * @relates Path::extrema()
291 */
292 struct PathExtrema {
293 /** Points with the minimum and maximum value of a coordinate. */
294 Point min_point, max_point;
295
296 /** Directions in which the OTHER coordinates change at the extremum points.
297 *
298 * - equals +1.0 if the other coordinate increases,
299 * - equals 0.0 if the other coordinate is constant (e.g., for an axis-aligned segment),
300 * - equals -1.0 if the other coordinate decreases.
301 */
302 float glance_direction_at_min, glance_direction_at_max;
303
304 /** Path times corresponding to minimum and maximum points. */
305 PathTime min_time, max_time;
306 };
307
308 /** @brief Sequence of contiguous curves, aka spline.
309 *
310 * Path represents a sequence of contiguous curves, also known as a spline.
311 * It corresponds to a "subpath" in SVG terminology. It can represent both
312 * open and closed subpaths. The final point of each curve is exactly
313 * equal to the initial point of the next curve.
314 *
315 * The path always contains a linear closing segment that connects
316 * the final point of the last "real" curve to the initial point of the
317 * first curve. This way the curves form a closed loop even for open paths.
318 * If the closing segment has nonzero length and the path is closed, it is
319 * considered a normal part of the path data. There are three distinct sets
320 * of end iterators one can use to iterate over the segments:
321 *
322 * - Iterating between @a begin() and @a end() will iterate over segments
323 * which are part of the path.
324 * - Iterating between @a begin() and @a end_closed()
325 * will always iterate over a closed loop of segments.
326 * - Iterating between @a begin() and @a end_open() will always skip
327 * the final linear closing segment.
328 *
329 * If the final point of the last "real" segment coincides exactly with the initial
330 * point of the first segment, the closing segment will be absent from both
331 * [begin(), end_open()) and [begin(), end_closed()).
332 *
333 * Normally, an exception will be thrown when you try to insert a curve
334 * that makes the path non-continuous. If you are working with unsanitized
335 * curve data, you can call setStitching(true), which will insert line segments
336 * to make the path continuous.
337 *
338 * Internally, Path uses copy-on-write data. This is done for two reasons: first,
339 * copying a Curve requires calling a virtual function, so it's a little more expensive
340 * that normal copying; and second, it reduces the memory cost of copying the path.
341 * Therefore you can return Path and PathVector from functions without worrying
342 * about temporary copies.
343 *
344 * Note that this class cannot represent arbitrary shapes, which may contain holes.
345 * To do that, use PathVector, which is more generic.
346 *
347 * It's not very convenient to create a Path directly. To construct paths more easily,
348 * use PathBuilder.
349 *
350 * @ingroup Paths */
351 class Path
352 : boost::equality_comparable< Path >
353 {
354 public:
355 typedef PathInternal::PathData PathData;
356 typedef PathInternal::Sequence Sequence;
357 typedef PathInternal::BaseIterator<Path> iterator;
358 typedef PathInternal::BaseIterator<Path const> const_iterator;
359 typedef Sequence::size_type size_type;
360 typedef Sequence::difference_type difference_type;
361
362 class ClosingSegment : public LineSegment {
363 public:
364 ClosingSegment() : LineSegment() {}
365 341715 ClosingSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
366
1/4
✓ Branch 2 taken 861 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 861 Curve *duplicate() const override { return new ClosingSegment(*this); }
367
3/8
✓ Branch 3 taken 164700 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 164700 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 164700 times.
✗ Branch 11 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
 164700 Curve *reverse() const override { return new ClosingSegment((*this)[1], (*this)[0]); }
368 };
369
370 class StitchSegment : public LineSegment {
371 public:
372 StitchSegment() : LineSegment() {}
373 16 StitchSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
374 ✗ Curve *duplicate() const override { return new StitchSegment(*this); }
375 ✗ Curve *reverse() const override { return new StitchSegment((*this)[1], (*this)[0]); }
376 };
377
378 // Path(Path const &other) - use default copy constructor
379
380 /// Construct an empty path starting at the specified point.
381 177015 explicit Path(Point const &p = Point())
382
2/6
✓ Branch 1 taken 177015 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 177015 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 177015 : _data(new PathData())
383
2/6
✓ Branch 1 taken 177015 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 177015 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 177015 , _closing_seg(new ClosingSegment(p, p))
384 177015 , _closed(false)
385 177015 , _exception_on_stitch(true)
386 {
387
1/2
✓ Branch 2 taken 177015 times.
✗ Branch 3 not taken.
 177015 _data->curves.push_back(_closing_seg);
388 177015 }
389
390 /// Construct a path containing a range of curves.
391 template <typename Iter>
392 Path(Iter first, Iter last, bool closed = false, bool stitch = false)
393 : _data(new PathData())
394 , _closed(closed)
395 , _exception_on_stitch(!stitch)
396 {
397 for (Iter i = first; i != last; ++i) {
398 _data->curves.push_back(i->duplicate());
399 }
400 if (!_data->curves.empty()) {
401 _closing_seg = new ClosingSegment(_data->curves.back().finalPoint(),
402 _data->curves.front().initialPoint());
403 } else {
404 _closing_seg = new ClosingSegment();
405 }
406 _data->curves.push_back(_closing_seg);
407 }
408
409 /// Create a path from a rectangle.
410 explicit Path(Rect const &r);
411 /// Create a path from a convex hull.
412 explicit Path(ConvexHull const &);
413 /// Create a path from a circle, using two elliptical arcs.
414 explicit Path(Circle const &c);
415 /// Create a path from an ellipse, using two elliptical arcs.
416 explicit Path(Ellipse const &e);
417
418 1145682 virtual ~Path() {}
419
420 // Path &operator=(Path const &other) - use default assignment operator
421
422 /** @brief Swap contents with another path
423 * @todo Add noexcept specifiers for C++11 */
424 81900 void swap(Path &other) noexcept {
425 using std::swap;
426 81900 swap(other._data, _data);
427 81900 swap(other._closing_seg, _closing_seg);
428 81900 swap(other._closed, _closed);
429 81900 swap(other._exception_on_stitch, _exception_on_stitch);
430 81900 }
431 /** @brief Swap contents of two paths.
432 * @relates Path */
433 81900 friend inline void swap(Path &a, Path &b) noexcept { a.swap(b); }
434
435 /** @brief Access a curve by index */
436 1039 Curve const &operator[](size_type i) const { return _data->curves[i]; }
437 /** @brief Access a curve by index */
438 669 Curve const &at(size_type i) const { return _data->curves.at(i); }
439
440 /** @brief Access the first curve in the path.
441 * Since the curve always contains at least a degenerate closing segment,
442 * it is always safe to use this method. */
443 157 Curve const &front() const { return _data->curves.front(); }
444 /// Alias for front().
445 Curve const &initialCurve() const { return _data->curves.front(); }
446 /** @brief Access the last curve in the path. */
447 Curve const &back() const { return back_default(); }
448 12 Curve const &back_open() const {
449
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
 12 if (empty()) return _data->curves.back();
450 12 return _data->curves[_data->curves.size() - 2];
451 }
452 Curve const &back_closed() const {
453 return _closing_seg->isDegenerate()
454 ? _data->curves[_data->curves.size() - 2]
455 : _data->curves[_data->curves.size() - 1];
456 }
457 Curve const &back_default() const {
458 return _includesClosingSegment()
459 ? back_closed()
460 : back_open();
461 }
462 Curve const &finalCurve() const { return back_default(); }
463
464 20 const_iterator begin() const { return const_iterator(*this, 0); }
465 71 const_iterator end() const { return end_default(); }
466
1/2
✓ Branch 2 taken 293 times.
✗ Branch 3 not taken.
 293 const_iterator end_default() const { return const_iterator(*this, size_default()); }
467
1/2
✓ Branch 2 taken 59 times.
✗ Branch 3 not taken.
 59 const_iterator end_open() const { return const_iterator(*this, size_open()); }
468
1/2
✓ Branch 2 taken 1063527 times.
✗ Branch 3 not taken.
 1063527 const_iterator end_closed() const { return const_iterator(*this, size_closed()); }
469 244 iterator begin() { return iterator(*this, 0); }
470 44 iterator end() { return end_default(); }
471
1/2
✓ Branch 2 taken 44 times.
✗ Branch 3 not taken.
 44 iterator end_default() { return iterator(*this, size_default()); }
472 iterator end_open() { return iterator(*this, size_open()); }
473 iterator end_closed() { return iterator(*this, size_closed()); }
474
475 /// Size without the closing segment, even if the path is closed.
476 12222 size_type size_open() const { return _data->curves.size() - 1; }
477
478 /** @brief Size with the closing segment, if it makes a difference.
479 * If the closing segment is degenerate, i.e. its initial and final points
480 * are exactly equal, then it is not included in this size. */
481 ✗ size_type size_closed() const {
482 ✗ return _closing_seg->isDegenerate() ? _data->curves.size() - 1 : _data->curves.size();
483 }
484
485 /// Natural size of the path.
486 12222 size_type size_default() const {
487
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 12222 times.
 12222 return _includesClosingSegment() ? size_closed() : size_open();
488 }
489 /// Natural size of the path.
490 12000 size_type size() const { return size_default(); }
491
492 size_type max_size() const { return _data->curves.max_size() - 1; }
493
494 /** @brief Check whether path is empty.
495 * The path is empty if it contains only the closing segment, which according
496 * to the continuity invariant must be degenerate. Note that unlike standard
497 * containers, two empty paths are not necessarily identical, because the
498 * degenerate closing segment may be at a different point, affecting the operation
499 * of methods such as appendNew(). */
500 450335 bool empty() const { return (_data->curves.size() == 1); }
501
502 /// Check whether the path is closed.
503 86 bool closed() const { return _closed; }
504
505 /** @brief Set whether the path is closed.
506 * When closing a path where the last segment can be represented as a closing
507 * segment, the last segment will be removed. When opening a path, the closing
508 * segment will be erased. This means that closing and then opening a path
509 * will not always give back the original path. */
510 void close(bool closed = true);
511
512 /** @brief Remove all curves from the path.
513 * The initial and final points of the closing segment are set to (0,0).
514 * The stitching flag remains unchanged. */
515 void clear();
516
517 /** @brief Get the approximate bounding box.
518 * The rectangle returned by this method will contain all the curves, but it's not
519 * guaranteed to be the smallest possible one */
520 OptRect boundsFast() const;
521
522 /** @brief Get a tight-fitting bounding box.
523 * This will return the smallest possible axis-aligned rectangle containing
524 * all the curves in the path. */
525 OptRect boundsExact() const;
526
527 Piecewise<D2<SBasis> > toPwSb() const;
528
529 /// Test paths for exact equality.
530 bool operator==(Path const &other) const;
531
532 /// Apply a transform to each curve.
533 template <typename T>
534 36000 Path &operator*=(T const &tr) {
535 BOOST_CONCEPT_ASSERT((TransformConcept<T>));
536 36000 _unshare();
537
2/2
✓ Branch 2 taken 1098000 times.
✓ Branch 3 taken 18000 times.
 2232000 for (std::size_t i = 0; i < _data->curves.size(); ++i) {
538 2196000 _data->curves[i] *= tr;
539 }
540 36000 return *this;
541 }
542
543 template <typename T>
544 ✗ friend Path operator*(Path const &path, T const &tr) {
545 BOOST_CONCEPT_ASSERT((TransformConcept<T>));
546 ✗ Path result(path);
547 ✗ result *= tr;
548 ✗ return result;
549 ✗ }
550
551 /** @brief Get the allowed range of time values.
552 * @return Values for which pointAt() and valueAt() yield valid results. */
553 Interval timeRange() const;
554
555 /** Get the curve at the specified time value.
556 * @param t Time value
557 * @param rest Optional storage for the corresponding time value in the curve */
558 Curve const &curveAt(Coord t, Coord *rest = NULL) const;
559
560 /// Get the closing segment of the path.
561 LineSegment const &closingSegment() const { return *_closing_seg; }
562
563 /** @brief Get the point at the specified time value.
564 * Note that this method has reduced precision with respect to calling pointAt()
565 * directly on the curve. If you want high precision results, use the version
566 * that takes a PathTime parameter.
567 *
568 * Allowed time values range from zero to the number of curves; you can retrieve
569 * the allowed range of values with timeRange(). */
570 Point pointAt(Coord t) const;
571
572 /// Get one coordinate (X or Y) at the specified time value.
573 Coord valueAt(Coord t, Dim2 d) const;
574
575 /// Get the curve at the specified path time.
576 Curve const &curveAt(PathTime const &pos) const;
577 /// Get the point at the specified path time.
578 Point pointAt(PathTime const &pos) const;
579 /// Get one coordinate at the specified path time.
580 Coord valueAt(PathTime const &pos, Dim2 d) const;
581
582 Point operator()(Coord t) const { return pointAt(t); }
583
584 /** @brief Find the extrema of the specified coordinate.
585 *
586 * Returns a PathExtrema struct describing "witness" points on the path
587 * where the specified coordinate attains its minimum and maximum values.
588 */
589 PathExtrema extrema(Dim2 d) const;
590
591 /// Compute intersections with axis-aligned line.
592 std::vector<PathTime> roots(Coord v, Dim2 d) const;
593
594 /// Compute intersections with another path.
595 std::vector<PathIntersection> intersect(Path const &other, Coord precision = EPSILON) const;
596
597 /// Compute intersections of the path with itself.
598 std::vector<PathIntersection> intersectSelf(Coord precision = EPSILON) const;
599
600 /** @brief Determine the winding number at the specified point.
601 *
602 * The winding number is the number of full turns made by a ray that connects the passed
603 * point and the path's value (i.e. the result of the pointAt() method) as the time increases
604 * from 0 to the maximum valid value. Positive numbers indicate turns in the direction
605 * of increasing angles.
606 *
607 * Winding numbers are often used as the definition of what is considered "inside"
608 * the shape. Typically points with either nonzero winding or odd winding are
609 * considered to be inside the path. */
610 int winding(Point const &p) const;
611
612 std::vector<Coord> allNearestTimes(Point const &p, Coord from, Coord to) const;
613 std::vector<Coord> allNearestTimes(Point const &p) const {
614 return allNearestTimes(p, 0, size_default());
615 }
616
617 PathTime nearestTime(Point const &p, Coord *dist = NULL) const;
618 std::vector<Coord> nearestTimePerCurve(Point const &p) const;
619
620 std::vector<Point> nodes() const;
621
622 void appendPortionTo(Path &p, Coord f, Coord t) const;
623
624 /** @brief Append a subset of this path to another path.
625 * An extra stitching segment will be inserted if the start point of the portion
626 * and the final point of the target path do not match exactly.
627 * The closing segment of the target path will be modified. */
628 void appendPortionTo(Path &p, PathTime const &from, PathTime const &to, bool cross_start = false) const {
629 PathInterval ival(from, to, cross_start, size_closed());
630 appendPortionTo(p, ival, std::nullopt, std::nullopt);
631 }
632
633 /** @brief Append a subset of this path to another path.
634 * This version allows you to explicitly pass a PathInterval. */
635 void appendPortionTo(Path &p, PathInterval const &ival) const {
636 appendPortionTo(p, ival, std::nullopt, std::nullopt);
637 }
638
639 /** @brief Append a subset of this path to another path, specifying endpoints.
640 * This method is for use in situations where endpoints of the portion segments
641 * have to be set exactly, for instance when computing Boolean operations. */
642 void appendPortionTo(Path &p, PathInterval const &ival,
643 std::optional<Point> const &p_from, std::optional<Point> const &p_to) const;
644
645 Path portion(Coord f, Coord t) const {
646 Path ret;
647 ret.close(false);
648 appendPortionTo(ret, f, t);
649 return ret;
650 }
651
652 Path portion(Interval const &i) const { return portion(i.min(), i.max()); }
653
654 /** @brief Get a subset of the current path with full precision.
655 * When @a from is larger (later in the path) than @a to, the returned portion
656 * will be reversed. If @a cross_start is true, the portion will be reversed
657 * and will cross the initial point of the path. Therefore, when @a from is larger
658 * than @a to and @a cross_start is true, the returned portion will not be reversed,
659 * but will "wrap around" the end of the path. */
660 Path portion(PathTime const &from, PathTime const &to, bool cross_start = false) const {
661 Path ret;
662 ret.close(false);
663 appendPortionTo(ret, from, to, cross_start);
664 return ret;
665 }
666
667 /** @brief Get a subset of the current path with full precision.
668 * This version allows you to explicitly pass a PathInterval. */
669 Path portion(PathInterval const &ival) const {
670 Path ret;
671 ret.close(false);
672 appendPortionTo(ret, ival);
673 return ret;
674 }
675
676 /** @brief Obtain a reversed version of the current path.
677 * The final point of the current path will become the initial point
678 * of the reversed path, unless it is closed and has a non-degenerate
679 * closing segment. In that case, the new initial point will be the final point
680 * of the last "real" segment. */
681 Path reversed() const;
682
683 void insert(iterator pos, Curve const &curve);
684
685 template <typename Iter>
686 ✗ void insert(iterator pos, Iter first, Iter last) {
687 ✗ _unshare();
688 ✗ Sequence::iterator seq_pos(seq_iter(pos));
689 ✗ Sequence source;
690 ✗ for (; first != last; ++first) {
691 ✗ source.push_back(first->duplicate());
692 }
693 ✗ do_update(seq_pos, seq_pos, source);
694 ✗ }
695
696 void erase(iterator pos);
697 void erase(iterator first, iterator last);
698
699 // erase last segment of path
700 ✗ void erase_last() { erase(iterator(*this, size() - 1)); }
701
702 void start(Point const &p);
703
704 /** @brief Get the first point in the path. */
705 159 Point initialPoint() const { return (*_closing_seg)[1]; }
706
707 /** @brief Get the last point in the path.
708 * If the path is closed, this is always the same as the initial point. */
709
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 559974 times.
 559974 Point finalPoint() const { return (*_closing_seg)[_closed ? 1 : 0]; }
710
711 /** @brief Get the unit tangent vector at the start of the path,
712 * or the zero vector if undefined. */
713 ✗ Point initialUnitTangent() const {
714 ✗ for (auto const &curve : *this) {
715 ✗ if (!curve.isDegenerate()) {
716 ✗ return curve.unitTangentAt(0.0);
717 }
718 }
719 ✗ return Point();
720 }
721
722 /** @brief Get the unit tangent vector at the end of the path,
723 * or the zero vector if undefined. */
724 ✗ Point finalUnitTangent() const {
725 ✗ for (auto it = end(); it != begin();) {
726 ✗ --it;
727 ✗ if (!it->isDegenerate()) {
728 ✗ return it->unitTangentAt(1.0);
729 }
730 }
731 ✗ return Point();
732 }
733
734 void setInitial(Point const &p) {
735 _unshare();
736 _closed = false;
737 _data->curves.front().setInitial(p);
738 _closing_seg->setFinal(p);
739 }
740 void setFinal(Point const &p) {
741 _unshare();
742 _closed = false;
743 _data->curves[size_open() ? size_open() - 1 : 0].setFinal(p);
744 _closing_seg->setInitial(p);
745 }
746
747 /** @brief Add a new curve to the end of the path.
748 * This inserts the new curve right before the closing segment.
749 * The path takes ownership of the passed pointer, which should not be freed. */
750 116 void append(Curve *curve) {
751 116 _unshare();
752
2/4
✓ Branch 2 taken 116 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 116 times.
✗ Branch 6 not taken.
 116 stitchTo(curve->initialPoint());
753 116 do_append(curve);
754 116 }
755
756 68 void append(Curve const &curve) {
757 68 _unshare();
758
2/4
✓ Branch 2 taken 68 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 68 times.
✗ Branch 6 not taken.
 68 stitchTo(curve.initialPoint());
759 68 do_append(curve.duplicate());
760 68 }
761 void append(D2<SBasis> const &curve) {
762 _unshare();
763 stitchTo(Point(curve[X][0][0], curve[Y][0][0]));
764 do_append(new SBasisCurve(curve));
765 }
766 void append(Path const &other) {
767 replace(end_open(), other.begin(), other.end());
768 }
769
770 void replace(iterator replaced, Curve const &curve);
771 void replace(iterator first, iterator last, Curve const &curve);
772 void replace(iterator replaced, Path const &path);
773 void replace(iterator first, iterator last, Path const &path);
774
775 template <typename Iter>
776 ✗ void replace(iterator replaced, Iter first, Iter last) {
777 ✗ replace(replaced, replaced + 1, first, last);
778 ✗ }
779
780 template <typename Iter>
781 ✗ void replace(iterator first_replaced, iterator last_replaced, Iter first, Iter last) {
782 ✗ _unshare();
783 ✗ Sequence::iterator seq_first_replaced(seq_iter(first_replaced));
784 ✗ Sequence::iterator seq_last_replaced(seq_iter(last_replaced));
785 ✗ Sequence source;
786 ✗ for (; first != last; ++first) {
787 ✗ source.push_back(first->duplicate());
788 }
789 ✗ do_update(seq_first_replaced, seq_last_replaced, source);
790 ✗ }
791
792 /** @brief Append a new curve to the path.
793 *
794 * This family of methods will automatically use the current final point of the path
795 * as the first argument of the new curve's constructor. To call this method,
796 * you'll need to write e.g.:
797 * @code
798 path.template appendNew<CubicBezier>(control1, control2, end_point);
799 @endcode
800 * It is important to note that the coordinates passed to appendNew should be finite!
801 * If one of the coordinates is infinite, 2geom will throw a ContinuityError exception.
802 */
803 template <typename CurveType, typename... Args>
804 418548 void appendNew(Args&&... args) {
805 418548 _unshare();
806
6/16
✓ Branch 3 taken 549 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 394725 times.
✓ Branch 6 taken 549 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 394725 times.
✓ Branch 9 taken 549 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 394725 times.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
 418548 do_append(new CurveType(finalPoint(), std::forward<Args>(args)...));
807 418548 }
808
809 /** @brief Reduce the closing segment to a point if it's shorter than precision.
810 * Do this by moving the final point. */
811 void snapEnds(Coord precision = EPSILON);
812
813 /// Append a stitching segment ending at the specified point.
814 void stitchTo(Point const &p);
815
816 /** @brief Return a copy of the path without degenerate curves, except possibly for a
817 * degenerate closing segment. */
818 Path withoutDegenerateCurves() const;
819
820 /** @brief Verify the continuity invariant.
821 * If the path is not contiguous, this will throw a CountinuityError. */
822 void checkContinuity() const;
823
824 /** @brief Enable or disable the throwing of exceptions when stitching discontinuities.
825 * Normally stitching will cause exceptions, but when you are working with unsanitized
826 * curve data, you can disable these exceptions. */
827 23 void setStitching(bool x) {
828 23 _exception_on_stitch = !x;
829 23 }
830
831 private:
832 ✗ static Sequence::iterator seq_iter(iterator const &iter) {
833 ✗ return iter.path->_data->curves.begin() + iter.index;
834 }
835 static Sequence::const_iterator seq_iter(const_iterator const &iter) {
836 return iter.path->_data->curves.begin() + iter.index;
837 }
838
839 // whether the closing segment is part of the path
840 176922 bool _includesClosingSegment() const {
841
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 176922 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 176922 return _closed && !_closing_seg->isDegenerate();
842 }
843 414135 void _unshare() {
844 // Called before every mutation.
845 // Ensure we have our own copy of curve data and reset cached values
846
2/2
✓ Branch 1 taken 861 times.
✓ Branch 2 taken 413274 times.
 414135 if (!_data.unique()) {
847
2/6
✓ Branch 3 taken 861 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 861 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 861 _data.reset(new PathData(*_data));
848 861 _closing_seg = static_cast<ClosingSegment*>(&_data->curves.back());
849 }
850 414135 _data->fast_bounds = OptRect();
851 414135 }
852 PathTime _factorTime(Coord t) const;
853
854 void stitch(Sequence::iterator first_replaced, Sequence::iterator last_replaced, Sequence &sequence);
855 void do_update(Sequence::iterator first, Sequence::iterator last, Sequence &source);
856
857 // n.b. takes ownership of curve object
858 void do_append(Curve *curve);
859
860 std::shared_ptr<PathData> _data;
861 ClosingSegment *_closing_seg;
862 bool _closed;
863 bool _exception_on_stitch;
864 }; // end class Path
865
866 Piecewise<D2<SBasis> > paths_to_pw(PathVector const &paths);
867
868 inline Coord nearest_time(Point const &p, Path const &c) {
869 PathTime pt = c.nearestTime(p);
870 return pt.curve_index + pt.t;
871 }
872
873 bool are_near(Path const &a, Path const &b, Coord precision = EPSILON);
874
875 /**
876 * @brief Find the first point where two paths diverge away from one another.
877 *
878 * If the two paths have a common starting point, the algorithm follows them for as long as the
879 * images of the paths coincide and finds the first point where they stop coinciding. Note that
880 * only the images of paths in the plane are compared, and not their parametrizations, so this
881 * is not a functional (parametric) coincidence. If you want to test parametric coincidence, use
882 * bool are_near(Path const&, Path const&, Coord) instead.
883 *
884 * The function returns the point where the traces of the two paths finally diverge up to the
885 * specified precision. If the traces (images) of the paths are nearly identical until the end,
886 * the returned point is their (almost) common endpoint. If however the image of one of the paths
887 * is completely contained in the image of the other path, the returned point is the endpoint of
888 * the shorter path.
889 *
890 * If the paths have different starting points, then the returned intersection has the special
891 * time values of -1.0 on both paths and the returned intersection point is the midpoint of the
892 * line segment connecting the two starting points.
893 *
894 * @param first The first path to follow; corresponds to .first in the return value.
895 * @param second The second path to follow; corresponds to .second in the return value.
896 * @param precision How close the paths' images need to be in order to be considered as overlapping.
897 * @return A path intersection specifying the point and path times where the two paths part ways.
898 */
899 PathIntersection parting_point(Path const &first, Path const &second, Coord precision = EPSILON);
900
901 std::ostream &operator<<(std::ostream &out, Path const &path);
902
903 } // end namespace Geom
904
905
906 #endif // LIB2GEOM_SEEN_PATH_H
907
908 /*
909 Local Variables:
910 mode:c++
911 c-file-style:"stroustrup"
912 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
913 indent-tabs-mode:nil
914 fill-column:99
915 End:
916 */
917 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
918