path.h

Go to the documentation of this 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.
  */
 
#ifndef LIB2GEOM_SEEN_PATH_H
#define LIB2GEOM_SEEN_PATH_H
 
#include <cstddef>
#include <iterator>
#include <algorithm>
#include <iostream>
#include <memory>
#include <optional>
#include <utility>
#include <vector>
 
#include <boost/operators.hpp>
#include <boost/ptr_container/ptr_vector.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;
    }
    std::ptrdiff_t operator-(Self const &other) const {
        assert(path == other.path);
        return (std::ptrdiff_t)index - (std::ptrdiff_t)other.index;
    }
 
  private:
    P *path;
    unsigned index;
 
    friend class ::Geom::Path;
};
 
}
 
struct PathTime
    : boost::totally_ordered<PathTime>
{
    typedef PathInternal::Sequence::size_type size_type;
 
    Coord t; 
    size_type curve_index; 
 
    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;
    }
    void normalizeForward(size_type path_size) {
        if (t >= 1) {
            curve_index = (curve_index + 1) % path_size;
            t = 0;
        }
    }
    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;
}
 
 
class PathInterval {
public:
    typedef PathInternal::Sequence::size_type size_type;
 
    PathInterval();
 
    PathInterval(PathTime const &from, PathTime const &to, bool cross_start, size_type path_size);
 
    PathTime const &initialTime() const { return _from; }
    PathTime const &finalTime() const { return _to; }
 
    PathTime const &from() const { return _from; }
    PathTime const &to() const { return _to; }
 
    bool isDegenerate() const { return _from == _to; }
    bool reverse() const { return _reverse; }
    bool crossesStart() const { return _cross_start; }
 
    bool contains(PathTime const &pos) const;
 
    PathTime inside(Coord min_dist = EPSILON) const;
 
    static PathInterval from_direction(PathTime const &from, PathTime const &to,
                                       bool reversed, size_type path_size);
 
    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;
};
 
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;
}
 
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;
}
 
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;
};
 
struct PathExtrema {
    Point min_point, max_point;
 
    float glance_direction_at_min, glance_direction_at_max;
 
    PathTime min_time, max_time;
};
 
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) {}
        Curve *duplicate() const override { return new ClosingSegment(*this); }
        Curve *reverse() const override { return new ClosingSegment((*this)[1], (*this)[0]); }
    };
 
    class StitchSegment : public LineSegment {
      public:
        StitchSegment() : LineSegment() {}
        StitchSegment(Point const &p1, Point const &p2) : LineSegment(p1, p2) {}
        Curve *duplicate() const override { return new StitchSegment(*this); }
        Curve *reverse() const override { return new StitchSegment((*this)[1], (*this)[0]); }
    };
 
    // Path(Path const &other) - use default copy constructor
 
    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);
    }
 
    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);
    }
 
    explicit Path(Rect const &r);
    explicit Path(ConvexHull const &);
    explicit Path(Circle const &c);
    explicit Path(Ellipse const &e);
 
    virtual ~Path() {}
 
    // Path &operator=(Path const &other) - use default assignment operator
 
    void swap(Path &other) noexcept {
        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);
    }
    friend inline void swap(Path &a, Path &b) noexcept { a.swap(b); }
 
    Curve const &operator[](size_type i) const { return _data->curves[i]; }
    Curve const &at(size_type i) const { return _data->curves.at(i); }
 
    Curve const &front() const { return _data->curves.front(); }
    Curve const &initialCurve() const { return _data->curves.front(); }
    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_type size_open() const { return _data->curves.size() - 1; }
 
    size_type size_closed() const {
        return _closing_seg->isDegenerate() ? _data->curves.size() - 1 : _data->curves.size();
    }
 
    size_type size_default() const {
        return _includesClosingSegment() ? size_closed() : size_open();
    }
    size_type size() const { return size_default(); }
 
    size_type max_size() const { return _data->curves.max_size() - 1; }
 
    bool empty() const { return (_data->curves.size() == 1); }
 
    bool closed() const { return _closed; }
 
    void close(bool closed = true);
 
    void clear();
 
    OptRect boundsFast() const;
 
    OptRect boundsExact() const;
 
    Piecewise<D2<SBasis> > toPwSb() const;
 
    bool operator==(Path const &other) const;
 
    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;
    }
 
    Interval timeRange() const;
 
    Curve const &curveAt(Coord t, Coord *rest = NULL) const;
 
    LineSegment const &closingSegment() const { return *_closing_seg; }
 
    Point pointAt(Coord t) const;
 
    Coord valueAt(Coord t, Dim2 d) const;
 
    Curve const &curveAt(PathTime const &pos) const;
    Point pointAt(PathTime const &pos) const;
    Coord valueAt(PathTime const &pos, Dim2 d) const;
 
    Point operator()(Coord t) const { return pointAt(t); }
 
    PathExtrema extrema(Dim2 d) const;
 
    std::vector<PathTime> roots(Coord v, Dim2 d) const;
 
    std::vector<PathIntersection> intersect(Path const &other, Coord precision = EPSILON) const;
 
    std::vector<PathIntersection> intersectSelf(Coord precision = EPSILON) const;
 
    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;
 
    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, std::nullopt, std::nullopt);
    }
 
    void appendPortionTo(Path &p, PathInterval const &ival) const {
        appendPortionTo(p, ival, std::nullopt, std::nullopt);
    }
 
    void appendPortionTo(Path &p, PathInterval const &ival,
                         std::optional<Point> const &p_from, std::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()); }
 
    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;
    }
 
    Path portion(PathInterval const &ival) const {
        Path ret;
        ret.close(false);
        appendPortionTo(ret, ival);
        return ret;
    }
 
    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);
 
    Point initialPoint() const { return (*_closing_seg)[1]; }
 
    Point finalPoint() const { return (*_closing_seg)[_closed ? 1 : 0]; }
 
    Point initialUnitTangent() const {
        for (auto const &curve : *this) {
            if (!curve.isDegenerate()) {
                return curve.unitTangentAt(0.0);
            }
        }
        return Point();
    }
 
    Point finalUnitTangent() const {
        for (auto it = end(); it != begin();) {
            --it;
            if (!it->isDegenerate()) {
                return it->unitTangentAt(1.0);
            }
        }
        return Point();
    }
 
    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() ? size_open() - 1 : 0].setFinal(p);
        _closing_seg->setInitial(p);
    }
 
    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);
    }
 
    template <typename CurveType, typename... Args>
    void appendNew(Args&&... args) {
        _unshare();
        do_append(new CurveType(finalPoint(), std::forward<Args>(args)...));
    }
 
    void snapEnds(Coord precision = EPSILON);
 
    void stitchTo(Point const &p);
 
    Path withoutDegenerateCurves() const;
 
    void checkContinuity() const;
 
    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.use_count() != 1) {
            _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);
 
    std::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);
 
PathIntersection parting_point(Path const &first, Path const &second, 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 :