1 /*
2 * Path - Series of continuous curves
3 *
4 * Authors:
5 * MenTaLguY <mental@rydia.net>
6 * Marco Cecchetti <mrcekets at gmail.com>
7 *
8 * Copyright 2007-2008 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 */
37 #ifndef SEEN_GEOM_PATH_H
38 #define SEEN_GEOM_PATH_H
41 #include <boost/shared_ptr.hpp>
42 #include <2geom/curve.h>
43 #include <2geom/bezier-curve.h>
45 #include <iterator>
46 #include <algorithm>
49 namespace Geom
50 {
52 class Path;
54 namespace PathInternal {
56 typedef std::vector<boost::shared_ptr<Curve const> > Sequence;
58 template <typename C, typename P>
59 class BaseIterator {
60 protected:
61 BaseIterator() : path(NULL), index(0) {}
62 BaseIterator(P *p, unsigned i) : path(p), index(i) {}
63 // default copy, default assign
65 public:
66 bool operator==(BaseIterator const &other) {
67 return path == other.path && index == other.index;
68 }
69 bool operator!=(BaseIterator const &other) {
70 return path != other.path || index != other.index;
71 }
73 Curve const &operator*() const { return (*path)[index]; }
74 Curve const *operator->() const { return &(*path)[index]; }
75 boost::shared_ptr<Curve const> get_ref() const {
76 return path->get_ref_at_index(index);
77 }
79 C &operator++() {
80 ++index;
81 return static_cast<C &>(*this);
82 }
83 C operator++(int) {
84 C old(static_cast<C &>(*this));
85 ++(*this);
86 return old;
87 }
89 C &operator--() {
90 --index;
91 return static_cast<C &>(*this);
92 }
93 C operator--(int) {
94 C old(static_cast<C &>(*this));
95 --(*this);
96 return old;
97 }
99 private:
100 P *path;
101 unsigned index;
103 friend class ::Geom::Path;
104 };
106 class ConstIterator : public BaseIterator<ConstIterator, Path const> {
107 public:
108 typedef BaseIterator<ConstIterator, Path const> Base;
110 ConstIterator() : Base() {}
111 // default copy, default assign
113 private:
114 ConstIterator(Path const &p, unsigned i) : Base(&p, i) {}
115 friend class ::Geom::Path;
116 };
118 class Iterator : public BaseIterator<Iterator, Path> {
119 public:
120 typedef BaseIterator<Iterator, Path> Base;
122 Iterator() : Base() {}
123 // default copy, default assign
125 operator ConstIterator const &() const {
126 return reinterpret_cast<ConstIterator const &>(*this);
127 }
129 private:
130 Iterator(Path &p, unsigned i) : Base(&p, i) {}
131 friend class ::Geom::Path;
132 };
134 }
136 /*
137 * Open and closed paths: all paths, whether open or closed, store a final
138 * segment which connects the initial and final endpoints of the "real"
139 * path data. While similar to the "z" in an SVG path, it exists for
140 * both open and closed paths, and is not considered part of the "normal"
141 * path data, which is always covered by the range [begin(), end_open()).
142 * Conversely, the range [begin(), end_closed()) always contains the "extra"
143 * closing segment.
144 *
145 * The only difference between a closed and an open path is whether
146 * end_default() returns end_closed() or end_open(). The idea behind this
147 * is to let any path be stroked using [begin(), end_default()), and filled
148 * using [begin(), end_closed()), without requiring a separate "filled" version
149 * of the path to use for filling.
150 *
151 * \invariant : curves_ always contains at least one segment. The last segment
152 * is always of type ClosingSegment. All constructors take care of this.
153 (curves_.size() > 0) && dynamic_cast<ClosingSegment>(curves_.back())
154 */
155 class Path {
156 public:
157 typedef PathInternal::Sequence Sequence;
158 typedef PathInternal::Iterator iterator;
159 typedef PathInternal::ConstIterator const_iterator;
160 typedef Sequence::size_type size_type;
161 typedef Sequence::difference_type difference_type;
163 class ClosingSegment : public LineSegment {
164 public:
165 ClosingSegment() : LineSegment() {}
166 ClosingSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
167 virtual Curve *duplicate() const { return new ClosingSegment(*this); }
168 virtual Curve *reverse() const { return new ClosingSegment((*this)[1], (*this)[0]); }
169 };
171 enum Stitching {
172 NO_STITCHING=0,
173 STITCH_DISCONTINUOUS
174 };
176 class StitchSegment : public LineSegment {
177 public:
178 StitchSegment() : LineSegment() {}
179 StitchSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
180 virtual Curve *duplicate() const { return new StitchSegment(*this); }
181 virtual Curve *reverse() const { return new StitchSegment((*this)[1], (*this)[0]); }
182 };
184 // Path(Path const &other) - use default copy constructor
186 explicit Path(Point p=Point())
187 : curves_(boost::shared_ptr<Sequence>(new Sequence(1, boost::shared_ptr<Curve>()))),
188 final_(new ClosingSegment(p, p)),
189 closed_(false)
190 {
191 get_curves().back() = boost::shared_ptr<Curve>(final_);
192 }
194 Path(const_iterator const &first,
195 const_iterator const &last,
196 bool closed=false)
197 : curves_(boost::shared_ptr<Sequence>(new Sequence(seq_iter(first),
198 seq_iter(last)))),
199 closed_(closed)
200 {
201 if (!get_curves().empty()) {
202 final_ = new ClosingSegment(get_curves().back()->finalPoint(),
203 get_curves().front()->initialPoint());
204 } else {
205 final_ = new ClosingSegment();
206 }
207 get_curves().push_back(boost::shared_ptr<Curve>(final_));
208 }
210 virtual ~Path() {}
212 // Path &operator=(Path const &other) - use default assignment operator
214 void swap(Path &other) {
215 std::swap(other.curves_, curves_);
216 std::swap(other.final_, final_);
217 std::swap(other.closed_, closed_);
218 }
220 Curve const &operator[](unsigned i) const { return *get_curves()[i]; }
221 Curve const &at_index(unsigned i) const { return *get_curves()[i]; }
222 boost::shared_ptr<Curve const> get_ref_at_index(unsigned i) {
223 return get_curves()[i];
224 }
226 Curve const &front() const { return *get_curves()[0]; }
227 Curve const &back() const { return back_open(); }
228 Curve const &back_open() const {
229 if (empty()) { THROW_RANGEERROR("Path contains not enough segments"); }
230 return *get_curves()[get_curves().size()-2];
231 }
232 Curve const &back_closed() const { return *get_curves()[get_curves().size()-1]; }
233 Curve const &back_default() const {
234 return ( closed_ ? back_closed() : back_open() );
235 }
237 const_iterator begin() const { return const_iterator(*this, 0); }
238 const_iterator end() const { return const_iterator(*this, size()); }
239 iterator begin() { return iterator(*this, 0); }
240 iterator end() { return iterator(*this, size()); }
242 const_iterator end_open() const { return const_iterator(*this, size()); }
243 const_iterator end_closed() const { return const_iterator(*this, size()+1); }
244 const_iterator end_default() const {
245 return ( closed_ ? end_closed() : end_open() );
246 }
248 size_type size_open() const { return get_curves().size()-1; }
249 size_type size_closed() const { return get_curves().size(); }
250 size_type size_default() const {
251 return ( closed_ ? size_closed() : size_open() );
252 }
253 size_type size() const { return size_open(); }
255 size_type max_size() const { return get_curves().max_size()-1; }
257 bool empty() const { return get_curves().size() == 1; }
258 bool closed() const { return closed_; }
259 void close(bool closed=true) { closed_ = closed; }
261 Rect boundsFast() const;
262 Rect boundsExact() const;
264 Piecewise<D2<SBasis> > toPwSb() const {
265 Piecewise<D2<SBasis> > ret;
266 ret.push_cut(0);
267 unsigned i = 1;
268 bool degenerate = true;
269 // pw<d2<>> is always open. so if path is closed, add closing segment as well to pwd2.
270 for(const_iterator it = begin(); it != end_default(); ++it) {
271 if (!it->isDegenerate()) {
272 ret.push(it->toSBasis(), i++);
273 degenerate = false;
274 }
275 }
276 if (degenerate) {
277 // if path only contains degenerate curves, no second cut is added
278 // so we need to create at least one segment manually
279 ret = Piecewise<D2<SBasis> >(initialPoint());
280 }
281 return ret;
282 }
284 bool operator==(Path const &other) const {
285 if (this == &other) return true;
286 if (closed_ != other.closed_) return false;
287 return get_curves() == other.get_curves();
288 }
289 bool operator!=(Path const &other) const {
290 return !( *this == other );
291 }
293 Path operator*(Matrix const &m) const {
294 Path ret(*this);
295 ret *= m;
296 return ret;
297 }
299 Path &operator*=(Matrix const &m);
301 Point pointAt(double t) const
302 {
303 unsigned int sz = size();
304 if ( closed() ) ++sz;
305 if ( t < 0 || t > sz )
306 {
307 THROW_RANGEERROR("parameter t out of bounds");
308 }
309 if ( empty() ) return Point(0,0);
310 double k, lt = modf(t, &k);
311 unsigned int i = static_cast<unsigned int>(k);
312 if ( i == sz )
313 {
314 --i;
315 lt = 1;
316 }
317 return (*this)[i].pointAt(lt);
318 }
320 double valueAt(double t, Dim2 d) const
321 {
322 unsigned int sz = size();
323 if ( closed() ) ++sz;
324 if ( t < 0 || t > sz )
325 {
326 THROW_RANGEERROR("parameter t out of bounds");
327 }
328 if ( empty() ) return 0;
329 double k, lt = modf(t, &k);
330 unsigned int i = static_cast<unsigned int>(k);
331 if ( i == sz )
332 {
333 --i;
334 lt = 1;
335 }
336 return (*this)[i].valueAt(lt, d);
337 }
340 Point operator() (double t) const
341 {
342 return pointAt(t);
343 }
345 std::vector<double> roots(double v, Dim2 d) const {
346 std::vector<double> res;
347 for(unsigned i = 0; i <= size(); i++) {
348 std::vector<double> temp = (*this)[i].roots(v, d);
349 for(unsigned j = 0; j < temp.size(); j++)
350 res.push_back(temp[j] + i);
351 }
352 return res;
353 }
355 std::vector<double>
356 allNearestPoints(Point const& _point, double from, double to) const;
358 std::vector<double>
359 allNearestPoints(Point const& _point) const
360 {
361 unsigned int sz = size();
362 if ( closed() ) ++sz;
363 return allNearestPoints(_point, 0, sz);
364 }
366 std::vector<double>
367 nearestPointPerCurve(Point const& _point) const;
369 double nearestPoint(Point const& _point, double from, double to, double *distance_squared = NULL) const;
371 double nearestPoint(Point const& _point, double *distance_squared = NULL) const
372 {
373 unsigned int sz = size();
374 if ( closed() ) ++sz;
375 return nearestPoint(_point, 0, sz, distance_squared);
376 }
378 void appendPortionTo(Path &p, double f, double t) const;
380 Path portion(double f, double t) const {
381 Path ret;
382 ret.close(false);
383 appendPortionTo(ret, f, t);
384 return ret;
385 }
386 Path portion(Interval i) const { return portion(i.min(), i.max()); }
388 Path reverse() const {
389 Path ret(*this);
390 ret.unshare();
391 for ( Sequence::iterator iter = ret.get_curves().begin() ;
392 iter != ret.get_curves().end()-1 ; ++iter )
393 {
394 *iter = boost::shared_ptr<Curve>((*iter)->reverse());
395 }
396 std::reverse(ret.get_curves().begin(), ret.get_curves().end()-1);
397 ret.final_ = static_cast<ClosingSegment *>(ret.final_->reverse());
398 ret.get_curves().back() = boost::shared_ptr<Curve>(ret.final_);
399 return ret;
400 }
402 void insert(iterator const &pos,
403 Curve const &curve, Stitching stitching=NO_STITCHING)
404 {
405 unshare();
406 Sequence::iterator seq_pos(seq_iter(pos));
407 Sequence source(1, boost::shared_ptr<Curve>(curve.duplicate()));
408 if (stitching) stitch(seq_pos, seq_pos, source);
409 do_update(seq_pos, seq_pos, source.begin(), source.end());
410 }
412 void insert(iterator const &pos,
413 const_iterator const &first,
414 const_iterator const &last,
415 Stitching stitching=NO_STITCHING)
416 {
417 unshare();
418 Sequence::iterator seq_pos(seq_iter(pos));
419 Sequence source(seq_iter(first), seq_iter(last));
420 if (stitching) stitch(seq_pos, seq_pos, source);
421 do_update(seq_pos, seq_pos, source.begin(), source.end());
422 }
424 void clear() {
425 unshare();
426 do_update(get_curves().begin(), get_curves().end()-1,
427 get_curves().begin(), get_curves().begin());
428 }
430 void erase(iterator const &pos, Stitching stitching=NO_STITCHING) {
431 unshare();
432 Sequence::iterator seq_pos(seq_iter(pos));
433 if (stitching) {
434 Sequence stitched;
435 stitch(seq_pos, seq_pos+1, stitched);
436 do_update(seq_pos, seq_pos+1, stitched.begin(), stitched.end());
437 } else {
438 do_update(seq_pos, seq_pos+1, get_curves().begin(), get_curves().begin());
439 }
440 }
442 void erase(iterator const &first,
443 iterator const &last,
444 Stitching stitching=NO_STITCHING)
445 {
446 unshare();
447 Sequence::iterator seq_first=seq_iter(first);
448 Sequence::iterator seq_last=seq_iter(last);
449 if (stitching) {
450 Sequence stitched;
451 stitch(seq_first, seq_last, stitched);
452 do_update(seq_first, seq_last, stitched.begin(), stitched.end());
453 } else {
454 do_update(seq_first, seq_last,
455 get_curves().begin(), get_curves().begin());
456 }
457 }
459 // erase last segment of path
460 void erase_last() {
461 erase(iterator(*this, size()-1));
462 }
464 void replace(iterator const &replaced,
465 Curve const &curve,
466 Stitching stitching=NO_STITCHING)
467 {
468 unshare();
469 Sequence::iterator seq_replaced(seq_iter(replaced));
470 Sequence source(1, boost::shared_ptr<Curve>(curve.duplicate()));
471 if (stitching) stitch(seq_replaced, seq_replaced+1, source);
472 do_update(seq_replaced, seq_replaced+1, source.begin(), source.end());
473 }
475 void replace(iterator const &first_replaced,
476 iterator const &last_replaced,
477 Curve const &curve, Stitching stitching=NO_STITCHING)
478 {
479 unshare();
480 Sequence::iterator seq_first_replaced(seq_iter(first_replaced));
481 Sequence::iterator seq_last_replaced(seq_iter(last_replaced));
482 Sequence source(1, boost::shared_ptr<Curve>(curve.duplicate()));
483 if (stitching) stitch(seq_first_replaced, seq_last_replaced, source);
484 do_update(seq_first_replaced, seq_last_replaced,
485 source.begin(), source.end());
486 }
488 void replace(iterator const &replaced,
489 const_iterator const &first,
490 const_iterator const &last,
491 Stitching stitching=NO_STITCHING)
492 {
493 unshare();
494 Sequence::iterator seq_replaced(seq_iter(replaced));
495 Sequence source(seq_iter(first), seq_iter(last));
496 if (stitching) stitch(seq_replaced, seq_replaced+1, source);
497 do_update(seq_replaced, seq_replaced+1, source.begin(), source.end());
498 }
500 void replace(iterator const &first_replaced,
501 iterator const &last_replaced,
502 const_iterator const &first,
503 const_iterator const &last,
504 Stitching stitching=NO_STITCHING)
505 {
506 unshare();
507 Sequence::iterator seq_first_replaced(seq_iter(first_replaced));
508 Sequence::iterator seq_last_replaced(seq_iter(last_replaced));
509 Sequence source(seq_iter(first), seq_iter(last));
510 if (stitching) stitch(seq_first_replaced, seq_last_replaced, source);
511 do_update(seq_first_replaced, seq_last_replaced,
512 source.begin(), source.end());
513 }
515 void start(Point p) {
516 clear();
517 final_->setPoint(0, p);
518 final_->setPoint(1, p);
519 }
521 Point initialPoint() const { return (*final_)[1]; }
522 Point finalPoint() const { return (*final_)[0]; }
524 void setInitial(Point const& p)
525 {
526 if ( empty() ) return;
527 unshare();
528 boost::shared_ptr<Curve> head(front().duplicate());
529 head->setInitial(p);
530 Sequence::iterator replaced = get_curves().begin();
531 Sequence source(1, head);
532 do_update(replaced, replaced + 1, source.begin(), source.end());
533 }
535 void setFinal(Point const& p)
536 {
537 if ( empty() ) return;
538 unshare();
539 boost::shared_ptr<Curve> tail(back().duplicate());
540 tail->setFinal(p);
541 Sequence::iterator replaced = get_curves().end() - 2;
542 Sequence source(1, tail);
543 do_update(replaced, replaced + 1, source.begin(), source.end());
544 }
546 void append(Curve const &curve, Stitching stitching=NO_STITCHING) {
547 unshare();
548 if (stitching) stitchTo(curve.initialPoint());
549 do_append(curve.duplicate());
550 }
551 void append(D2<SBasis> const &curve, Stitching stitching=NO_STITCHING) {
552 unshare();
553 if (stitching) stitchTo(Point(curve[X][0][0], curve[Y][0][0]));
554 do_append(new SBasisCurve(curve));
555 }
556 void append(Path const &other, Stitching stitching=NO_STITCHING) {
557 insert(end(), other.begin(), other.end(), stitching);
558 }
560 void stitchTo(Point const &p) {
561 if (!empty() && finalPoint() != p) {
562 unshare();
563 do_append(new StitchSegment(finalPoint(), p));
564 }
565 }
567 template <typename CurveType, typename A>
568 void appendNew(A a) {
569 unshare();
570 do_append(new CurveType(finalPoint(), a));
571 }
573 template <typename CurveType, typename A, typename B>
574 void appendNew(A a, B b) {
575 unshare();
576 do_append(new CurveType(finalPoint(), a, b));
577 }
579 template <typename CurveType, typename A, typename B, typename C>
580 void appendNew(A a, B b, C c) {
581 unshare();
582 do_append(new CurveType(finalPoint(), a, b, c));
583 }
585 template <typename CurveType, typename A, typename B, typename C,
586 typename D>
587 void appendNew(A a, B b, C c, D d) {
588 unshare();
589 do_append(new CurveType(finalPoint(), a, b, c, d));
590 }
592 template <typename CurveType, typename A, typename B, typename C,
593 typename D, typename E>
594 void appendNew(A a, B b, C c, D d, E e) {
595 unshare();
596 do_append(new CurveType(finalPoint(), a, b, c, d, e));
597 }
599 template <typename CurveType, typename A, typename B, typename C,
600 typename D, typename E, typename F>
601 void appendNew(A a, B b, C c, D d, E e, F f) {
602 unshare();
603 do_append(new CurveType(finalPoint(), a, b, c, d, e, f));
604 }
606 template <typename CurveType, typename A, typename B, typename C,
607 typename D, typename E, typename F,
608 typename G>
609 void appendNew(A a, B b, C c, D d, E e, F f, G g) {
610 unshare();
611 do_append(new CurveType(finalPoint(), a, b, c, d, e, f, g));
612 }
614 template <typename CurveType, typename A, typename B, typename C,
615 typename D, typename E, typename F,
616 typename G, typename H>
617 void appendNew(A a, B b, C c, D d, E e, F f, G g, H h) {
618 unshare();
619 do_append(new CurveType(finalPoint(), a, b, c, d, e, f, g, h));
620 }
622 template <typename CurveType, typename A, typename B, typename C,
623 typename D, typename E, typename F,
624 typename G, typename H, typename I>
625 void appendNew(A a, B b, C c, D d, E e, F f, G g, H h, I i) {
626 unshare();
627 do_append(new CurveType(finalPoint(), a, b, c, d, e, f, g, h, i));
628 }
630 private:
631 static Sequence::iterator seq_iter(iterator const &iter) {
632 return iter.path->get_curves().begin() + iter.index;
633 }
634 static Sequence::const_iterator seq_iter(const_iterator const &iter) {
635 return iter.path->get_curves().begin() + iter.index;
636 }
638 Sequence &get_curves() { return *curves_; }
639 Sequence const &get_curves() const { return *curves_; }
641 void unshare() {
642 if (!curves_.unique()) {
643 curves_ = boost::shared_ptr<Sequence>(new Sequence(*curves_));
644 }
645 if (!get_curves().back().unique()) {
646 final_ = static_cast<ClosingSegment *>(final_->duplicate());
647 get_curves().back() = boost::shared_ptr<Curve>(final_);
648 }
649 }
651 void stitch(Sequence::iterator first_replaced,
652 Sequence::iterator last_replaced,
653 Sequence &sequence);
655 void do_update(Sequence::iterator first_replaced,
656 Sequence::iterator last_replaced,
657 Sequence::iterator first,
658 Sequence::iterator last);
660 // n.b. takes ownership of curve object
661 void do_append(Curve *curve);
663 void check_continuity(Sequence::iterator first_replaced,
664 Sequence::iterator last_replaced,
665 Sequence::iterator first,
666 Sequence::iterator last);
668 boost::shared_ptr<Sequence> curves_;
669 ClosingSegment *final_;
670 bool closed_;
671 }; // end class Path
673 inline static Piecewise<D2<SBasis> > paths_to_pw(std::vector<Path> paths) {
674 Piecewise<D2<SBasis> > ret = paths[0].toPwSb();
675 for(unsigned i = 1; i < paths.size(); i++) {
676 ret.concat(paths[i].toPwSb());
677 }
678 return ret;
679 }
681 inline
682 Coord nearest_point(Point const& p, Path const& c)
683 {
684 return c.nearestPoint(p);
685 }
687 } // end namespace Geom
689 namespace std {
691 template <>
692 inline void swap<Geom::Path>(Geom::Path &a, Geom::Path &b)
693 {
694 a.swap(b);
695 }
697 } // end namespace std
699 #endif // SEEN_GEOM_PATH_H
704 /*
705 Local Variables:
706 mode:c++
707 c-file-style:"stroustrup"
708 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
709 indent-tabs-mode:nil
710 fill-column:99
711 End:
712 */
713 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :