1 /*
2 * Path - Series of continuous curves
3 *
4 * Copyright 2007 MenTaLguY <mental@rydia.net>
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it either under the terms of the GNU Lesser General Public
8 * License version 2.1 as published by the Free Software Foundation
9 * (the "LGPL") or, at your option, under the terms of the Mozilla
10 * Public License Version 1.1 (the "MPL"). If you do not alter this
11 * notice, a recipient may use your version of this file under either
12 * the MPL or the LGPL.
13 *
14 * You should have received a copy of the LGPL along with this library
15 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 * You should have received a copy of the MPL along with this library
18 * in the file COPYING-MPL-1.1
19 *
20 * The contents of this file are subject to the Mozilla Public License
21 * Version 1.1 (the "License"); you may not use this file except in
22 * compliance with the License. You may obtain a copy of the License at
23 * http://www.mozilla.org/MPL/
24 *
25 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27 * the specific language governing rights and limitations.
28 */
30 #include "path.h"
32 #include "ord.h"
34 namespace Geom {
36 int CurveHelpers::root_winding(Curve const &c, Point p) {
37 std::vector<double> ts = c.roots(p[Y], Y);
39 if(ts.empty()) return 0;
41 double const fudge = 0.01; //fudge factor used on first and last
43 std::sort(ts.begin(), ts.end());
45 // winding determined by crossings at roots
46 int wind=0;
47 // previous time
48 double pt = ts.front() - fudge;
49 for ( std::vector<double>::iterator ti = ts.begin()
50 ; ti != ts.end()
51 ; ++ti )
52 {
53 double t = *ti;
54 if ( t <= 0. || t >= 1. ) continue; //skip endpoint roots
55 if ( c.valueAt(t, X) > p[X] ) { // root is ray intersection
56 // Get t of next:
57 std::vector<double>::iterator next = ti;
58 next++;
59 double nt;
60 if(next == ts.end()) nt = t + fudge; else nt = *next;
62 // Check before in time and after in time for positions
63 // Currently we're using the average times between next and previous segs
64 Cmp after_to_ray = cmp(c.valueAt((t + nt) / 2, Y), p[Y]);
65 Cmp before_to_ray = cmp(c.valueAt((t + pt) / 2, Y), p[Y]);
66 // if y is included, these will have opposite values, giving order.
67 Cmp dt = cmp(after_to_ray, before_to_ray);
68 if(dt != EQUAL_TO) //Should always be true, but yah never know..
69 wind += dt;
70 pt = t;
71 }
72 }
74 return wind;
75 }
77 void Path::swap(Path &other) {
78 std::swap(curves_, other.curves_);
79 std::swap(closed_, other.closed_);
80 std::swap(*final_, *other.final_);
81 curves_[curves_.size()-1] = final_;
82 other.curves_[other.curves_.size()-1] = other.final_;
83 }
85 Rect Path::boundsFast() const {
86 Rect bounds=front().boundsFast();
87 for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {
88 bounds.unionWith(iter->boundsFast());
89 }
90 return bounds;
91 }
93 Rect Path::boundsExact() const {
94 Rect bounds=front().boundsExact();
95 for ( const_iterator iter=++begin(); iter != end() ; ++iter ) {
96 bounds.unionWith(iter->boundsExact());
97 }
98 return bounds;
99 }
101 template<typename iter>
102 iter inc(iter const &x, unsigned n) {
103 iter ret = x;
104 for(unsigned i = 0; i < n; i++)
105 ret++;
106 return ret;
107 }
109 //This assumes that you can't be perfect in your t-vals, and as such, tweaks the start
110 void Path::appendPortionTo(Path &ret, double from, double to) const {
111 assert(from >= 0 && to >= 0);
112 if(to == 0) to = size()+0.999999;
113 if(from == to) { return; }
114 double fi, ti;
115 double ff = modf(from, &fi), tf = modf(to, &ti);
116 if(tf == 0) { ti--; tf = 1; }
117 const_iterator fromi = inc(begin(), (unsigned)fi);
118 if(fi == ti && from < to) {
119 Curve *v = fromi->portion(ff, tf);
120 ret.append(*v);
121 delete v;
122 return;
123 }
124 const_iterator toi = inc(begin(), (unsigned)ti);
125 if(ff != 1.) {
126 Curve *fromv = fromi->portion(ff, 1.);
127 //fromv->setInitial(ret.finalPoint());
128 ret.append(*fromv);
129 delete fromv;
130 }
131 if(from >= to) {
132 const_iterator ender = end();
133 if(ender->initialPoint() == ender->finalPoint()) ender++;
134 ret.insert(ret.end(), ++fromi, ender);
135 ret.insert(ret.end(), begin(), toi);
136 } else {
137 ret.insert(ret.end(), ++fromi, toi);
138 }
139 Curve *tov = toi->portion(0., tf);
140 ret.append(*tov);
141 delete tov;
142 }
144 const double eps = .1;
146 void Path::append(Curve const &curve) {
147 if ( curves_.front() != final_ && !are_near(curve.initialPoint(), (*final_)[0], eps) ) {
148 throwContinuityError();
149 }
150 do_append(curve.duplicate());
151 }
153 void Path::append(D2<SBasis> const &curve) {
154 if ( curves_.front() != final_ ) {
155 for ( int i = 0 ; i < 2 ; ++i ) {
156 if ( !are_near(curve[i][0][0], (*final_)[0][i], eps) ) {
157 throwContinuityError();
158 }
159 }
160 }
161 do_append(new SBasisCurve(curve));
162 }
164 void Path::do_update(Sequence::iterator first_replaced,
165 Sequence::iterator last_replaced,
166 Sequence::iterator first,
167 Sequence::iterator last)
168 {
169 // note: modifies the contents of [first,last)
171 check_continuity(first_replaced, last_replaced, first, last);
172 delete_range(first_replaced, last_replaced);
173 if ( ( last - first ) == ( last_replaced - first_replaced ) ) {
174 std::copy(first, last, first_replaced);
175 } else {
176 // this approach depends on std::vector's behavior WRT iterator stability
177 curves_.erase(first_replaced, last_replaced);
178 curves_.insert(first_replaced, first, last);
179 }
181 if ( curves_.front() != final_ ) {
182 final_->setPoint(0, back().finalPoint());
183 final_->setPoint(1, front().initialPoint());
184 }
185 }
187 void Path::do_append(Curve *curve) {
188 if ( curves_.front() == final_ ) {
189 final_->setPoint(1, curve->initialPoint());
190 }
191 curves_.insert(curves_.end()-1, curve);
192 final_->setPoint(0, curve->finalPoint());
193 }
195 void Path::delete_range(Sequence::iterator first, Sequence::iterator last) {
196 for ( Sequence::iterator iter=first ; iter != last ; ++iter ) {
197 delete *iter;
198 }
199 }
201 void Path::check_continuity(Sequence::iterator first_replaced,
202 Sequence::iterator last_replaced,
203 Sequence::iterator first,
204 Sequence::iterator last)
205 {
206 if ( first != last ) {
207 if ( first_replaced != curves_.begin() ) {
208 if ( !are_near( (*first_replaced)->initialPoint(), (*first)->initialPoint(), eps ) ) {
209 throwContinuityError();
210 }
211 }
212 if ( last_replaced != (curves_.end()-1) ) {
213 if ( !are_near( (*(last_replaced-1))->finalPoint(), (*(last-1))->finalPoint(), eps ) ) {
214 throwContinuityError();
215 }
216 }
217 } else if ( first_replaced != last_replaced && first_replaced != curves_.begin() && last_replaced != curves_.end()-1) {
218 if ( !are_near((*first_replaced)->initialPoint(), (*(last_replaced-1))->finalPoint(), eps ) ) {
219 throwContinuityError();
220 }
221 }
222 }
224 } // end namespace Geom
226 /*
227 Local Variables:
228 mode:c++
229 c-file-style:"stroustrup"
230 c-file-offsets:((innamespace . 0)(substatement-open . 0))
231 indent-tabs-mode:nil
232 c-brace-offset:0
233 fill-column:99
234 End:
235 vim: filetype=cpp:expandtab:shiftwidth=2:tabstop=8:softtabstop=2 :
236 */