1 /*
2 * Path - Series of continuous curves
3 *
4 * Authors:
5 * MenTaLguY <mental@rydia.net>
6 * Marco Cecchetti <mrcekets at gmail.com>
7 *
8 * Copyright 2007-2008 authors
9 *
10 * This library is free software; you can redistribute it and/or
11 * modify it either under the terms of the GNU Lesser General Public
12 * License version 2.1 as published by the Free Software Foundation
13 * (the "LGPL") or, at your option, under the terms of the Mozilla
14 * Public License Version 1.1 (the "MPL"). If you do not alter this
15 * notice, a recipient may use your version of this file under either
16 * the MPL or the LGPL.
17 *
18 * You should have received a copy of the LGPL along with this library
19 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
21 * You should have received a copy of the MPL along with this library
22 * in the file COPYING-MPL-1.1
23 *
24 * The contents of this file are subject to the Mozilla Public License
25 * Version 1.1 (the "License"); you may not use this file except in
26 * compliance with the License. You may obtain a copy of the License at
27 * http://www.mozilla.org/MPL/
28 *
29 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
30 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
31 * the specific language governing rights and limitations.
32 */
37 #include <2geom/path.h>
38 #include <algorithm>
41 using namespace Geom::PathInternal;
43 namespace Geom
44 {
46 OptRect Path::boundsFast() const {
47 OptRect bounds;
48 if (empty()) return bounds;
49 bounds=front().boundsFast();
50 const_iterator iter = begin();
51 if ( iter != end() ) {
52 for ( ++iter; iter != end() ; ++iter ) {
53 bounds.unionWith(iter->boundsFast());
54 }
55 }
56 return bounds;
57 }
59 OptRect Path::boundsExact() const {
60 OptRect bounds;
61 if (empty()) return bounds;
62 bounds=front().boundsExact();
63 const_iterator iter = begin();
64 if ( iter != end() ) {
65 for ( ++iter; iter != end() ; ++iter ) {
66 bounds.unionWith(iter->boundsExact());
67 }
68 }
69 return bounds;
70 }
72 template<typename iter>
73 iter inc(iter const &x, unsigned n) {
74 iter ret = x;
75 for(unsigned i = 0; i < n; i++)
76 ret++;
77 return ret;
78 }
80 Path &Path::operator*=(Matrix const &m) {
81 unshare();
82 Sequence::iterator last = get_curves().end() - 1;
83 Sequence::iterator it;
84 Point prev;
85 for (it = get_curves().begin() ; it != last ; ++it) {
86 *it = boost::shared_ptr<Curve>((*it)->transformed(m));
87 if ( it != get_curves().begin() && (*it)->initialPoint() != prev ) {
88 THROW_CONTINUITYERROR();
89 }
90 prev = (*it)->finalPoint();
91 }
92 for ( int i = 0 ; i < 2 ; ++i ) {
93 final_->setPoint(i, (*final_)[i] * m);
94 }
95 if (get_curves().size() > 1) {
96 if ( front().initialPoint() != initialPoint() || back().finalPoint() != finalPoint() ) {
97 THROW_CONTINUITYERROR();
98 }
99 }
100 return *this;
101 }
103 std::vector<double>
104 Path::allNearestPoints(Point const& _point, double from, double to) const
105 {
106 if ( from > to ) std::swap(from, to);
107 const Path& _path = *this;
108 unsigned int sz = _path.size();
109 if ( _path.closed() ) ++sz;
110 if ( from < 0 || to > sz )
111 {
112 THROW_RANGEERROR("[from,to] interval out of bounds");
113 }
114 double sif, st = modf(from, &sif);
115 double eif, et = modf(to, &eif);
116 unsigned int si = static_cast<unsigned int>(sif);
117 unsigned int ei = static_cast<unsigned int>(eif);
118 if ( si == sz )
119 {
120 --si;
121 st = 1;
122 }
123 if ( ei == sz )
124 {
125 --ei;
126 et = 1;
127 }
128 if ( si == ei )
129 {
130 std::vector<double> all_nearest =
131 _path[si].allNearestPoints(_point, st, et);
132 for ( unsigned int i = 0; i < all_nearest.size(); ++i )
133 {
134 all_nearest[i] = si + all_nearest[i];
135 }
136 return all_nearest;
137 }
138 std::vector<double> all_t;
139 std::vector< std::vector<double> > all_np;
140 all_np.push_back( _path[si].allNearestPoints(_point, st) );
141 std::vector<unsigned int> ni;
142 ni.push_back(si);
143 double dsq;
144 double mindistsq
145 = distanceSq( _point, _path[si].pointAt( all_np.front().front() ) );
146 Rect bb(Geom::Point(0,0),Geom::Point(0,0));
147 for ( unsigned int i = si + 1; i < ei; ++i )
148 {
149 bb = *(_path[i].boundsFast());
150 dsq = distanceSq(_point, bb);
151 if ( mindistsq < dsq ) continue;
152 all_t = _path[i].allNearestPoints(_point);
153 dsq = distanceSq( _point, _path[i].pointAt( all_t.front() ) );
154 if ( mindistsq > dsq )
155 {
156 all_np.clear();
157 all_np.push_back(all_t);
158 ni.clear();
159 ni.push_back(i);
160 mindistsq = dsq;
161 }
162 else if ( mindistsq == dsq )
163 {
164 all_np.push_back(all_t);
165 ni.push_back(i);
166 }
167 }
168 bb = *(_path[ei].boundsFast());
169 dsq = distanceSq(_point, bb);
170 if ( mindistsq >= dsq )
171 {
172 all_t = _path[ei].allNearestPoints(_point, 0, et);
173 dsq = distanceSq( _point, _path[ei].pointAt( all_t.front() ) );
174 if ( mindistsq > dsq )
175 {
176 for ( unsigned int i = 0; i < all_t.size(); ++i )
177 {
178 all_t[i] = ei + all_t[i];
179 }
180 return all_t;
181 }
182 else if ( mindistsq == dsq )
183 {
184 all_np.push_back(all_t);
185 ni.push_back(ei);
186 }
187 }
188 std::vector<double> all_nearest;
189 for ( unsigned int i = 0; i < all_np.size(); ++i )
190 {
191 for ( unsigned int j = 0; j < all_np[i].size(); ++j )
192 {
193 all_nearest.push_back( ni[i] + all_np[i][j] );
194 }
195 }
196 all_nearest.erase(std::unique(all_nearest.begin(), all_nearest.end()),
197 all_nearest.end());
198 return all_nearest;
199 }
201 std::vector<double>
202 Path::nearestPointPerCurve(Point const& _point) const
203 {
204 //return a single nearest point for each curve in this path
205 std::vector<double> np;
206 for (const_iterator it = begin() ; it != end_default(); ++it)
207 //for (std::vector<Path>::const_iterator it = _path.begin(); it != _path.end(), ++it){
208 {
209 np.push_back(it->nearestPoint(_point));
210 }
211 return np;
212 }
214 double Path::nearestPoint(Point const &_point, double from, double to, double *distance_squared) const
215 {
216 if ( from > to ) std::swap(from, to);
217 const Path& _path = *this;
218 unsigned int sz = _path.size();
219 if ( _path.closed() ) ++sz;
220 if ( from < 0 || to > sz )
221 {
222 THROW_RANGEERROR("[from,to] interval out of bounds");
223 }
224 double sif, st = modf(from, &sif);
225 double eif, et = modf(to, &eif);
226 unsigned int si = static_cast<unsigned int>(sif);
227 unsigned int ei = static_cast<unsigned int>(eif);
228 if(sz == 0) {// naked moveto
229 if (distance_squared != NULL)
230 *distance_squared = distanceSq(_point, _path.initialPoint());
231 return 0;
232 }
233 if ( si == sz )
234 {
235 --si;
236 st = 1;
237 }
238 if ( ei == sz )
239 {
240 --ei;
241 et = 1;
242 }
243 if ( si == ei )
244 {
245 double nearest = _path[si].nearestPoint(_point, st, et);
246 if (distance_squared != NULL)
247 *distance_squared = distanceSq(_point, _path[si].pointAt(nearest));
248 return si + nearest;
249 }
251 double t;
252 double nearest = _path[si].nearestPoint(_point, st);
253 unsigned int ni = si;
254 double dsq;
255 double mindistsq = distanceSq(_point, _path[si].pointAt(nearest));
256 Rect bb(Geom::Point(0,0),Geom::Point(0,0));
257 for ( unsigned int i = si + 1; i < ei; ++i )
258 {
259 bb = *(_path[i].boundsFast());
260 dsq = distanceSq(_point, bb);
261 if ( mindistsq <= dsq ) continue;
262 t = _path[i].nearestPoint(_point);
263 dsq = distanceSq(_point, _path[i].pointAt(t));
264 if ( mindistsq > dsq )
265 {
266 nearest = t;
267 ni = i;
268 mindistsq = dsq;
269 }
270 }
271 bb = *(_path[ei].boundsFast());
272 dsq = distanceSq(_point, bb);
273 if ( mindistsq > dsq )
274 {
275 t = _path[ei].nearestPoint(_point, 0, et);
276 dsq = distanceSq(_point, _path[ei].pointAt(t));
277 if ( mindistsq > dsq )
278 {
279 nearest = t;
280 ni = ei;
281 mindistsq = dsq;
282 }
283 }
285 if (distance_squared != NULL)
286 *distance_squared = mindistsq;
288 return ni + nearest;
289 }
291 void Path::appendPortionTo(Path &ret, double from, double to) const {
292 if (!(from >= 0 && to >= 0)) {
293 THROW_RANGEERROR("from and to must be >=0 in Path::appendPortionTo");
294 }
295 if(to == 0) to = size()+0.999999;
296 if(from == to) { return; }
297 double fi, ti;
298 double ff = modf(from, &fi), tf = modf(to, &ti);
299 if(tf == 0) { ti--; tf = 1; }
300 const_iterator fromi = inc(begin(), (unsigned)fi);
301 if(fi == ti && from < to) {
302 Curve *v = fromi->portion(ff, tf);
303 ret.append(*v, STITCH_DISCONTINUOUS);
304 delete v;
305 return;
306 }
307 const_iterator toi = inc(begin(), (unsigned)ti);
308 if(ff != 1.) {
309 Curve *fromv = fromi->portion(ff, 1.);
310 //fromv->setInitial(ret.finalPoint());
311 ret.append(*fromv, STITCH_DISCONTINUOUS);
312 delete fromv;
313 }
314 if(from >= to) {
315 const_iterator ender = end();
316 if(ender->initialPoint() == ender->finalPoint()) ender++;
317 ret.insert(ret.end(), ++fromi, ender, STITCH_DISCONTINUOUS);
318 ret.insert(ret.end(), begin(), toi, STITCH_DISCONTINUOUS);
319 } else {
320 ret.insert(ret.end(), ++fromi, toi, STITCH_DISCONTINUOUS);
321 }
322 Curve *tov = toi->portion(0., tf);
323 ret.append(*tov, STITCH_DISCONTINUOUS);
324 delete tov;
325 }
327 void Path::do_update(Sequence::iterator first_replaced,
328 Sequence::iterator last_replaced,
329 Sequence::iterator first,
330 Sequence::iterator last)
331 {
332 // note: modifies the contents of [first,last)
333 check_continuity(first_replaced, last_replaced, first, last);
334 if ( ( last - first ) == ( last_replaced - first_replaced ) ) {
335 std::copy(first, last, first_replaced);
336 } else {
337 // this approach depends on std::vector's behavior WRT iterator stability
338 get_curves().erase(first_replaced, last_replaced);
339 get_curves().insert(first_replaced, first, last);
340 }
342 if ( get_curves().front().get() != final_ ) {
343 final_->setPoint(0, back().finalPoint());
344 final_->setPoint(1, front().initialPoint());
345 }
346 }
348 void Path::do_append(Curve *c) {
349 boost::shared_ptr<Curve> curve(c);
350 if ( get_curves().front().get() == final_ ) {
351 final_->setPoint(1, curve->initialPoint());
352 } else {
353 if (curve->initialPoint() != finalPoint()) {
354 THROW_CONTINUITYERROR();
355 }
356 }
357 get_curves().insert(get_curves().end()-1, curve);
358 final_->setPoint(0, curve->finalPoint());
359 }
361 void Path::stitch(Sequence::iterator first_replaced,
362 Sequence::iterator last_replaced,
363 Sequence &source)
364 {
365 if (!source.empty()) {
366 if ( first_replaced != get_curves().begin() ) {
367 if ( (*first_replaced)->initialPoint() != source.front()->initialPoint() ) {
368 Curve *stitch = new StitchSegment((*first_replaced)->initialPoint(),
369 source.front()->initialPoint());
370 source.insert(source.begin(), boost::shared_ptr<Curve>(stitch));
371 }
372 }
373 if ( last_replaced != (get_curves().end()-1) ) {
374 if ( (*last_replaced)->finalPoint() != source.back()->finalPoint() ) {
375 Curve *stitch = new StitchSegment(source.back()->finalPoint(),
376 (*last_replaced)->finalPoint());
377 source.insert(source.end(), boost::shared_ptr<Curve>(stitch));
378 }
379 }
380 } else if ( first_replaced != last_replaced && first_replaced != get_curves().begin() && last_replaced != get_curves().end()-1) {
381 if ( (*first_replaced)->initialPoint() != (*(last_replaced-1))->finalPoint() ) {
382 Curve *stitch = new StitchSegment((*(last_replaced-1))->finalPoint(),
383 (*first_replaced)->initialPoint());
384 source.insert(source.begin(), boost::shared_ptr<Curve>(stitch));
385 }
386 }
387 }
389 void Path::check_continuity(Sequence::iterator first_replaced,
390 Sequence::iterator last_replaced,
391 Sequence::iterator first,
392 Sequence::iterator last)
393 {
394 if ( first != last ) {
395 if ( first_replaced != get_curves().begin() ) {
396 if ( (*first_replaced)->initialPoint() != (*first)->initialPoint() ) {
397 THROW_CONTINUITYERROR();
398 }
399 }
400 if ( last_replaced != (get_curves().end()-1) ) {
401 if ( (*(last_replaced-1))->finalPoint() != (*(last-1))->finalPoint() ) {
402 THROW_CONTINUITYERROR();
403 }
404 }
405 } else if ( first_replaced != last_replaced && first_replaced != get_curves().begin() && last_replaced != get_curves().end()-1) {
406 if ( (*first_replaced)->initialPoint() != (*(last_replaced-1))->finalPoint() ) {
407 THROW_CONTINUITYERROR();
408 }
409 }
410 }
412 } // end namespace Geom
414 /*
415 Local Variables:
416 mode:c++
417 c-file-style:"stroustrup"
418 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
419 indent-tabs-mode:nil
420 fill-column:99
421 End:
422 */
423 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :