summaryrefslogtreecommitdiffstats
path: root/src/2geom/path.h
blob: 81511b21e83d1e5612667c83bd8577fe4582465b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
/** @file
 * @brief Path - a sequence of contiguous curves
 *//*
  * Authors:
  *   MenTaLguY <mental@rydia.net>
  *   Marco Cecchetti <mrcekets at gmail.com>
  *   Krzysztof Kosiński <tweenk.pl@gmail.com>
  *
  * Copyright 2007-2014 Authors
  *
  * This library is free software; you can redistribute it and/or
  * modify it either under the terms of the GNU Lesser General Public
  * License version 2.1 as published by the Free Software Foundation
  * (the "LGPL") or, at your option, under the terms of the Mozilla
  * Public License Version 1.1 (the "MPL"). If you do not alter this
  * notice, a recipient may use your version of this file under either
  * the MPL or the LGPL.
  *
  * You should have received a copy of the LGPL along with this library
  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  * You should have received a copy of the MPL along with this library
  * in the file COPYING-MPL-1.1
  *
  * The contents of this file are subject to the Mozilla Public License
  * Version 1.1 (the "License"); you may not use this file except in
  * compliance with the License. You may obtain a copy of the License at
  * http://www.mozilla.org/MPL/
  *
  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  * the specific language governing rights and limitations.
  */

#ifndef LIB2GEOM_SEEN_PATH_H
#define LIB2GEOM_SEEN_PATH_H

#include <iterator>
#include <algorithm>
#include <iostream>
#include <boost/operators.hpp>
#include <boost/ptr_container/ptr_vector.hpp>
#include <boost/shared_ptr.hpp>
#include <2geom/intersection.h>
#include <2geom/curve.h>
#include <2geom/bezier-curve.h>
#include <2geom/transforms.h>

namespace Geom {

class Path;
class ConvexHull;

namespace PathInternal {

typedef boost::ptr_vector<Curve> Sequence;

struct PathData {
    Sequence curves;
    OptRect fast_bounds;
};

template <typename P>
class BaseIterator
    : public boost::random_access_iterator_helper
        < BaseIterator<P>
        , Curve const
        , std::ptrdiff_t
        , Curve const *
        , Curve const &
        >
{
  protected:
    BaseIterator(P &p, unsigned i) : path(&p), index(i) {}
    // default copy, default assign
    typedef BaseIterator<P> Self;

  public:
    BaseIterator() : path(NULL), index(0) {}

    bool operator<(BaseIterator const &other) const {
        return path == other.path && index < other.index;
    }
    bool operator==(BaseIterator const &other) const {
        return path == other.path && index == other.index;
    }
    Curve const &operator*() const {
        return (*path)[index];
    }

    Self &operator++() {
        ++index;
        return *this;
    }
    Self &operator--() {
        --index;
        return *this;
    }
    Self &operator+=(std::ptrdiff_t d) {
        index += d;
        return *this;
    }
    Self &operator-=(std::ptrdiff_t d) {
        index -= d;
        return *this;
    }

  private:
    P *path;
    unsigned index;

    friend class ::Geom::Path;
};

}

/** @brief Generalized time value in the path.
 *
 * This class exists because when mapping the range of multiple curves onto the same interval
 * as the curve index, we lose some precision. For instance, a path with 16 curves will
 * have 4 bits less precision than a path with 1 curve. If you need high precision results
 * in long paths, either use this class and related methods instead of the standard methods
 * pointAt(), nearestTime() and so on, or use curveAt() to first obtain the curve, then
 * call the method again to obtain a high precision result.
 * 
 * @ingroup Paths */
struct PathTime
    : boost::totally_ordered<PathTime>
{
    typedef PathInternal::Sequence::size_type size_type;

    Coord t; ///< Time value in the curve
    size_type curve_index; ///< Index of the curve in the path

    PathTime() : t(0), curve_index(0) {}
    PathTime(size_type idx, Coord tval) : t(tval), curve_index(idx) {}

    bool operator<(PathTime const &other) const {
        if (curve_index < other.curve_index) return true;
        if (curve_index == other.curve_index) {
            return t < other.t;
        }
        return false;
    }
    bool operator==(PathTime const &other) const {
        return curve_index == other.curve_index && t == other.t;
    }
    /// Convert times at or beyond 1 to 0 on the next curve.
    void normalizeForward(size_type path_size) {
        if (t >= 1) {
            curve_index = (curve_index + 1) % path_size;
            t = 0;
        }
    }
    /// Convert times at or before 0 to 1 on the previous curve.
    void normalizeBackward(size_type path_size) {
        if (t <= 0) {
            curve_index = (curve_index - 1) % path_size;
            t = 1;
        }
    }

    Coord asFlatTime() const { return curve_index + t; }
};

inline std::ostream &operator<<(std::ostream &os, PathTime const &pos) {
    os << pos.curve_index << ": " << format_coord_nice(pos.t);
    return os;
}


/** @brief Contiguous subset of the path's parameter domain.
 * This is a directed interval, which allows one to specify any contiguous subset
 * of the path's domain, including subsets that wrap around the initial point
 * of the path.
 * @ingroup Paths */
class PathInterval {
public:
    typedef PathInternal::Sequence::size_type size_type;

    /** @brief Default interval.
     * Default-constructed PathInterval includes only the initial point of the initial segment. */
    PathInterval();

    /** @brief Construct an interval in the path's parameter domain.
     * @param from Initial time
     * @param to Final time
     * @param cross_start If true, the interval will proceed from the initial to final
     *   time through the initial point of the path, wrapping around the closing segment;
     *   otherwise it will not wrap around the closing segment.
     * @param path_size Size of the path to which this interval applies, required
     *   to clean up degenerate cases */
    PathInterval(PathTime const &from, PathTime const &to, bool cross_start, size_type path_size);

    /// Get the time value of the initial point.
    PathTime const &initialTime() const { return _from; }
    /// Get the time value of the final point.
    PathTime const &finalTime() const { return _to; }

    PathTime const &from() const { return _from; }
    PathTime const &to() const { return _to; }

    /// Check whether the interval has only one point.
    bool isDegenerate() const { return _from == _to; }
    /// True if the interval goes in the direction of decreasing time values.
    bool reverse() const { return _reverse; }
    /// True if the interior of the interval contains the initial point of the path.
    bool crossesStart() const { return _cross_start; }

    /// Test a path time for inclusion.
    bool contains(PathTime const &pos) const;

    /// Get a time at least @a min_dist away in parameter space from the ends.
    /// If no such time exists, the middle point is returned.
    PathTime inside(Coord min_dist = EPSILON) const;

    /// Select one of two intervals with given endpoints by parameter direction.
    static PathInterval from_direction(PathTime const &from, PathTime const &to,
                                       bool reversed, size_type path_size);

    /// Select one of two intervals with given endpoints by whether it includes the initial point.
    static PathInterval from_start_crossing(PathTime const &from, PathTime const &to,
                                            bool cross_start, size_type path_size) {
        PathInterval result(from, to, cross_start, path_size);
        return result;
    }

    size_type pathSize() const { return _path_size; }
    size_type curveCount() const;

private:
    PathTime _from, _to;
    size_type _path_size;
    bool _cross_start, _reverse;
};

/// Create an interval in the direction of increasing time value.
/// @relates PathInterval
inline PathInterval forward_interval(PathTime const &from, PathTime const &to,
                                     PathInterval::size_type path_size)
{
    PathInterval result = PathInterval::from_direction(from, to, false, path_size);
    return result;
}

/// Create an interval in the direction of decreasing time value.
/// @relates PathInterval
inline PathInterval backward_interval(PathTime const &from, PathTime const &to,
                                      PathInterval::size_type path_size)
{
    PathInterval result = PathInterval::from_direction(from, to, true, path_size);
    return result;
}

/// Output an interval in the path's domain.
/// @relates PathInterval
inline std::ostream &operator<<(std::ostream &os, PathInterval const &ival) {
    os << "PathInterval[";
    if (ival.crossesStart()) {
        os << ival.from() << " -> 0: 0.0 -> " << ival.to();
    } else {
        os << ival.from() << " -> " << ival.to();
    }
    os << "]";
    return os;
}

typedef Intersection<PathTime> PathIntersection;

template <>
struct ShapeTraits<Path> {
    typedef PathTime TimeType;
    typedef PathInterval IntervalType;
    typedef Path AffineClosureType;
    typedef PathIntersection IntersectionType;
};

/** @brief Sequence of contiguous curves, aka spline.
 *
 * Path represents a sequence of contiguous curves, also known as a spline.
 * It corresponds to a "subpath" in SVG terminology. It can represent both
 * open and closed subpaths. The final point of each curve is exactly
 * equal to the initial point of the next curve.
 *
 * The path always contains a linear closing segment that connects
 * the final point of the last "real" curve to the initial point of the
 * first curve. This way the curves form a closed loop even for open paths.
 * If the closing segment has nonzero length and the path is closed, it is
 * considered a normal part of the path data. There are three distinct sets
 * of end iterators one can use to iterate over the segments:
 *
 * - Iterating between @a begin() and @a end() will iterate over segments
 *   which are part of the path.
 * - Iterating between @a begin() and @a end_closed()
 *   will always iterate over a closed loop of segments.
 * - Iterating between @a begin() and @a end_open() will always skip
 *   the final linear closing segment.
 *
 * If the final point of the last "real" segment coincides exactly with the initial
 * point of the first segment, the closing segment will be absent from both
 * [begin(), end_open()) and [begin(), end_closed()).
 *
 * Normally, an exception will be thrown when you try to insert a curve
 * that makes the path non-continuous. If you are working with unsanitized
 * curve data, you can call setStitching(true), which will insert line segments
 * to make the path continuous.
 *
 * Internally, Path uses copy-on-write data. This is done for two reasons: first,
 * copying a Curve requires calling a virtual function, so it's a little more expensive
 * that normal copying; and second, it reduces the memory cost of copying the path.
 * Therefore you can return Path and PathVector from functions without worrying
 * about temporary copies.
 *
 * Note that this class cannot represent arbitrary shapes, which may contain holes.
 * To do that, use PathVector, which is more generic.
 *
 * It's not very convenient to create a Path directly. To construct paths more easily,
 * use PathBuilder.
 *
 * @ingroup Paths */
class Path
    : boost::equality_comparable< Path >
{
public:
    typedef PathInternal::PathData PathData;
    typedef PathInternal::Sequence Sequence;
    typedef PathInternal::BaseIterator<Path> iterator;
    typedef PathInternal::BaseIterator<Path const> const_iterator;
    typedef Sequence::size_type size_type;
    typedef Sequence::difference_type difference_type;

    class ClosingSegment : public LineSegment {
      public:
        ClosingSegment() : LineSegment() {}
        ClosingSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
        virtual Curve *duplicate() const { return new ClosingSegment(*this); }
        virtual Curve *reverse() const { return new ClosingSegment((*this)[1], (*this)[0]); }
    };

    class StitchSegment : public LineSegment {
      public:
        StitchSegment() : LineSegment() {}
        StitchSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
        virtual Curve *duplicate() const { return new StitchSegment(*this); }
        virtual Curve *reverse() const { return new StitchSegment((*this)[1], (*this)[0]); }
    };

    // Path(Path const &other) - use default copy constructor

    /// Construct an empty path starting at the specified point.
    explicit Path(Point const &p = Point())
        : _data(new PathData())
        , _closing_seg(new ClosingSegment(p, p))
        , _closed(false)
        , _exception_on_stitch(true)
    {
        _data->curves.push_back(_closing_seg);
    }

    /// Construct a path containing a range of curves.
    template <typename Iter>
    Path(Iter first, Iter last, bool closed = false, bool stitch = false)
        : _data(new PathData())
        , _closed(closed)
        , _exception_on_stitch(!stitch)
    {
        for (Iter i = first; i != last; ++i) {
            _data->curves.push_back(i->duplicate());
        }
        if (!_data->curves.empty()) {
            _closing_seg = new ClosingSegment(_data->curves.back().finalPoint(),
                                              _data->curves.front().initialPoint());
        } else {
            _closing_seg = new ClosingSegment();
        }
        _data->curves.push_back(_closing_seg);
    }

    /// Create a path from a rectangle.
    explicit Path(Rect const &r);
    /// Create a path from a convex hull.
    explicit Path(ConvexHull const &);
    /// Create a path from a circle, using two elliptical arcs.
    explicit Path(Circle const &c);
    /// Create a path from an ellipse, using two elliptical arcs.
    explicit Path(Ellipse const &e);

    virtual ~Path() {}

    // Path &operator=(Path const &other) - use default assignment operator

    /** @brief Swap contents with another path
     * @todo Add noexcept specifiers for C++11 */
    void swap(Path &other) throw() {
        using std::swap;
        swap(other._data, _data);
        swap(other._closing_seg, _closing_seg);
        swap(other._closed, _closed);
        swap(other._exception_on_stitch, _exception_on_stitch);
    }
    /** @brief Swap contents of two paths.
     * @relates Path */
    friend inline void swap(Path &a, Path &b) throw() { a.swap(b); }

    /** @brief Access a curve by index */
    Curve const &operator[](size_type i) const { return _data->curves[i]; }
    /** @brief Access a curve by index */
    Curve const &at(size_type i) const { return _data->curves.at(i); }

    /** @brief Access the first curve in the path.
     * Since the curve always contains at least a degenerate closing segment,
     * it is always safe to use this method. */
    Curve const &front() const { return _data->curves.front(); }
    /// Alias for front().
    Curve const &initialCurve() const { return _data->curves.front(); }
    /** @brief Access the last curve in the path. */
    Curve const &back() const { return back_default(); }
    Curve const &back_open() const {
        if (empty()) return _data->curves.back();
        return _data->curves[_data->curves.size() - 2];
    }
    Curve const &back_closed() const {
        return _closing_seg->isDegenerate()
            ? _data->curves[_data->curves.size() - 2]
            : _data->curves[_data->curves.size() - 1];
    }
    Curve const &back_default() const {
        return _includesClosingSegment()
            ? back_closed()
            : back_open();
    }
    Curve const &finalCurve() const { return back_default(); }

    const_iterator begin() const { return const_iterator(*this, 0); }
    const_iterator end() const { return end_default(); }
    const_iterator end_default() const { return const_iterator(*this, size_default()); }
    const_iterator end_open() const { return const_iterator(*this, size_open()); }
    const_iterator end_closed() const { return const_iterator(*this, size_closed()); }
    iterator begin() { return iterator(*this, 0); }
    iterator end() { return end_default(); }
    iterator end_default() { return iterator(*this, size_default()); }
    iterator end_open() { return iterator(*this, size_open()); }
    iterator end_closed() { return iterator(*this, size_closed()); }

    /// Size without the closing segment, even if the path is closed.
    size_type size_open() const { return _data->curves.size() - 1; }

    /** @brief Size with the closing segment, if it makes a difference.
     * If the closing segment is degenerate, i.e. its initial and final points
     * are exactly equal, then it is not included in this size. */
    size_type size_closed() const {
        return _closing_seg->isDegenerate() ? _data->curves.size() - 1 : _data->curves.size();
    }

    /// Natural size of the path.
    size_type size_default() const {
        return _includesClosingSegment() ? size_closed() : size_open();
    }
    /// Natural size of the path.
    size_type size() const { return size_default(); }

    size_type max_size() const { return _data->curves.max_size() - 1; }

    /** @brief Check whether path is empty.
     * The path is empty if it contains only the closing segment, which according
     * to the continuity invariant must be degenerate. Note that unlike standard
     * containers, two empty paths are not necessarily identical, because the
     * degenerate closing segment may be at a different point, affecting the operation
     * of methods such as appendNew(). */
    bool empty() const { return (_data->curves.size() == 1); }

    /// Check whether the path is closed.
    bool closed() const { return _closed; }

    /** @brief Set whether the path is closed.
     * When closing a path where the last segment can be represented as a closing
     * segment, the last segment will be removed. When opening a path, the closing
     * segment will be erased. This means that closing and then opening a path
     * will not always give back the original path. */
    void close(bool closed = true);

    /** @brief Remove all curves from the path.
     * The initial and final points of the closing segment are set to (0,0).
     * The stitching flag remains unchanged. */
    void clear();

    /** @brief Get the approximate bounding box.
     * The rectangle returned by this method will contain all the curves, but it's not
     * guaranteed to be the smallest possible one */
    OptRect boundsFast() const;

    /** @brief Get a tight-fitting bounding box.
     * This will return the smallest possible axis-aligned rectangle containing
     * all the curves in the path. */
    OptRect boundsExact() const;

    Piecewise<D2<SBasis> > toPwSb() const;

    /// Test paths for exact equality.
    bool operator==(Path const &other) const;

    /// Apply a transform to each curve.
    template <typename T>
    Path &operator*=(T const &tr) {
        BOOST_CONCEPT_ASSERT((TransformConcept<T>));
        _unshare();
        for (std::size_t i = 0; i < _data->curves.size(); ++i) {
            _data->curves[i] *= tr;
        }
        return *this;
    }

    template <typename T>
    friend Path operator*(Path const &path, T const &tr) {
        BOOST_CONCEPT_ASSERT((TransformConcept<T>));
        Path result(path);
        result *= tr;
        return result;
    }

    /** @brief Get the allowed range of time values.
     * @return Values for which pointAt() and valueAt() yield valid results. */
    Interval timeRange() const;

    /** Get the curve at the specified time value.
     * @param t Time value
     * @param rest Optional storage for the corresponding time value in the curve */
    Curve const &curveAt(Coord t, Coord *rest = NULL) const;

    /// Get the closing segment of the path.
    LineSegment const &closingSegment() const { return *_closing_seg; }

    /** @brief Get the point at the specified time value.
     * Note that this method has reduced precision with respect to calling pointAt()
     * directly on the curve. If you want high precision results, use the version
     * that takes a PathTime parameter.
     * 
     * Allowed time values range from zero to the number of curves; you can retrieve
     * the allowed range of values with timeRange(). */
    Point pointAt(Coord t) const;

    /// Get one coordinate (X or Y) at the specified time value.
    Coord valueAt(Coord t, Dim2 d) const;

    /// Get the curve at the specified path time.
    Curve const &curveAt(PathTime const &pos) const;
    /// Get the point at the specified path time.
    Point pointAt(PathTime const &pos) const;
    /// Get one coordinate at the specified path time.
    Coord valueAt(PathTime const &pos, Dim2 d) const;

    Point operator()(Coord t) const { return pointAt(t); }

    /// Compute intersections with axis-aligned line.
    std::vector<PathTime> roots(Coord v, Dim2 d) const;

    /// Compute intersections with another path.
    std::vector<PathIntersection> intersect(Path const &other, Coord precision = EPSILON) const;

    /** @brief Determine the winding number at the specified point.
     * 
     * The winding number is the number of full turns made by a ray that connects the passed
     * point and the path's value (i.e. the result of the pointAt() method) as the time increases
     * from 0 to the maximum valid value. Positive numbers indicate turns in the direction
     * of increasing angles.
     *
     * Winding numbers are often used as the definition of what is considered "inside"
     * the shape. Typically points with either nonzero winding or odd winding are
     * considered to be inside the path. */
    int winding(Point const &p) const;

    std::vector<Coord> allNearestTimes(Point const &p, Coord from, Coord to) const;
    std::vector<Coord> allNearestTimes(Point const &p) const {
        return allNearestTimes(p, 0, size_default());
    }

    PathTime nearestTime(Point const &p, Coord *dist = NULL) const;
    std::vector<Coord> nearestTimePerCurve(Point const &p) const;

    std::vector<Point> nodes() const;

    void appendPortionTo(Path &p, Coord f, Coord t) const;

    /** @brief Append a subset of this path to another path.
     * An extra stitching segment will be inserted if the start point of the portion
     * and the final point of the target path do not match exactly.
     * The closing segment of the target path will be modified. */
    void appendPortionTo(Path &p, PathTime const &from, PathTime const &to, bool cross_start = false) const {
        PathInterval ival(from, to, cross_start, size_closed());
        appendPortionTo(p, ival, boost::none, boost::none);
    }

    /** @brief Append a subset of this path to another path.
     * This version allows you to explicitly pass a PathInterval. */
    void appendPortionTo(Path &p, PathInterval const &ival) const {
        appendPortionTo(p, ival, boost::none, boost::none);
    }

    /** @brief Append a subset of this path to another path, specifying endpoints.
     * This method is for use in situations where endpoints of the portion segments
     * have to be set exactly, for instance when computing Boolean operations. */
    void appendPortionTo(Path &p, PathInterval const &ival,
                         boost::optional<Point> const &p_from, boost::optional<Point> const &p_to) const;

    Path portion(Coord f, Coord t) const {
        Path ret;
        ret.close(false);
        appendPortionTo(ret, f, t);
        return ret;
    }

    Path portion(Interval const &i) const { return portion(i.min(), i.max()); }

    /** @brief Get a subset of the current path with full precision.
     * When @a from is larger (later in the path) than @a to, the returned portion
     * will be reversed. If @a cross_start is true, the portion will be reversed
     * and will cross the initial point of the path. Therefore, when @a from is larger
     * than @a to and @a cross_start is true, the returned portion will not be reversed,
     * but will "wrap around" the end of the path. */
    Path portion(PathTime const &from, PathTime const &to, bool cross_start = false) const {
        Path ret;
        ret.close(false);
        appendPortionTo(ret, from, to, cross_start);
        return ret;
    }

    /** @brief Get a subset of the current path with full precision.
     * This version allows you to explicitly pass a PathInterval. */
    Path portion(PathInterval const &ival) const {
        Path ret;
        ret.close(false);
        appendPortionTo(ret, ival);
        return ret;
    }

    /** @brief Obtain a reversed version of the current path.
     * The final point of the current path will become the initial point
     * of the reversed path, unless it is closed and has a non-degenerate
     * closing segment. In that case, the new initial point will be the final point
     * of the last "real" segment. */
    Path reversed() const;

    void insert(iterator pos, Curve const &curve);
    
    template <typename Iter>
    void insert(iterator pos, Iter first, Iter last) {
        _unshare();
        Sequence::iterator seq_pos(seq_iter(pos));
        Sequence source;
        for (; first != last; ++first) {
            source.push_back(first->duplicate());
        }
        do_update(seq_pos, seq_pos, source);
    }

    void erase(iterator pos);
    void erase(iterator first, iterator last);

    // erase last segment of path
    void erase_last() { erase(iterator(*this, size() - 1)); }

    void start(Point const &p);

    /** @brief Get the first point in the path. */
    Point initialPoint() const { return (*_closing_seg)[1]; }

    /** @brief Get the last point in the path.
     * If the path is closed, this is always the same as the initial point. */
    Point finalPoint() const { return (*_closing_seg)[_closed ? 1 : 0]; }

    void setInitial(Point const &p) {
        _unshare();
        _closed = false;
        _data->curves.front().setInitial(p);
        _closing_seg->setFinal(p);
    }
    void setFinal(Point const &p) {
        _unshare();
        _closed = false;
        _data->curves[size_open() - 1].setFinal(p);
        _closing_seg->setInitial(p);
    }

    /** @brief Add a new curve to the end of the path.
     * This inserts the new curve right before the closing segment.
     * The path takes ownership of the passed pointer, which should not be freed. */
    void append(Curve *curve) {
        _unshare();
        stitchTo(curve->initialPoint());
        do_append(curve);
    }

    void append(Curve const &curve) {
        _unshare();
        stitchTo(curve.initialPoint());
        do_append(curve.duplicate());
    }
    void append(D2<SBasis> const &curve) {
        _unshare();
        stitchTo(Point(curve[X][0][0], curve[Y][0][0]));
        do_append(new SBasisCurve(curve));
    }
    void append(Path const &other) {
        replace(end_open(), other.begin(), other.end());
    }

    void replace(iterator replaced, Curve const &curve);
    void replace(iterator first, iterator last, Curve const &curve);
    void replace(iterator replaced, Path const &path);
    void replace(iterator first, iterator last, Path const &path);

    template <typename Iter>
    void replace(iterator replaced, Iter first, Iter last) {
        replace(replaced, replaced + 1, first, last);
    }

    template <typename Iter>
    void replace(iterator first_replaced, iterator last_replaced, Iter first, Iter last) {
        _unshare();
        Sequence::iterator seq_first_replaced(seq_iter(first_replaced));
        Sequence::iterator seq_last_replaced(seq_iter(last_replaced));
        Sequence source;
        for (; first != last; ++first) {
            source.push_back(first->duplicate());
        }
        do_update(seq_first_replaced, seq_last_replaced, source);
    }

    /** @brief Append a new curve to the path.
     *
     * This family of methods will automatically use the current final point of the path
     * as the first argument of the new curve's constructor. To call this method,
     * you'll need to write e.g.:
     * @code
       path.template appendNew<CubicBezier>(control1, control2, end_point);
       @endcode
     * It is important to note that the coordinates passed to appendNew should be finite!
     * If one of the coordinates is infinite, 2geom will throw a ContinuityError exception.
     */
    template <typename CurveType, typename A>
    void appendNew(A a) {
        _unshare();
        do_append(new CurveType(finalPoint(), a));
    }

    template <typename CurveType, typename A, typename B>
    void appendNew(A a, B b) {
        _unshare();
        do_append(new CurveType(finalPoint(), a, b));
    }

    template <typename CurveType, typename A, typename B, typename C>
    void appendNew(A a, B b, C c) {
        _unshare();
        do_append(new CurveType(finalPoint(), a, b, c));
    }

    template <typename CurveType, typename A, typename B, typename C, typename D>
    void appendNew(A a, B b, C c, D d) {
        _unshare();
        do_append(new CurveType(finalPoint(), a, b, c, d));
    }

    template <typename CurveType, typename A, typename B, typename C, typename D, typename E>
    void appendNew(A a, B b, C c, D d, E e) {
        _unshare();
        do_append(new CurveType(finalPoint(), a, b, c, d, e));
    }

    template <typename CurveType, typename A, typename B, typename C, typename D, typename E, typename F>
    void appendNew(A a, B b, C c, D d, E e, F f) {
        _unshare();
        do_append(new CurveType(finalPoint(), a, b, c, d, e, f));
    }

    template <typename CurveType, typename A, typename B, typename C, typename D, typename E, typename F, typename G>
    void appendNew(A a, B b, C c, D d, E e, F f, G g) {
        _unshare();
        do_append(new CurveType(finalPoint(), a, b, c, d, e, f, g));
    }

    template <typename CurveType, typename A, typename B, typename C, typename D, typename E, typename F, typename G,
              typename H>
    void appendNew(A a, B b, C c, D d, E e, F f, G g, H h) {
        _unshare();
        do_append(new CurveType(finalPoint(), a, b, c, d, e, f, g, h));
    }

    template <typename CurveType, typename A, typename B, typename C, typename D, typename E, typename F, typename G,
              typename H, typename I>
    void appendNew(A a, B b, C c, D d, E e, F f, G g, H h, I i) {
        _unshare();
        do_append(new CurveType(finalPoint(), a, b, c, d, e, f, g, h, i));
    }

    /** @brief Reduce the closing segment to a point if it's shorter than precision.
     * Do this by moving the final point. */
    void snapEnds(Coord precision = EPSILON);

    /// Append a stitching segment ending at the specified point.
    void stitchTo(Point const &p);

    /** @brief Verify the continuity invariant.
     * If the path is not contiguous, this will throw a CountinuityError. */
    void checkContinuity() const;

    /** @brief Enable or disable the throwing of exceptions when stitching discontinuities.
     * Normally stitching will cause exceptions, but when you are working with unsanitized
     * curve data, you can disable these exceptions. */
    void setStitching(bool x) {
        _exception_on_stitch = !x;
    }

private:
    static Sequence::iterator seq_iter(iterator const &iter) {
        return iter.path->_data->curves.begin() + iter.index;
    }
    static Sequence::const_iterator seq_iter(const_iterator const &iter) {
        return iter.path->_data->curves.begin() + iter.index;
    }

    // whether the closing segment is part of the path
    bool _includesClosingSegment() const {
        return _closed && !_closing_seg->isDegenerate();
    }
    void _unshare() {
        // Called before every mutation.
        // Ensure we have our own copy of curve data and reset cached values
        if (!_data.unique()) {
            _data.reset(new PathData(*_data));
            _closing_seg = static_cast<ClosingSegment*>(&_data->curves.back());
        }
        _data->fast_bounds = OptRect();
    }
    PathTime _factorTime(Coord t) const;

    void stitch(Sequence::iterator first_replaced, Sequence::iterator last_replaced, Sequence &sequence);
    void do_update(Sequence::iterator first, Sequence::iterator last, Sequence &source);

    // n.b. takes ownership of curve object
    void do_append(Curve *curve);

    boost::shared_ptr<PathData> _data;
    ClosingSegment *_closing_seg;
    bool _closed;
    bool _exception_on_stitch;
}; // end class Path

Piecewise<D2<SBasis> > paths_to_pw(PathVector const &paths);

inline Coord nearest_time(Point const &p, Path const &c) {
    PathTime pt = c.nearestTime(p);
    return pt.curve_index + pt.t;
}

bool are_near(Path const &a, Path const &b, Coord precision = EPSILON);

std::ostream &operator<<(std::ostream &out, Path const &path);

} // end namespace Geom


#endif // LIB2GEOM_SEEN_PATH_H

/*
  Local Variables:
  mode:c++
  c-file-style:"stroustrup"
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  indent-tabs-mode:nil
  fill-column:99
  End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :