src/2geom/path.cpp

   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  */
  33
  34
  35
  36
  37 #include <2geom/path.h>
  38 #include <algorithm>
  39
  40
  41 using namespace Geom::PathInternal;
  42
  43 namespace Geom
  44 {
  45
  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 }
  58
  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 }
  71
  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 }
  79
  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 }
 102
 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 }
 200
 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 }
 213
 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         }
 250
 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         }
 284
 285     if (distance_squared != NULL)
 286         *distance_squared = mindistsq;
 287
 288         return ni + nearest;
 289 }
 290
 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 }
 326
 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   }
 341
 342   if ( get_curves().front().get() != final_ ) {
 343     final_->setPoint(0, back().finalPoint());
 344     final_->setPoint(1, front().initialPoint());
 345   }
 346 }
 347
 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 }
 360
 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 }
 388
 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 }
 411
 412 } // end namespace Geom
 413
 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:encoding=utf-8:textwidth=99 :