← Back to branch summary

~lib2geom-hackers/lib2geom/trunk

« back to all changes in this revision

Viewing changes to path.h

  • Committer: njh
  • Date: 2006-05-22 11:50:24 UTC
  • Revision ID: svn-v4:4601daaa-0314-0410-9a8b-c964a3c23b6b:trunk/lib2geom:1
initial commit

Show diffs side-by-side

added added

removed removed

Lines of Context:
path.h
 
1
#ifndef SEEN_PATH_H
 
2
#define SEEN_PATH_H
 
3
 
 
4
#include "point.h"
 
5
#include "rect.h"
 
6
#include "maybe.h"
 
7
#include <vector>
 
8
 
 
9
/* Need some kind of efficient iterator / position reference. */
 
10
 
 
11
/** Ideas:
 
12
 * path consists of handles and commands
 
13
 * reversing the handles and commands reverses the path
 
14
 * affine transforming the handles affine transforms the path
 
15
 * paths are immutable
 
16
 * all methods are O(n) or better, and bounds are given for each method and function.
 
17
 * library is as self contained as possible
 
18
*/
 
19
 
 
20
/** To be solved:
 
21
 * How do we show elements through the iterator?
 
22
 */
 
23
 
 
24
namespace Geom{
 
25
 
 
26
enum PathOp{
 
27
    moveto,
 
28
    lineto,
 
29
    quadto,
 
30
    cubicto,
 
31
    ellipto,
 
32
    close
 
33
};
 
34
 
 
35
unsigned const PathOpHandles[] = {1, 1, 2, 3, 4, 0, 0};
 
36
int const PathOpTail[] = {0, -1, -1, -1, -1, 0, 0};
 
37
 
 
38
class Path{
 
39
public:
 
40
    std::vector<Point> handles;
 
41
    std::vector<PathOp> cmd;
 
42
 
 
43
    class PathElem{
 
44
    public:
 
45
        PathOp op;
 
46
        std::vector<Point>::const_iterator s, e;
 
47
        std::vector<Point>::const_iterator begin() const {return s;}
 
48
        std::vector<Point>::const_iterator end() const {return e;}
 
49
        Point first() { return *s;}
 
50
        Point last() { return e[-1];}
 
51
 
 
52
        PathElem() {}
 
53
        PathElem(PathOp op,
 
54
                 std::vector<Point>::const_iterator s,
 
55
                 std::vector<Point>::const_iterator e) : op(op), s(s), e(e) {
 
56
        }
 
57
        
 
58
        Point operator[](int i) {return s[i];}
 
59
        
 
60
        void point_tangent_acc_at(double t, Point &p, Point &t, Point &a);
 
61
        Point point_at(double t);
 
62
        //Point tangent_at(double t);
 
63
        bool nearest_location(Point p, double& dist, double& t);
 
64
    };
 
65
 
 
66
    class PathConstIter {
 
67
    public:
 
68
        std::vector<PathOp>::const_iterator c;
 
69
        std::vector<Point>::const_iterator h;
 
70
        
 
71
        PathConstIter() {}
 
72
        PathConstIter(std::vector<PathOp>::const_iterator c,
 
73
                 std::vector<Point>::const_iterator h) :
 
74
            c(c), h(h) {}
 
75
        void operator++() {h+=PathOpHandles[*c]; c++;}
 
76
        void operator--() {c--; h-=PathOpHandles[*c];}
 
77
        PathElem operator*() const {return PathElem(*c, h+PathOpTail[*c], h + PathOpHandles[*c]);}
 
78
 
 
79
        std::vector<Point>::const_iterator begin() const {return h;}
 
80
        std::vector<Point>::const_iterator end() const {return h + PathOpHandles[*c];}
 
81
        PathOp cmd() { return *c;}
 
82
    };
 
83
 
 
84
    typedef PathConstIter const_iterator;
 
85
 
 
86
    class PathLocation{
 
87
    public:
 
88
        PathConstIter it;
 
89
        double t; // element specific meaning [0,1)
 
90
        PathLocation(PathConstIter it, double t) : it(it), t(t) {}
 
91
    };
 
92
 
 
93
    PathConstIter begin() const { return PathConstIter(cmd.begin(), handles.begin());}
 
94
    PathConstIter end() const { return PathConstIter(cmd.end(), handles.end());}
 
95
 
 
96
    /** returns the point at the position given by walking along the path. */
 
97
    PathLocation point_at_arc_length(double s);
 
98
 
 
99
    /** return the last nearest point on the path. */
 
100
    PathLocation nearest_location(Point p, double& dist);
 
101
 
 
102
    /** return a new path over [begin, end). */
 
103
    Path subpath(PathConstIter begin, PathConstIter end);
 
104
    
 
105
    /** return a new path over [begin, end). */
 
106
    Path subpath(PathLocation begin, PathLocation end);
 
107
 
 
108
    /** compute the bounding box of this path. */
 
109
    Maybe<Rect> bbox() const;
 
110
 
 
111
    /** a new path with an extra node inserted at at without changing the curve. */
 
112
    Path insert_nodes(PathLocation* b, PathLocation* e);
 
113
    Path insert_node(PathLocation at);
 
114
 
 
115
    /** coords of point on path. */
 
116
    Point point_at(PathLocation at);
 
117
 
 
118
    void point_tangent_acc_at (PathLocation at, Point & pos, Point & tgt, Point &acc);
 
119
    
 
120
    void push_back(PathElem e);
 
121
    void insert(PathConstIter before, PathConstIter s, PathConstIter e);
 
122
    PathConstIter indexed_elem(int i) { // mainly for debugging
 
123
        PathConstIter it = begin();
 
124
        while(--i >= 0) ++it;
 
125
        return it;
 
126
    }
 
127
};
 
128
 
 
129
inline bool operator!=(const Path::PathConstIter &a, const Path::PathConstIter &b) 
 
130
{ return (a.c!=b.c) || (a.h != b.h);}
 
131
 
 
132
//Path operator * (Path, Matrix);
 
133
 
 
134
template <class T> Path operator*(Path const &p, T const &m) {
 
135
    Path pr;
 
136
    
 
137
    pr.cmd = p.cmd;
 
138
    pr.handles.reserve(p.handles.size());
 
139
    
 
140
    for(unsigned i = 0; i < p.handles.size(); i++) {
 
141
        pr.handles.push_back(p.handles[i]*m);
 
142
    }
 
143
    return pr;
 
144
}
 
145
 
 
146
template <typename Point, unsigned order>
 
147
struct BezImpl {
 
148
    static inline Point compute(double t, Point *b) {
 
149
        Point child[order];
 
150
        for ( unsigned i=0 ; i < order ; i++ ) {
 
151
            child[i] = BezImpl<Point, 1>(t, b + i);
 
152
        }
 
153
        return BezImpl<Point, order-1>::compute(t, child);
 
154
    }
 
155
};
 
156
 
 
157
template <typename Point>
 
158
struct BezImpl<Point, 1> {
 
159
    static inline Point compute(double t, Point *b) {
 
160
        return ( 1 - t ) * b[0] + t * b[1];
 
161
    }
 
162
};
 
163
 
 
164
template <typename Point>
 
165
struct BezImpl<Point, 0> {
 
166
    static inline Point compute(double t, Point *b) {
 
167
        return *b;
 
168
    }
 
169
};
 
170
 
 
171
template <unsigned order, typename Point>
 
172
 
 
173
inline Point bezier_at(double t, Point *b) {
 
174
    return BezImpl<Point, order>::compute(t, b);
 
175
}
 
176
 
 
177
}; // namespace Geom
 
178
 
 
179
#endif // SEEN_PATH_H
 
180
 
 
181
/*
 
182
  Local Variables:
 
183
  mode:c++
 
184
  c-file-style:"stroustrup"
 
185
  c-file-offsets:((innamespace . 0)(substatement-open . 0))
 
186
  indent-tabs-mode:nil
 
187
  c-brace-offset:0
 
188
  fill-column:99
 
189
  End:
 
190
  vim: filetype=c++:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 :
 
191
*/
 
192