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