1 /** @file
2 * @brief Path - a sequence of contiguous curves (implementation file)
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 #include <2geom/path.h>
36 #include <2geom/pathvector.h>
37 #include <2geom/transforms.h>
38 #include <2geom/circle.h>
39 #include <2geom/ellipse.h>
40 #include <2geom/convex-hull.h>
41 #include <2geom/svg-path-writer.h>
42 #include <2geom/sweeper.h>
43 #include <algorithm>
44 #include <limits>
45 #include <optional>
46
47 using std::swap;
48 using namespace Geom::PathInternal;
49
50 namespace Geom {
51
52 // this represents an empty interval
PathInterval()53 PathInterval::PathInterval()
54 : _from(0, 0.0)
55 , _to(0, 0.0)
56 , _path_size(1)
57 , _cross_start(false)
58 , _reverse(false)
59 {}
60
PathInterval(PathTime const & from,PathTime const & to,bool cross_start,size_type path_size)61 PathInterval::PathInterval(PathTime const &from, PathTime const &to, bool cross_start, size_type path_size)
62 : _from(from)
63 , _to(to)
64 , _path_size(path_size)
65 , _cross_start(cross_start)
66 , _reverse(cross_start ? to >= from : to < from)
67 {
68 if (_reverse) {
69 _to.normalizeForward(_path_size);
70 if (_from != _to) {
71 _from.normalizeBackward(_path_size);
72 }
73 } else {
74 _from.normalizeForward(_path_size);
75 if (_from != _to) {
76 _to.normalizeBackward(_path_size);
77 }
78 }
79
80 if (_from == _to) {
81 _reverse = false;
82 _cross_start = false;
83 }
84 }
85
contains(PathTime const & pos) const86 bool PathInterval::contains(PathTime const &pos) const {
87 if (_cross_start) {
88 if (_reverse) {
89 return pos >= _to || _from >= pos;
90 } else {
91 return pos >= _from || _to >= pos;
92 }
93 } else {
94 if (_reverse) {
95 return _to <= pos && pos <= _from;
96 } else {
97 return _from <= pos && pos <= _to;
98 }
99 }
100 }
101
curveCount() const102 PathInterval::size_type PathInterval::curveCount() const
103 {
104 if (isDegenerate()) return 0;
105 if (_cross_start) {
106 if (_reverse) {
107 return _path_size - _to.curve_index + _from.curve_index + 1;
108 } else {
109 return _path_size - _from.curve_index + _to.curve_index + 1;
110 }
111 } else {
112 if (_reverse) {
113 return _from.curve_index - _to.curve_index + 1;
114 } else {
115 return _to.curve_index - _from.curve_index + 1;
116 }
117 }
118 }
119
inside(Coord min_dist) const120 PathTime PathInterval::inside(Coord min_dist) const
121 {
122 // If there is some node further than min_dist (in time coord) from the ends,
123 // return that node. Otherwise, return the middle.
124 PathTime result(0, 0.0);
125
126 if (!_cross_start && _from.curve_index == _to.curve_index) {
127 PathTime result(_from.curve_index, lerp(0.5, _from.t, _to.t));
128 return result;
129 }
130 // If _cross_start, then we can be sure that at least one node is in the domain.
131 // If dcurve == 0, it actually means that all curves are included in the domain
132
133 if (_reverse) {
134 size_type dcurve = (_path_size + _from.curve_index - _to.curve_index) % _path_size;
135 bool from_close = _from.t < min_dist;
136 bool to_close = _to.t > 1 - min_dist;
137
138 if (dcurve == 0) {
139 dcurve = _path_size;
140 }
141
142 if (dcurve == 1) {
143 if (from_close || to_close) {
144 result.curve_index = _from.curve_index;
145 Coord tmid = _from.t - ((1 - _to.t) + _from.t) * 0.5;
146 if (tmid < 0) {
147 result.curve_index = (_path_size + result.curve_index - 1) % _path_size;
148 tmid += 1;
149 }
150 result.t = tmid;
151 return result;
152 }
153
154 result.curve_index = _from.curve_index;
155 return result;
156 }
157
158 result.curve_index = (_to.curve_index + 1) % _path_size;
159 if (to_close) {
160 if (dcurve == 2) {
161 result.t = 0.5;
162 } else {
163 result.curve_index = (result.curve_index + 1) % _path_size;
164 }
165 }
166 return result;
167 } else {
168 size_type dcurve = (_path_size + _to.curve_index - _from.curve_index) % _path_size;
169 bool from_close = _from.t > 1 - min_dist;
170 bool to_close = _to.t < min_dist;
171
172 if (dcurve == 0) {
173 dcurve = _path_size;
174 }
175
176 if (dcurve == 1) {
177 if (from_close || to_close) {
178 result.curve_index = _from.curve_index;
179 Coord tmid = ((1 - _from.t) + _to.t) * 0.5 + _from.t;
180 if (tmid >= 1) {
181 result.curve_index = (result.curve_index + 1) % _path_size;
182 tmid -= 1;
183 }
184 result.t = tmid;
185 return result;
186 }
187
188 result.curve_index = _to.curve_index;
189 return result;
190 }
191
192 result.curve_index = (_from.curve_index + 1) % _path_size;
193 if (from_close) {
194 if (dcurve == 2) {
195 result.t = 0.5;
196 } else {
197 result.curve_index = (result.curve_index + 1) % _path_size;
198 }
199 }
200 return result;
201 }
202
203 result.curve_index = _reverse ? _from.curve_index : _to.curve_index;
204 return result;
205 }
206
from_direction(PathTime const & from,PathTime const & to,bool reversed,size_type path_size)207 PathInterval PathInterval::from_direction(PathTime const &from, PathTime const &to, bool reversed, size_type path_size)
208 {
209 PathInterval result;
210 result._from = from;
211 result._to = to;
212 result._path_size = path_size;
213
214 if (reversed) {
215 result._to.normalizeForward(path_size);
216 if (result._from != result._to) {
217 result._from.normalizeBackward(path_size);
218 }
219 } else {
220 result._from.normalizeForward(path_size);
221 if (result._from != result._to) {
222 result._to.normalizeBackward(path_size);
223 }
224 }
225
226 if (result._from == result._to) {
227 result._reverse = false;
228 result._cross_start = false;
229 } else {
230 result._reverse = reversed;
231 if (reversed) {
232 result._cross_start = from < to;
233 } else {
234 result._cross_start = to < from;
235 }
236 }
237 return result;
238 }
239
240
Path(Rect const & r)241 Path::Path(Rect const &r)
242 : _data(new PathData())
243 , _closing_seg(new ClosingSegment(r.corner(3), r.corner(0)))
244 , _closed(true)
245 , _exception_on_stitch(true)
246 {
247 for (unsigned i = 0; i < 3; ++i) {
248 _data->curves.push_back(new LineSegment(r.corner(i), r.corner(i+1)));
249 }
250 _data->curves.push_back(_closing_seg);
251 }
252
Path(ConvexHull const & ch)253 Path::Path(ConvexHull const &ch)
254 : _data(new PathData())
255 , _closing_seg(new ClosingSegment(Point(), Point()))
256 , _closed(true)
257 , _exception_on_stitch(true)
258 {
259 if (ch.empty()) {
260 _data->curves.push_back(_closing_seg);
261 return;
262 }
263
264 _closing_seg->setInitial(ch.back());
265 _closing_seg->setFinal(ch.front());
266
267 Point last = ch.front();
268
269 for (std::size_t i = 1; i < ch.size(); ++i) {
270 _data->curves.push_back(new LineSegment(last, ch[i]));
271 last = ch[i];
272 }
273
274 _data->curves.push_back(_closing_seg);
275 _closed = true;
276 }
277
Path(Circle const & c)278 Path::Path(Circle const &c)
279 : _data(new PathData())
280 , _closing_seg(NULL)
281 , _closed(true)
282 , _exception_on_stitch(true)
283 {
284 Point p1 = c.pointAt(0);
285 Point p2 = c.pointAt(M_PI);
286 _data->curves.push_back(new EllipticalArc(p1, c.radius(), c.radius(), 0, false, true, p2));
287 _data->curves.push_back(new EllipticalArc(p2, c.radius(), c.radius(), 0, false, true, p1));
288 _closing_seg = new ClosingSegment(p1, p1);
289 _data->curves.push_back(_closing_seg);
290 }
291
Path(Ellipse const & e)292 Path::Path(Ellipse const &e)
293 : _data(new PathData())
294 , _closing_seg(NULL)
295 , _closed(true)
296 , _exception_on_stitch(true)
297 {
298 Point p1 = e.pointAt(0);
299 Point p2 = e.pointAt(M_PI);
300 _data->curves.push_back(new EllipticalArc(p1, e.rays(), e.rotationAngle(), false, true, p2));
301 _data->curves.push_back(new EllipticalArc(p2, e.rays(), e.rotationAngle(), false, true, p1));
302 _closing_seg = new ClosingSegment(p1, p1);
303 _data->curves.push_back(_closing_seg);
304 }
305
close(bool c)306 void Path::close(bool c)
307 {
308 if (c == _closed) return;
309 if (c && _data->curves.size() >= 2) {
310 // when closing, if last segment is linear and ends at initial point,
311 // replace it with the closing segment
312 Sequence::iterator last = _data->curves.end() - 2;
313 if (last->isLineSegment() && last->finalPoint() == initialPoint()) {
314 _closing_seg->setInitial(last->initialPoint());
315 _data->curves.erase(last);
316 }
317 }
318 _closed = c;
319 }
320
clear()321 void Path::clear()
322 {
323 _unshare();
324 _data->curves.pop_back().release();
325 _data->curves.clear();
326 _closing_seg->setInitial(Point(0, 0));
327 _closing_seg->setFinal(Point(0, 0));
328 _data->curves.push_back(_closing_seg);
329 _closed = false;
330 }
331
boundsFast() const332 OptRect Path::boundsFast() const
333 {
334 OptRect bounds;
335 if (empty()) {
336 return bounds;
337 }
338 // if the path is not empty, we look for cached bounds
339 if (_data->fast_bounds) {
340 return _data->fast_bounds;
341 }
342
343 bounds = front().boundsFast();
344 const_iterator iter = begin();
345 // the closing path segment can be ignored, because it will always
346 // lie within the bbox of the rest of the path
347 if (iter != end()) {
348 for (++iter; iter != end(); ++iter) {
349 bounds.unionWith(iter->boundsFast());
350 }
351 }
352 _data->fast_bounds = bounds;
353 return bounds;
354 }
355
boundsExact() const356 OptRect Path::boundsExact() const
357 {
358 OptRect bounds;
359 if (empty())
360 return bounds;
361 bounds = front().boundsExact();
362 const_iterator iter = begin();
363 // the closing path segment can be ignored, because it will always lie within the bbox of the rest of the path
364 if (iter != end()) {
365 for (++iter; iter != end(); ++iter) {
366 bounds.unionWith(iter->boundsExact());
367 }
368 }
369 return bounds;
370 }
371
toPwSb() const372 Piecewise<D2<SBasis> > Path::toPwSb() const
373 {
374 Piecewise<D2<SBasis> > ret;
375 ret.push_cut(0);
376 unsigned i = 1;
377 bool degenerate = true;
378 // pw<d2<>> is always open. so if path is closed, add closing segment as well to pwd2.
379 for (const_iterator it = begin(); it != end_default(); ++it) {
380 if (!it->isDegenerate()) {
381 ret.push(it->toSBasis(), i++);
382 degenerate = false;
383 }
384 }
385 if (degenerate) {
386 // if path only contains degenerate curves, no second cut is added
387 // so we need to create at least one segment manually
388 ret = Piecewise<D2<SBasis> >(initialPoint());
389 }
390 return ret;
391 }
392
393 template <typename iter>
inc(iter const & x,unsigned n)394 iter inc(iter const &x, unsigned n) {
395 iter ret = x;
396 for (unsigned i = 0; i < n; i++)
397 ret++;
398 return ret;
399 }
400
operator ==(Path const & other) const401 bool Path::operator==(Path const &other) const
402 {
403 if (this == &other)
404 return true;
405 if (_closed != other._closed)
406 return false;
407 return _data->curves == other._data->curves;
408 }
409
start(Point const & p)410 void Path::start(Point const &p) {
411 if (_data->curves.size() > 1) {
412 clear();
413 }
414 _closing_seg->setInitial(p);
415 _closing_seg->setFinal(p);
416 }
417
timeRange() const418 Interval Path::timeRange() const
419 {
420 Interval ret(0, size_default());
421 return ret;
422 }
423
curveAt(Coord t,Coord * rest) const424 Curve const &Path::curveAt(Coord t, Coord *rest) const
425 {
426 PathTime pos = _factorTime(t);
427 if (rest) {
428 *rest = pos.t;
429 }
430 return at(pos.curve_index);
431 }
432
pointAt(Coord t) const433 Point Path::pointAt(Coord t) const
434 {
435 return pointAt(_factorTime(t));
436 }
437
valueAt(Coord t,Dim2 d) const438 Coord Path::valueAt(Coord t, Dim2 d) const
439 {
440 return valueAt(_factorTime(t), d);
441 }
442
curveAt(PathTime const & pos) const443 Curve const &Path::curveAt(PathTime const &pos) const
444 {
445 return at(pos.curve_index);
446 }
pointAt(PathTime const & pos) const447 Point Path::pointAt(PathTime const &pos) const
448 {
449 return at(pos.curve_index).pointAt(pos.t);
450 }
valueAt(PathTime const & pos,Dim2 d) const451 Coord Path::valueAt(PathTime const &pos, Dim2 d) const
452 {
453 return at(pos.curve_index).valueAt(pos.t, d);
454 }
455
roots(Coord v,Dim2 d) const456 std::vector<PathTime> Path::roots(Coord v, Dim2 d) const
457 {
458 std::vector<PathTime> res;
459 for (unsigned i = 0; i < size(); i++) {
460 std::vector<Coord> temp = (*this)[i].roots(v, d);
461 for (double j : temp)
462 res.emplace_back(i, j);
463 }
464 return res;
465 }
466
467
468 // The class below implements sweepline optimization for curve intersection in paths.
469 // Instead of O(N^2), this takes O(N + X), where X is the number of overlaps
470 // between the bounding boxes of curves.
471
472 struct CurveIntersectionSweepSet
473 {
474 public:
475 struct CurveRecord {
476 boost::intrusive::list_member_hook<> _hook;
477 Curve const *curve;
478 Rect bounds;
479 std::size_t index;
480 unsigned which;
481
CurveRecordGeom::CurveIntersectionSweepSet::CurveRecord482 CurveRecord(Curve const *pc, std::size_t idx, unsigned w)
483 : curve(pc)
484 , bounds(curve->boundsFast())
485 , index(idx)
486 , which(w)
487 {}
488 };
489
490 typedef std::vector<CurveRecord>::const_iterator ItemIterator;
491
CurveIntersectionSweepSetGeom::CurveIntersectionSweepSet492 CurveIntersectionSweepSet(std::vector<PathIntersection> &result,
493 Path const &a, Path const &b, Coord precision)
494 : _result(result)
495 , _precision(precision)
496 , _sweep_dir(X)
497 {
498 std::size_t asz = a.size(), bsz = b.size();
499 _records.reserve(asz + bsz);
500
501 for (std::size_t i = 0; i < asz; ++i) {
502 _records.emplace_back(&a[i], i, 0);
503 }
504 for (std::size_t i = 0; i < bsz; ++i) {
505 _records.emplace_back(&b[i], i, 1);
506 }
507
508 OptRect abb = a.boundsFast() | b.boundsFast();
509 if (abb && abb->height() > abb->width()) {
510 _sweep_dir = Y;
511 }
512 }
513
itemsGeom::CurveIntersectionSweepSet514 std::vector<CurveRecord> const &items() { return _records; }
itemBoundsGeom::CurveIntersectionSweepSet515 Interval itemBounds(ItemIterator ii) {
516 return ii->bounds[_sweep_dir];
517 }
518
addActiveItemGeom::CurveIntersectionSweepSet519 void addActiveItem(ItemIterator ii) {
520 unsigned w = ii->which;
521 unsigned ow = (w+1) % 2;
522
523 _active[w].push_back(const_cast<CurveRecord&>(*ii));
524
525 for (auto & i : _active[ow]) {
526 if (!ii->bounds.intersects(i.bounds)) continue;
527 std::vector<CurveIntersection> cx = ii->curve->intersect(*i.curve, _precision);
528 for (auto & k : cx) {
529 PathTime tw(ii->index, k.first), tow(i.index, k.second);
530 _result.emplace_back(
531 w == 0 ? tw : tow,
532 w == 0 ? tow : tw,
533 k.point());
534 }
535 }
536 }
removeActiveItemGeom::CurveIntersectionSweepSet537 void removeActiveItem(ItemIterator ii) {
538 ActiveCurveList &acl = _active[ii->which];
539 acl.erase(acl.iterator_to(*ii));
540 }
541
542 private:
543 typedef boost::intrusive::list
544 < CurveRecord
545 , boost::intrusive::member_hook
546 < CurveRecord
547 , boost::intrusive::list_member_hook<>
548 , &CurveRecord::_hook
549 >
550 > ActiveCurveList;
551
552 std::vector<CurveRecord> _records;
553 std::vector<PathIntersection> &_result;
554 ActiveCurveList _active[2];
555 Coord _precision;
556 Dim2 _sweep_dir;
557 };
558
intersect(Path const & other,Coord precision) const559 std::vector<PathIntersection> Path::intersect(Path const &other, Coord precision) const
560 {
561 std::vector<PathIntersection> result;
562
563 CurveIntersectionSweepSet cisset(result, *this, other, precision);
564 Sweeper<CurveIntersectionSweepSet> sweeper(cisset);
565 sweeper.process();
566
567 // preprocessing to remove duplicate intersections at endpoints
568 std::size_t asz = size(), bsz = other.size();
569 for (auto & i : result) {
570 i.first.normalizeForward(asz);
571 i.second.normalizeForward(bsz);
572 }
573 std::sort(result.begin(), result.end());
574 result.erase(std::unique(result.begin(), result.end()), result.end());
575
576 return result;
577 }
578
winding(Point const & p) const579 int Path::winding(Point const &p) const {
580 int wind = 0;
581
582 /* To handle all the edge cases, we consider the maximum Y edge of the bounding box
583 * as not included in box. This way paths that contain linear horizontal
584 * segments will be treated correctly. */
585 for (const_iterator i = begin(); i != end_closed(); ++i) {
586 Rect bounds = i->boundsFast();
587
588 if (bounds.height() == 0) continue;
589 if (p[X] > bounds.right() || !bounds[Y].lowerContains(p[Y])) {
590 // Ray doesn't intersect bbox, so we ignore this segment
591 continue;
592 }
593
594 if (p[X] < bounds.left()) {
595 /* Ray intersects the curve's bbox, but the point is outside it.
596 * The winding contribution is exactly the same as that
597 * of a linear segment with the same initial and final points. */
598 Point ip = i->initialPoint();
599 Point fp = i->finalPoint();
600 Rect eqbox(ip, fp);
601
602 if (eqbox[Y].lowerContains(p[Y])) {
603 /* The ray intersects the equivalent linear segment.
604 * Determine winding contribution based on its derivative. */
605 if (ip[Y] < fp[Y]) {
606 wind += 1;
607 } else if (ip[Y] > fp[Y]) {
608 wind -= 1;
609 } else {
610 // should never happen, because bounds.height() was not zero
611 assert(false);
612 }
613 }
614 } else {
615 // point is inside bbox
616 wind += i->winding(p);
617 }
618 }
619 return wind;
620 }
621
allNearestTimes(Point const & _point,double from,double to) const622 std::vector<double> Path::allNearestTimes(Point const &_point, double from, double to) const
623 {
624 // TODO from and to are not used anywhere.
625 // rewrite this to simplify.
626 using std::swap;
627
628 if (from > to)
629 swap(from, to);
630 const Path &_path = *this;
631 unsigned int sz = _path.size();
632 if (_path.closed())
633 ++sz;
634 if (from < 0 || to > sz) {
635 THROW_RANGEERROR("[from,to] interval out of bounds");
636 }
637 double sif, st = modf(from, &sif);
638 double eif, et = modf(to, &eif);
639 unsigned int si = static_cast<unsigned int>(sif);
640 unsigned int ei = static_cast<unsigned int>(eif);
641 if (si == sz) {
642 --si;
643 st = 1;
644 }
645 if (ei == sz) {
646 --ei;
647 et = 1;
648 }
649 if (si == ei) {
650 std::vector<double> all_nearest = _path[si].allNearestTimes(_point, st, et);
651 for (double & i : all_nearest) {
652 i = si + i;
653 }
654 return all_nearest;
655 }
656 std::vector<double> all_t;
657 std::vector<std::vector<double> > all_np;
658 all_np.push_back(_path[si].allNearestTimes(_point, st));
659 std::vector<unsigned int> ni;
660 ni.push_back(si);
661 double dsq;
662 double mindistsq = distanceSq(_point, _path[si].pointAt(all_np.front().front()));
663 Rect bb(Geom::Point(0, 0), Geom::Point(0, 0));
664 for (unsigned int i = si + 1; i < ei; ++i) {
665 bb = (_path[i].boundsFast());
666 dsq = distanceSq(_point, bb);
667 if (mindistsq < dsq)
668 continue;
669 all_t = _path[i].allNearestTimes(_point);
670 dsq = distanceSq(_point, _path[i].pointAt(all_t.front()));
671 if (mindistsq > dsq) {
672 all_np.clear();
673 all_np.push_back(all_t);
674 ni.clear();
675 ni.push_back(i);
676 mindistsq = dsq;
677 } else if (mindistsq == dsq) {
678 all_np.push_back(all_t);
679 ni.push_back(i);
680 }
681 }
682 bb = (_path[ei].boundsFast());
683 dsq = distanceSq(_point, bb);
684 if (mindistsq >= dsq) {
685 all_t = _path[ei].allNearestTimes(_point, 0, et);
686 dsq = distanceSq(_point, _path[ei].pointAt(all_t.front()));
687 if (mindistsq > dsq) {
688 for (double & i : all_t) {
689 i = ei + i;
690 }
691 return all_t;
692 } else if (mindistsq == dsq) {
693 all_np.push_back(all_t);
694 ni.push_back(ei);
695 }
696 }
697 std::vector<double> all_nearest;
698 for (unsigned int i = 0; i < all_np.size(); ++i) {
699 for (unsigned int j = 0; j < all_np[i].size(); ++j) {
700 all_nearest.push_back(ni[i] + all_np[i][j]);
701 }
702 }
703 all_nearest.erase(std::unique(all_nearest.begin(), all_nearest.end()), all_nearest.end());
704 return all_nearest;
705 }
706
nearestTimePerCurve(Point const & p) const707 std::vector<Coord> Path::nearestTimePerCurve(Point const &p) const
708 {
709 // return a single nearest time for each curve in this path
710 std::vector<Coord> np;
711 for (const_iterator it = begin(); it != end_default(); ++it) {
712 np.push_back(it->nearestTime(p));
713 }
714 return np;
715 }
716
nearestTime(Point const & p,Coord * dist) const717 PathTime Path::nearestTime(Point const &p, Coord *dist) const
718 {
719 Coord mindist = std::numeric_limits<Coord>::max();
720 PathTime ret;
721
722 if (_data->curves.size() == 1) {
723 // naked moveto
724 ret.curve_index = 0;
725 ret.t = 0;
726 if (dist) {
727 *dist = distance(_closing_seg->initialPoint(), p);
728 }
729 return ret;
730 }
731
732 for (size_type i = 0; i < size_default(); ++i) {
733 Curve const &c = at(i);
734 if (distance(p, c.boundsFast()) >= mindist) continue;
735
736 Coord t = c.nearestTime(p);
737 Coord d = distance(c.pointAt(t), p);
738 if (d < mindist) {
739 mindist = d;
740 ret.curve_index = i;
741 ret.t = t;
742 }
743 }
744 if (dist) {
745 *dist = mindist;
746 }
747
748 return ret;
749 }
750
nodes() const751 std::vector<Point> Path::nodes() const
752 {
753 std::vector<Point> result;
754 size_type path_size = size_closed();
755 for (size_type i = 0; i < path_size; ++i) {
756 result.push_back(_data->curves[i].initialPoint());
757 }
758 return result;
759 }
760
appendPortionTo(Path & ret,double from,double to) const761 void Path::appendPortionTo(Path &ret, double from, double to) const
762 {
763 if (!(from >= 0 && to >= 0)) {
764 THROW_RANGEERROR("from and to must be >=0 in Path::appendPortionTo");
765 }
766 if (to == 0)
767 to = size() + 0.999999;
768 if (from == to) {
769 return;
770 }
771 double fi, ti;
772 double ff = modf(from, &fi), tf = modf(to, &ti);
773 if (tf == 0) {
774 ti--;
775 tf = 1;
776 }
777 const_iterator fromi = inc(begin(), (unsigned)fi);
778 if (fi == ti && from < to) {
779 ret.append(fromi->portion(ff, tf));
780 return;
781 }
782 const_iterator toi = inc(begin(), (unsigned)ti);
783 if (ff != 1.) {
784 // fromv->setInitial(ret.finalPoint());
785 ret.append(fromi->portion(ff, 1.));
786 }
787 if (from >= to) {
788 const_iterator ender = end();
789 if (ender->initialPoint() == ender->finalPoint())
790 ++ender;
791 ret.insert(ret.end(), ++fromi, ender);
792 ret.insert(ret.end(), begin(), toi);
793 } else {
794 ret.insert(ret.end(), ++fromi, toi);
795 }
796 ret.append(toi->portion(0., tf));
797 }
798
appendPortionTo(Path & target,PathInterval const & ival,std::optional<Point> const & p_from,std::optional<Point> const & p_to) const799 void Path::appendPortionTo(Path &target, PathInterval const &ival,
800 std::optional<Point> const &p_from, std::optional<Point> const &p_to) const
801 {
802 assert(ival.pathSize() == size_closed());
803
804 if (ival.isDegenerate()) {
805 Point stitch_to = p_from ? *p_from : pointAt(ival.from());
806 target.stitchTo(stitch_to);
807 return;
808 }
809
810 PathTime const &from = ival.from(), &to = ival.to();
811
812 bool reverse = ival.reverse();
813 int di = reverse ? -1 : 1;
814 size_type s = size_closed();
815
816 if (!ival.crossesStart() && from.curve_index == to.curve_index) {
817 Curve *c = (*this)[from.curve_index].portion(from.t, to.t);
818 if (p_from) {
819 c->setInitial(*p_from);
820 }
821 if (p_to) {
822 c->setFinal(*p_to);
823 }
824 target.append(c);
825 } else {
826 Curve *c_first = (*this)[from.curve_index].portion(from.t, reverse ? 0 : 1);
827 if (p_from) {
828 c_first->setInitial(*p_from);
829 }
830 target.append(c_first);
831
832 for (size_type i = (from.curve_index + s + di) % s; i != to.curve_index;
833 i = (i + s + di) % s)
834 {
835 if (reverse) {
836 target.append((*this)[i].reverse());
837 } else {
838 target.append((*this)[i].duplicate());
839 }
840 }
841
842 Curve *c_last = (*this)[to.curve_index].portion(reverse ? 1 : 0, to.t);
843 if (p_to) {
844 c_last->setFinal(*p_to);
845 }
846 target.append(c_last);
847 }
848 }
849
reversed() const850 Path Path::reversed() const
851 {
852 typedef std::reverse_iterator<Sequence::const_iterator> RIter;
853
854 Path ret(finalPoint());
855 if (empty()) return ret;
856
857 ret._data->curves.pop_back(); // this also deletes the closing segment from ret
858
859 RIter iter(_includesClosingSegment() ? _data->curves.end() : _data->curves.end() - 1);
860 RIter rend(_data->curves.begin());
861
862 if (_closed) {
863 // when the path is closed, there are two cases:
864 if (front().isLineSegment()) {
865 // 1. initial segment is linear: it becomes the new closing segment.
866 rend = RIter(_data->curves.begin() + 1);
867 ret._closing_seg = new ClosingSegment(front().finalPoint(), front().initialPoint());
868 } else {
869 // 2. initial segment is not linear: the closing segment becomes degenerate.
870 // However, skip it if it's already degenerate.
871 Point fp = finalPoint();
872 ret._closing_seg = new ClosingSegment(fp, fp);
873 }
874 } else {
875 // when the path is open, we reverse all real curves, and add a reversed closing segment.
876 ret._closing_seg = static_cast<ClosingSegment *>(_closing_seg->reverse());
877 }
878
879 for (; iter != rend; ++iter) {
880 ret._data->curves.push_back(iter->reverse());
881 }
882 ret._data->curves.push_back(ret._closing_seg);
883 ret._closed = _closed;
884 return ret;
885 }
886
887
insert(iterator pos,Curve const & curve)888 void Path::insert(iterator pos, Curve const &curve)
889 {
890 _unshare();
891 Sequence::iterator seq_pos(seq_iter(pos));
892 Sequence source;
893 source.push_back(curve.duplicate());
894 do_update(seq_pos, seq_pos, source);
895 }
896
erase(iterator pos)897 void Path::erase(iterator pos)
898 {
899 _unshare();
900 Sequence::iterator seq_pos(seq_iter(pos));
901
902 Sequence stitched;
903 do_update(seq_pos, seq_pos + 1, stitched);
904 }
905
erase(iterator first,iterator last)906 void Path::erase(iterator first, iterator last)
907 {
908 _unshare();
909 Sequence::iterator seq_first = seq_iter(first);
910 Sequence::iterator seq_last = seq_iter(last);
911
912 Sequence stitched;
913 do_update(seq_first, seq_last, stitched);
914 }
915
stitchTo(Point const & p)916 void Path::stitchTo(Point const &p)
917 {
918 if (!empty() && _closing_seg->initialPoint() != p) {
919 if (_exception_on_stitch) {
920 THROW_CONTINUITYERROR();
921 }
922 _unshare();
923 do_append(new StitchSegment(_closing_seg->initialPoint(), p));
924 }
925 }
926
replace(iterator replaced,Curve const & curve)927 void Path::replace(iterator replaced, Curve const &curve)
928 {
929 replace(replaced, replaced + 1, curve);
930 }
931
replace(iterator first_replaced,iterator last_replaced,Curve const & curve)932 void Path::replace(iterator first_replaced, iterator last_replaced, Curve const &curve)
933 {
934 _unshare();
935 Sequence::iterator seq_first_replaced(seq_iter(first_replaced));
936 Sequence::iterator seq_last_replaced(seq_iter(last_replaced));
937 Sequence source(1);
938 source.push_back(curve.duplicate());
939
940 do_update(seq_first_replaced, seq_last_replaced, source);
941 }
942
replace(iterator replaced,Path const & path)943 void Path::replace(iterator replaced, Path const &path)
944 {
945 replace(replaced, path.begin(), path.end());
946 }
947
replace(iterator first,iterator last,Path const & path)948 void Path::replace(iterator first, iterator last, Path const &path)
949 {
950 replace(first, last, path.begin(), path.end());
951 }
952
snapEnds(Coord precision)953 void Path::snapEnds(Coord precision)
954 {
955 if (!_closed) return;
956 if (_data->curves.size() > 1 && are_near(_closing_seg->length(precision), 0, precision)) {
957 _unshare();
958 _closing_seg->setInitial(_closing_seg->finalPoint());
959 (_data->curves.end() - 1)->setFinal(_closing_seg->finalPoint());
960 }
961 }
962
963 // replace curves between first and last with contents of source,
964 //
do_update(Sequence::iterator first,Sequence::iterator last,Sequence & source)965 void Path::do_update(Sequence::iterator first, Sequence::iterator last, Sequence &source)
966 {
967 // TODO: handle cases where first > last in closed paths?
968 bool last_beyond_closing_segment = (last == _data->curves.end());
969
970 // special case:
971 // if do_update replaces the closing segment, we have to regenerate it
972 if (source.empty()) {
973 if (first == last) return; // nothing to do
974
975 // only removing some segments
976 if ((!_closed && first == _data->curves.begin()) || (!_closed && last == _data->curves.end() - 1) || last_beyond_closing_segment) {
977 // just adjust the closing segment
978 // do nothing
979 } else if (first->initialPoint() != (last - 1)->finalPoint()) {
980 if (_exception_on_stitch) {
981 THROW_CONTINUITYERROR();
982 }
983 source.push_back(new StitchSegment(first->initialPoint(), (last - 1)->finalPoint()));
984 }
985 } else {
986 // replacing
987 if (first == _data->curves.begin() && last == _data->curves.end()) {
988 // special case: replacing everything should work the same in open and closed curves
989 _data->curves.erase(_data->curves.begin(), _data->curves.end() - 1);
990 _closing_seg->setFinal(source.front().initialPoint());
991 _closing_seg->setInitial(source.back().finalPoint());
992 _data->curves.transfer(_data->curves.begin(), source.begin(), source.end(), source);
993 return;
994 }
995
996 // stitch in front
997 if (!_closed && first == _data->curves.begin()) {
998 // not necessary to stitch in front
999 } else if (first->initialPoint() != source.front().initialPoint()) {
1000 if (_exception_on_stitch) {
1001 THROW_CONTINUITYERROR();
1002 }
1003 source.insert(source.begin(), new StitchSegment(first->initialPoint(), source.front().initialPoint()));
1004 }
1005
1006 // stitch at the end
1007 if ((!_closed && last == _data->curves.end() - 1) || last_beyond_closing_segment) {
1008 // repurpose the closing segment as the stitch segment
1009 // do nothing
1010 } else if (source.back().finalPoint() != (last - 1)->finalPoint()) {
1011 if (_exception_on_stitch) {
1012 THROW_CONTINUITYERROR();
1013 }
1014 source.push_back(new StitchSegment(source.back().finalPoint(), (last - 1)->finalPoint()));
1015 }
1016 }
1017
1018 // do not erase the closing segment, adjust it instead
1019 if (last_beyond_closing_segment) {
1020 --last;
1021 }
1022 _data->curves.erase(first, last);
1023 _data->curves.transfer(first, source.begin(), source.end(), source);
1024
1025 // adjust closing segment
1026 if (size_open() == 0) {
1027 _closing_seg->setFinal(_closing_seg->initialPoint());
1028 } else {
1029 _closing_seg->setInitial(back_open().finalPoint());
1030 _closing_seg->setFinal(front().initialPoint());
1031 }
1032
1033 checkContinuity();
1034 }
1035
do_append(Curve * c)1036 void Path::do_append(Curve *c)
1037 {
1038 if (&_data->curves.front() == _closing_seg) {
1039 _closing_seg->setFinal(c->initialPoint());
1040 } else {
1041 // if we can't freely move the closing segment, we check whether
1042 // the new curve connects with the last non-closing curve
1043 if (c->initialPoint() != _closing_seg->initialPoint()) {
1044 THROW_CONTINUITYERROR();
1045 }
1046 if (_closed && c->isLineSegment() &&
1047 c->finalPoint() == _closing_seg->finalPoint())
1048 {
1049 // appending a curve that matches the closing segment has no effect
1050 delete c;
1051 return;
1052 }
1053 }
1054 _data->curves.insert(_data->curves.end() - 1, c);
1055 _closing_seg->setInitial(c->finalPoint());
1056 }
1057
checkContinuity() const1058 void Path::checkContinuity() const
1059 {
1060 Sequence::const_iterator i = _data->curves.begin(), j = _data->curves.begin();
1061 ++j;
1062 for (; j != _data->curves.end(); ++i, ++j) {
1063 if (i->finalPoint() != j->initialPoint()) {
1064 THROW_CONTINUITYERROR();
1065 }
1066 }
1067 if (_data->curves.front().initialPoint() != _data->curves.back().finalPoint()) {
1068 THROW_CONTINUITYERROR();
1069 }
1070 }
1071
1072 // breaks time value into integral and fractional part
_factorTime(Coord t) const1073 PathTime Path::_factorTime(Coord t) const
1074 {
1075 size_type sz = size_default();
1076 if (t < 0 || t > sz) {
1077 THROW_RANGEERROR("parameter t out of bounds");
1078 }
1079
1080 PathTime ret;
1081 Coord k;
1082 ret.t = modf(t, &k);
1083 ret.curve_index = k;
1084 if (ret.curve_index == sz) {
1085 --ret.curve_index;
1086 ret.t = 1;
1087 }
1088 return ret;
1089 }
1090
paths_to_pw(PathVector const & paths)1091 Piecewise<D2<SBasis> > paths_to_pw(PathVector const &paths)
1092 {
1093 Piecewise<D2<SBasis> > ret = paths[0].toPwSb();
1094 for (unsigned i = 1; i < paths.size(); i++) {
1095 ret.concat(paths[i].toPwSb());
1096 }
1097 return ret;
1098 }
1099
are_near(Path const & a,Path const & b,Coord precision)1100 bool are_near(Path const &a, Path const &b, Coord precision)
1101 {
1102 if (a.size() != b.size()) return false;
1103
1104 for (unsigned i = 0; i < a.size(); ++i) {
1105 if (!a[i].isNear(b[i], precision)) return false;
1106 }
1107 return true;
1108 }
1109
operator <<(std::ostream & out,Path const & path)1110 std::ostream &operator<<(std::ostream &out, Path const &path)
1111 {
1112 SVGPathWriter pw;
1113 pw.feed(path);
1114 out << pw.str();
1115 return out;
1116 }
1117
1118 } // end namespace Geom
1119
1120 /*
1121 Local Variables:
1122 mode:c++
1123 c-file-style:"stroustrup"
1124 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
1125 indent-tabs-mode:nil
1126 fill-column:99
1127 End:
1128 */
1129 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :
1130