path: root/src/2geom/path.cpp

/** @file
 * @brief Path - a sequence of contiguous curves (implementation file)
 *//*
 * 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.
 */

#include <2geom/path.h>
#include <2geom/pathvector.h>
#include <2geom/transforms.h>
#include <2geom/convex-hull.h>
#include <algorithm>
#include <limits>

using std::swap;
using namespace Geom::PathInternal;

namespace Geom {

// this represents an empty interval
PathInterval::PathInterval()
    : _from(0, 0.0)
    , _to(0, 0.0)
    , _path_size(1)
    , _cross_start(false)
    , _reverse(false)
{}

PathInterval::PathInterval(Position const &from, Position const &to, bool cross_start, size_type path_size)
    : _from(from)
    , _to(to)
    , _path_size(path_size)
    , _cross_start(cross_start)
    , _reverse(cross_start ? to >= from : to < from)
{
    if (_reverse) {
        _to.normalizeForward(_path_size);
        if (_from != _to) {
            _from.normalizeBackward(_path_size);
        }
    } else {
        _from.normalizeForward(_path_size);
        if (_from != _to) {
            _to.normalizeBackward(_path_size);
        }
    }

    if (_from == _to) {
        _reverse = false;
        _cross_start = false;
    }
}

bool PathInterval::contains(Position const &pos) const {
    if (_cross_start) {
        if (_reverse) {
            return pos >= _to || _from >= pos;
        } else {
            return pos >= _from || _to >= pos;
        }
    } else {
        if (_reverse) {
            return _to <= pos && pos <= _from;
        } else {
            return _from <= pos && pos <= _to;
        }
    }
}

PathPosition PathInterval::inside(Coord min_dist) const
{
    // If there is some node further than min_dist (in time coord) from the ends,
    // return that node. Otherwise, return the middle.
    PathPosition result(0, 0.0);

    if (!_cross_start && _from.curve_index == _to.curve_index) {
        PathPosition result(_from.curve_index, lerp(0.5, _from.t, _to.t));
        return result;
    }
    // If _cross_start, then we can be sure that at least one node is in the domain.
    // If dcurve == 0, it actually means that all curves are included in the domain

    if (_reverse) {
        size_type dcurve = (_path_size + _from.curve_index - _to.curve_index) % _path_size;
        bool from_close = _from.t < min_dist;
        bool to_close = _to.t > 1 - min_dist;

        if (dcurve == 0) {
            dcurve = _path_size;
        }

        if (dcurve == 1) {
            if (from_close || to_close) {
                result.curve_index = _from.curve_index;
                Coord tmid = _from.t - ((1 - _to.t) + _from.t) * 0.5;
                if (tmid < 0) {
                    result.curve_index = (_path_size + result.curve_index - 1) % _path_size;
                    tmid += 1;
                }
                result.t = tmid;
                return result;
            }

            result.curve_index = _from.curve_index;
            return result;
        }

        result.curve_index = (_to.curve_index + 1) % _path_size;
        if (to_close) {
            if (dcurve == 2) {
                result.t = 0.5;
            } else {
                result.curve_index = (result.curve_index + 1) % _path_size;
            }
        }
        return result;
    } else {
        size_type dcurve = (_path_size + _to.curve_index - _from.curve_index) % _path_size;
        bool from_close = _from.t > 1 - min_dist;
        bool to_close = _to.t < min_dist;

        if (dcurve == 0) {
            dcurve = _path_size;
        }

        if (dcurve == 1) {
            if (from_close || to_close) {
                result.curve_index = _from.curve_index;
                Coord tmid = ((1 - _from.t) + _to.t) * 0.5 + _from.t;
                if (tmid >= 1) {
                    result.curve_index = (result.curve_index + 1) % _path_size;
                    tmid -= 1;
                }
                result.t = tmid;
                return result;
            }

            result.curve_index = _to.curve_index;
            return result;
        }

        result.curve_index = (_from.curve_index + 1) % _path_size;
        if (from_close) {
            if (dcurve == 2) {
                result.t = 0.5;
            } else {
                result.curve_index = (result.curve_index + 1) % _path_size;
            }
        }
        return result;
    }

    result.curve_index = _reverse ? _from.curve_index : _to.curve_index;
    return result;
}

PathInterval PathInterval::from_direction(Position const &from, Position const &to, bool reversed, size_type path_size)
{
    PathInterval result;
    result._from = from;
    result._to = to;
    result._path_size = path_size;

    if (reversed) {
        result._to.normalizeForward(path_size);
        if (result._from != result._to) {
            result._from.normalizeBackward(path_size);
        }
    } else {
        result._from.normalizeForward(path_size);
        if (result._from != result._to) {
            result._to.normalizeBackward(path_size);
        }
    }

    if (result._from == result._to) {
        result._reverse = false;
        result._cross_start = false;
    } else {
        result._reverse = reversed;
        if (reversed) {
            result._cross_start = from < to;
        } else {
            result._cross_start = to < from;
        }
    }
    return result;
}


Path::Path(ConvexHull const &ch)
    : _curves(new Sequence())
    , _closing_seg(new ClosingSegment(Point(), Point()))
    , _closed(false)
    , _exception_on_stitch(true)
{
    if (ch.empty()) {
        _curves->push_back(_closing_seg);
        return;
    }

    _closing_seg->setInitial(ch.back());
    _closing_seg->setFinal(ch.front());

    Point last = ch.front();

    for (std::size_t i = 1; i < ch.size(); ++i) {
        _curves->push_back(new LineSegment(last, ch[i]));
        last = ch[i];
    }

    _curves->push_back(_closing_seg);
    _closed = true;
}

void Path::clear()
{
    _unshare();
    _curves->pop_back().release();
    _curves->clear();
    _closing_seg->setInitial(Point(0, 0));
    _closing_seg->setFinal(Point(0, 0));
    _curves->push_back(_closing_seg);
    _closed = false;
}

OptRect Path::boundsFast() const
{
    OptRect bounds;
    if (empty())
        return bounds;
    bounds = front().boundsFast();
    const_iterator iter = begin();
    // the closing path segment can be ignored, because it will always lie within the bbox of the rest of the path
    if (iter != end()) {
        for (++iter; iter != end(); ++iter) {
            bounds.unionWith(iter->boundsFast());
        }
    }
    return bounds;
}

OptRect Path::boundsExact() const
{
    OptRect bounds;
    if (empty())
        return bounds;
    bounds = front().boundsExact();
    const_iterator iter = begin();
    // the closing path segment can be ignored, because it will always lie within the bbox of the rest of the path
    if (iter != end()) {
        for (++iter; iter != end(); ++iter) {
            bounds.unionWith(iter->boundsExact());
        }
    }
    return bounds;
}

Piecewise<D2<SBasis> > Path::toPwSb() const
{
    Piecewise<D2<SBasis> > ret;
    ret.push_cut(0);
    unsigned i = 1;
    bool degenerate = true;
    // pw<d2<>> is always open. so if path is closed, add closing segment as well to pwd2.
    for (const_iterator it = begin(); it != end_default(); ++it) {
        if (!it->isDegenerate()) {
            ret.push(it->toSBasis(), i++);
            degenerate = false;
        }
    }
    if (degenerate) {
        // if path only contains degenerate curves, no second cut is added
        // so we need to create at least one segment manually
        ret = Piecewise<D2<SBasis> >(initialPoint());
    }
    return ret;
}

template <typename iter>
iter inc(iter const &x, unsigned n) {
    iter ret = x;
    for (unsigned i = 0; i < n; i++)
        ret++;
    return ret;
}

bool Path::operator==(Path const &other) const
{
    if (this == &other)
        return true;
    if (_closed != other._closed)
        return false;
    return *_curves == *other._curves;
}

Path &Path::operator*=(Affine const &m)
{
    _unshare();
    Sequence::iterator last = _curves->end() - 1;
    Sequence::iterator it;

    for (it = _curves->begin(); it != last; ++it) {
        it->transform(m);
    }
    _closing_seg->transform(m);
    checkContinuity();
    return *this;
}

void Path::start(Point const &p) {
    if (_curves->size() > 1) {
        clear();
    }
    _closing_seg->setInitial(p);
    _closing_seg->setFinal(p);
}

Interval Path::timeRange() const
{
    Interval ret(0, size_default());
    return ret;
}

Curve const &Path::curveAt(Coord t, Coord *rest) const
{
    Position pos = _getPosition(t);
    if (rest) {
        *rest = pos.t;
    }
    return at(pos.curve_index);
}

Point Path::pointAt(Coord t) const
{
    return pointAt(_getPosition(t));
}

Coord Path::valueAt(Coord t, Dim2 d) const
{
    return valueAt(_getPosition(t), d);
}

Curve const &Path::curveAt(Position const &pos) const
{
    return at(pos.curve_index);
}
Point Path::pointAt(Position const &pos) const
{
    return at(pos.curve_index).pointAt(pos.t);
}
Coord Path::valueAt(Position const &pos, Dim2 d) const
{
    return at(pos.curve_index).valueAt(pos.t, d);
}

std::vector<PathPosition> Path::roots(Coord v, Dim2 d) const
{
    std::vector<PathPosition> res;
    for (unsigned i = 0; i <= size(); i++) {
        std::vector<Coord> temp = (*this)[i].roots(v, d);
        for (unsigned j = 0; j < temp.size(); j++)
            res.push_back(PathPosition(i, temp[j]));
    }
    return res;
}

std::vector<PathIntersection> Path::intersect(Path const &other, Coord precision) const
{
    std::vector<PathIntersection> result;

    // TODO: sweepline optimization
    // TODO: remove multiple intersections within precision of each other?
    for (size_type i = 0; i < size(); ++i) {
        for (size_type j = 0; j < other.size(); ++j) {
            std::vector<CurveIntersection> cx = (*this)[i].intersect(other[j], precision);
            for (std::size_t ci = 0; ci < cx.size(); ++ci) {
                PathPosition a(i, cx[ci].first), b(j, cx[ci].second);
                PathIntersection px(a, b, cx[ci].point());
                result.push_back(px);
            }
        }
    }

    return result;
}

int Path::winding(Point const &p) const {
    int wind = 0;

    /* To handle all the edge cases, we consider the maximum Y edge of the bounding box
     * as not included in box. This way paths that contain linear horizontal
     * segments will be treated correctly. */
    for (const_iterator i = begin(); i != end_closed(); ++i) {
        Rect bounds = i->boundsFast();

        if (bounds.height() == 0) continue;
        if (p[X] > bounds.right() || !bounds[Y].lowerContains(p[Y])) {
            // Ray doesn't intersect bbox, so we ignore this segment
            continue;
        }

        if (p[X] < bounds.left()) {
            /* Ray intersects the curve's bbox, but the point is outside it.
             * The winding contribution is exactly the same as that
             * of a linear segment with the same initial and final points. */
            Point ip = i->initialPoint();
            Point fp = i->finalPoint();
            Rect eqbox(ip, fp);

            if (eqbox[Y].lowerContains(p[Y])) {
                /* The ray intersects the equivalent linear segment.
                 * Determine winding contribution based on its derivative. */
                if (ip[Y] < fp[Y]) {
                    wind += 1;
                } else if (ip[Y] > fp[Y]) {
                    wind -= 1;
                } else {
                    // should never happen, because bounds.height() was not zero
                    assert(false);
                }
            }
        } else {
            // point is inside bbox
            wind += i->winding(p);
        }
    }
    return wind;
}

std::vector<double> Path::allNearestTimes(Point const &_point, double from, double to) const
{
    // TODO from and to are not used anywhere.
    // rewrite this to simplify.
    using std::swap;

    if (from > to)
        swap(from, to);
    const Path &_path = *this;
    unsigned int sz = _path.size();
    if (_path.closed())
        ++sz;
    if (from < 0 || to > sz) {
        THROW_RANGEERROR("[from,to] interval out of bounds");
    }
    double sif, st = modf(from, &sif);
    double eif, et = modf(to, &eif);
    unsigned int si = static_cast<unsigned int>(sif);
    unsigned int ei = static_cast<unsigned int>(eif);
    if (si == sz) {
        --si;
        st = 1;
    }
    if (ei == sz) {
        --ei;
        et = 1;
    }
    if (si == ei) {
        std::vector<double> all_nearest = _path[si].allNearestTimes(_point, st, et);
        for (unsigned int i = 0; i < all_nearest.size(); ++i) {
            all_nearest[i] = si + all_nearest[i];
        }
        return all_nearest;
    }
    std::vector<double> all_t;
    std::vector<std::vector<double> > all_np;
    all_np.push_back(_path[si].allNearestTimes(_point, st));
    std::vector<unsigned int> ni;
    ni.push_back(si);
    double dsq;
    double mindistsq = distanceSq(_point, _path[si].pointAt(all_np.front().front()));
    Rect bb(Geom::Point(0, 0), Geom::Point(0, 0));
    for (unsigned int i = si + 1; i < ei; ++i) {
        bb = (_path[i].boundsFast());
        dsq = distanceSq(_point, bb);
        if (mindistsq < dsq)
            continue;
        all_t = _path[i].allNearestTimes(_point);
        dsq = distanceSq(_point, _path[i].pointAt(all_t.front()));
        if (mindistsq > dsq) {
            all_np.clear();
            all_np.push_back(all_t);
            ni.clear();
            ni.push_back(i);
            mindistsq = dsq;
        } else if (mindistsq == dsq) {
            all_np.push_back(all_t);
            ni.push_back(i);
        }
    }
    bb = (_path[ei].boundsFast());
    dsq = distanceSq(_point, bb);
    if (mindistsq >= dsq) {
        all_t = _path[ei].allNearestTimes(_point, 0, et);
        dsq = distanceSq(_point, _path[ei].pointAt(all_t.front()));
        if (mindistsq > dsq) {
            for (unsigned int i = 0; i < all_t.size(); ++i) {
                all_t[i] = ei + all_t[i];
            }
            return all_t;
        } else if (mindistsq == dsq) {
            all_np.push_back(all_t);
            ni.push_back(ei);
        }
    }
    std::vector<double> all_nearest;
    for (unsigned int i = 0; i < all_np.size(); ++i) {
        for (unsigned int j = 0; j < all_np[i].size(); ++j) {
            all_nearest.push_back(ni[i] + all_np[i][j]);
        }
    }
    all_nearest.erase(std::unique(all_nearest.begin(), all_nearest.end()), all_nearest.end());
    return all_nearest;
}

std::vector<Coord> Path::nearestTimePerCurve(Point const &p) const
{
    // return a single nearest time for each curve in this path
    std::vector<Coord> np;
    for (const_iterator it = begin(); it != end_default(); ++it) {
        np.push_back(it->nearestTime(p));
    }
    return np;
}

Coord Path::nearestTime(Point const &p, Coord *dist) const
{
    Position pos = nearestPosition(p, dist);
    return pos.curve_index + pos.t;
}

PathPosition Path::nearestPosition(Point const &p, Coord *dist) const
{
    Coord mindist = std::numeric_limits<Coord>::max();
    Position ret;

    if (_curves->size() == 1) {
        // naked moveto
        ret.curve_index = 0;
        ret.t = 0;
        if (dist) {
            *dist = distance(_closing_seg->initialPoint(), p);
        }
        return ret;
    }

    for (size_type i = 0; i < size_default(); ++i) {
        Curve const &c = at(i);
        if (distance(p, c.boundsFast()) >= mindist) continue;

        Coord t = c.nearestTime(p);
        Coord d = distance(c.pointAt(t), p);
        if (d < mindist) {
            mindist = d;
            ret.curve_index = i;
            ret.t = t;
        }
    }
    if (dist) {
        *dist = mindist;
    }

    return ret;
}

void Path::appendPortionTo(Path &ret, double from, double to) const
{
    if (!(from >= 0 && to >= 0)) {
        THROW_RANGEERROR("from and to must be >=0 in Path::appendPortionTo");
    }
    if (to == 0)
        to = size() + 0.999999;
    if (from == to) {
        return;
    }
    double fi, ti;
    double ff = modf(from, &fi), tf = modf(to, &ti);
    if (tf == 0) {
        ti--;
        tf = 1;
    }
    const_iterator fromi = inc(begin(), (unsigned)fi);
    if (fi == ti && from < to) {
        ret.append(fromi->portion(ff, tf));
        return;
    }
    const_iterator toi = inc(begin(), (unsigned)ti);
    if (ff != 1.) {
        // fromv->setInitial(ret.finalPoint());
        ret.append(fromi->portion(ff, 1.));
    }
    if (from >= to) {
        const_iterator ender = end();
        if (ender->initialPoint() == ender->finalPoint())
            ++ender;
        ret.insert(ret.end(), ++fromi, ender);
        ret.insert(ret.end(), begin(), toi);
    } else {
        ret.insert(ret.end(), ++fromi, toi);
    }
    ret.append(toi->portion(0., tf));
}

void Path::appendPortionTo(Path &target, PathInterval const &ival,
                           boost::optional<Point> const &p_from, boost::optional<Point> const &p_to) const
{
    assert(ival.pathSize() == size_closed());

    if (ival.isDegenerate()) {
        Point stitch_to = p_from ? *p_from : pointAt(ival.from());
        target.stitchTo(stitch_to);
        return;
    }

    Position const &from = ival.from(), &to = ival.to();

    bool reverse = ival.reverse();
    int di = reverse ? -1 : 1;
    size_type s = size_closed();

    if (!ival.crossesStart() && from.curve_index == to.curve_index) {
        Curve *c = (*this)[from.curve_index].portion(from.t, to.t);
        if (p_from) {
            c->setInitial(*p_from);
        }
        if (p_to) {
            c->setFinal(*p_to);
        }
        target.append(c);
    } else {
        Curve *c_first = (*this)[from.curve_index].portion(from.t, reverse ? 0 : 1);
        if (p_from) {
            c_first->setInitial(*p_from);
        }
        target.append(c_first);

        for (size_type i = (from.curve_index + s + di) % s; i != to.curve_index;
             i = (i + s + di) % s)
        {
            if (reverse) {
                target.append((*this)[i].reverse());
            } else {
                target.append((*this)[i].duplicate());
            }
        }

        Curve *c_last = (*this)[to.curve_index].portion(reverse ? 1 : 0, to.t);
        if (p_to) {
            c_last->setFinal(*p_to);
        }
        target.append(c_last);
    }
}

Path Path::reversed() const
{
    typedef std::reverse_iterator<Sequence::const_iterator> RIter;

    Path ret;
    ret._curves->pop_back();
    RIter iter(_curves->end()), rend(_curves->begin());
    for (; iter != rend; ++iter) {
        ret._curves->push_back(iter->reverse());
    }
    ret._closing_seg = static_cast<ClosingSegment *>(ret._closing_seg->reverse());
    ret._curves->push_back(ret._closing_seg);
    return ret;
}


void Path::insert(iterator pos, Curve const &curve)
{
    _unshare();
    Sequence::iterator seq_pos(seq_iter(pos));
    Sequence source;
    source.push_back(curve.duplicate());
    do_update(seq_pos, seq_pos, source);
}

void Path::erase(iterator pos)
{
    _unshare();
    Sequence::iterator seq_pos(seq_iter(pos));

    Sequence stitched;
    do_update(seq_pos, seq_pos + 1, stitched);
}

void Path::erase(iterator first, iterator last)
{
    _unshare();
    Sequence::iterator seq_first = seq_iter(first);
    Sequence::iterator seq_last = seq_iter(last);

    Sequence stitched;
    do_update(seq_first, seq_last, stitched);
}

void Path::stitchTo(Point const &p)
{
    if (!empty() && _closing_seg->initialPoint() != p) {
        if (_exception_on_stitch) {
            THROW_CONTINUITYERROR();
        }
        _unshare();
        do_append(new StitchSegment(_closing_seg->initialPoint(), p));
    }
}

void Path::replace(iterator replaced, Curve const &curve)
{
    replace(replaced, replaced + 1, curve);
}

void Path::replace(iterator first_replaced, iterator last_replaced, Curve const &curve)
{
    _unshare();
    Sequence::iterator seq_first_replaced(seq_iter(first_replaced));
    Sequence::iterator seq_last_replaced(seq_iter(last_replaced));
    Sequence source(1);
    source.push_back(curve.duplicate());

    do_update(seq_first_replaced, seq_last_replaced, source);
}

void Path::replace(iterator replaced, Path const &path)
{
    replace(replaced, path.begin(), path.end());
}

void Path::replace(iterator first, iterator last, Path const &path)
{
    replace(first, last, path.begin(), path.end());
}

void Path::snapEnds(Coord precision)
{
    if (!_closed) return;
    if (_curves->size() > 1 && are_near(_closing_seg->length(precision), 0, precision)) {
        _unshare();
        _closing_seg->setInitial(_closing_seg->finalPoint());
        (_curves->end() - 1)->setFinal(_closing_seg->finalPoint());
    }
}

// replace curves between first and last with contents of source,
// 
void Path::do_update(Sequence::iterator first, Sequence::iterator last, Sequence &source)
{
    // TODO: handle cases where first > last in closed paths?
    bool last_beyond_closing_segment = (last == _curves->end());

    // special case:
    // if do_update replaces the closing segment, we have to regenerate it
    if (source.empty()) {
        if (first == last) return; // nothing to do

        // only removing some segments
        if ((!_closed && first == _curves->begin()) || (!_closed && last == _curves->end() - 1) || last_beyond_closing_segment) {
            // just adjust the closing segment
            // do nothing
        } else if (first->initialPoint() != (last - 1)->finalPoint()) {
            if (_exception_on_stitch) {
                THROW_CONTINUITYERROR();
            }
            source.push_back(new StitchSegment(first->initialPoint(), (last - 1)->finalPoint()));
        }
    } else {
        // replacing
        if (first == _curves->begin() && last == _curves->end()) {
            // special case: replacing everything should work the same in open and closed curves
            _curves->erase(_curves->begin(), _curves->end() - 1);
            _closing_seg->setFinal(source.front().initialPoint());
            _closing_seg->setInitial(source.back().finalPoint());
            _curves->transfer(_curves->begin(), source.begin(), source.end(), source);
            return;
        }

        // stitch in front
        if (!_closed && first == _curves->begin()) {
            // not necessary to stitch in front
        } else if (first->initialPoint() != source.front().initialPoint()) {
            if (_exception_on_stitch) {
                THROW_CONTINUITYERROR();
            }
            source.insert(source.begin(), new StitchSegment(first->initialPoint(), source.front().initialPoint()));
        }

        // stitch at the end
        if ((!_closed && last == _curves->end() - 1) || last_beyond_closing_segment) {
            // repurpose the closing segment as the stitch segment
            // do nothing
        } else if (source.back().finalPoint() != (last - 1)->finalPoint()) {
            if (_exception_on_stitch) {
                THROW_CONTINUITYERROR();
            }
            source.push_back(new StitchSegment(source.back().finalPoint(), (last - 1)->finalPoint()));
        }
    }

    // do not erase the closing segment, adjust it instead
    if (last_beyond_closing_segment) {
        --last;
    }
    _curves->erase(first, last);
    _curves->transfer(first, source.begin(), source.end(), source);

    // adjust closing segment
    if (size_open() == 0) {
        _closing_seg->setFinal(_closing_seg->initialPoint());
    } else {
        _closing_seg->setInitial(back_open().finalPoint());
        _closing_seg->setFinal(front().initialPoint());
    }

    checkContinuity();
}

void Path::do_append(Curve *c)
{
    if (&_curves->front() == _closing_seg) {
        _closing_seg->setFinal(c->initialPoint());
    } else {
        // if we can't freely move the closing segment, we check whether
        // the new curve connects with the last non-closing curve
        if (c->initialPoint() != _closing_seg->initialPoint()) {
            THROW_CONTINUITYERROR();
        }
    }
    _curves->insert(_curves->end() - 1, c);
    _closing_seg->setInitial(c->finalPoint());
}

void Path::checkContinuity() const
{
    Sequence::const_iterator i = _curves->begin(), j = _curves->begin();
    ++j;
    for (; j != _curves->end(); ++i, ++j) {
        if (i->finalPoint() != j->initialPoint()) {
            THROW_CONTINUITYERROR();
        }
    }
    if (_curves->front().initialPoint() != _curves->back().finalPoint()) {
        THROW_CONTINUITYERROR();
    }
}

PathPosition Path::_getPosition(Coord t) const
{
    size_type sz = size_default();
    if (t < 0 || t > sz) {
        THROW_RANGEERROR("parameter t out of bounds");
    }

    Position ret;
    Coord k;
    ret.t = modf(t, &k);
    ret.curve_index = k;
    if (ret.curve_index == sz) {
        --ret.curve_index;
        ret.t = 1;
    }
    return ret;
}

Piecewise<D2<SBasis> > paths_to_pw(PathVector const &paths)
{
    Piecewise<D2<SBasis> > ret = paths[0].toPwSb();
    for (unsigned i = 1; i < paths.size(); i++) {
        ret.concat(paths[i].toPwSb());
    }
    return ret;
}

} // end namespace Geom

/*
  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 :