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 "path.h"
  38
  39
  40 namespace Geom
  41 {
  42
  43 void Path::swap(Path &other) {
  44   std::swap(curves_, other.curves_);
  45   std::swap(closed_, other.closed_);
  46   std::swap(*final_, *other.final_);
  47   curves_[curves_.size()-1] = final_;
  48   other.curves_[other.curves_.size()-1] = other.final_;
  49 }
  50
  51 Rect Path::boundsFast() const {
  52   Rect bounds=front().boundsFast();
  53   const_iterator iter = begin();
  54   if ( iter != end() ) {
  55           for ( ++iter; iter != end() ; ++iter ) {
  56             bounds.unionWith(iter->boundsFast());
  57           }
  58   }
  59   return bounds;
  60 }
  61
  62 Rect Path::boundsExact() const {
  63   Rect bounds=front().boundsExact();
  64   const_iterator iter = begin();
  65   if ( iter != end() ) {
  66     for ( ++iter; iter != end() ; ++iter ) {
  67       bounds.unionWith(iter->boundsExact());
  68     }
  69   }
  70   return bounds;
  71 }
  72
  73 template<typename iter>
  74 iter inc(iter const &x, unsigned n) {
  75   iter ret = x;
  76   for(unsigned i = 0; i < n; i++)
  77     ret++;
  78   return ret;
  79 }
  80
  81 std::vector<double>
  82 Path::allNearestPoints(Point const& _point, double from, double to) const
  83 {
  84         if ( from > to ) std::swap(from, to);
  85         const Path& _path = *this;
  86         unsigned int sz = _path.size();
  87         if ( _path.closed() ) ++sz;
  88         if ( from < 0 || to > sz )
  89         {
  90                 THROW_RANGEERROR("[from,to] interval out of bounds");
  91         }
  92         double sif, st = modf(from, &sif);
  93         double eif, et = modf(to, &eif);
  94         unsigned int si = static_cast<unsigned int>(sif);
  95         unsigned int ei = static_cast<unsigned int>(eif);
  96         if ( si == sz )
  97         {
  98                 --si;
  99                 st = 1;
 100         }
 101         if ( ei == sz )
 102         {
 103                 --ei;
 104                 et = 1;
 105         }
 106         if ( si == ei )
 107         {
 108                 std::vector<double>     all_nearest =
 109                         _path[si].allNearestPoints(_point, st, et);
 110                 for ( unsigned int i = 0; i < all_nearest.size(); ++i )
 111                 {
 112                         all_nearest[i] = si + all_nearest[i];
 113                 }
 114                 return all_nearest;
 115         }
 116         std::vector<double> all_t;
 117         std::vector< std::vector<double> > all_np;
 118         all_np.push_back( _path[si].allNearestPoints(_point, st) );
 119         std::vector<unsigned int> ni;
 120         ni.push_back(si);
 121         double dsq;
 122         double mindistsq
 123                 = distanceSq( _point, _path[si].pointAt( all_np.front().front() ) );
 124         Rect bb;
 125         for ( unsigned int i = si + 1; i < ei; ++i )
 126         {
 127                 bb = _path[i].boundsFast();
 128                 dsq = distanceSq(_point, bb);
 129                 if ( mindistsq < dsq ) continue;
 130                 all_t = _path[i].allNearestPoints(_point);
 131                 dsq = distanceSq( _point, _path[i].pointAt( all_t.front() ) );
 132                 if ( mindistsq > dsq )
 133                 {
 134                         all_np.clear();
 135                         all_np.push_back(all_t);
 136                         ni.clear();
 137                         ni.push_back(i);
 138                         mindistsq = dsq;
 139                 }
 140                 else if ( mindistsq == dsq )
 141                 {
 142                         all_np.push_back(all_t);
 143                         ni.push_back(i);
 144                 }
 145         }
 146         bb = _path[ei].boundsFast();
 147         dsq = distanceSq(_point, bb);
 148         if ( mindistsq >= dsq )
 149         {
 150                 all_t = _path[ei].allNearestPoints(_point, 0, et);
 151                 dsq = distanceSq( _point, _path[ei].pointAt( all_t.front() ) );
 152                 if ( mindistsq > dsq )
 153                 {
 154                         for ( unsigned int i = 0; i < all_t.size(); ++i )
 155                         {
 156                                 all_t[i] = ei + all_t[i];
 157                         }
 158                         return all_t;
 159                 }
 160                 else if ( mindistsq == dsq )
 161                 {
 162                         all_np.push_back(all_t);
 163                         ni.push_back(ei);
 164                 }
 165         }
 166         std::vector<double> all_nearest;
 167         for ( unsigned int i = 0; i < all_np.size(); ++i )
 168         {
 169                 for ( unsigned int j = 0; j < all_np[i].size(); ++j )
 170                 {
 171                         all_nearest.push_back( ni[i] + all_np[i][j] );
 172                 }
 173         }
 174         return all_nearest;
 175 }
 176
 177 double Path::nearestPoint(Point const& _point, double from, double to) const
 178 {
 179         if ( from > to ) std::swap(from, to);
 180         const Path& _path = *this;
 181         unsigned int sz = _path.size();
 182         if ( _path.closed() ) ++sz;
 183         if ( from < 0 || to > sz )
 184         {
 185                 THROW_RANGEERROR("[from,to] interval out of bounds");
 186         }
 187         double sif, st = modf(from, &sif);
 188         double eif, et = modf(to, &eif);
 189         unsigned int si = static_cast<unsigned int>(sif);
 190         unsigned int ei = static_cast<unsigned int>(eif);
 191         if ( si == sz )
 192         {
 193                 --si;
 194                 st = 1;
 195         }
 196         if ( ei == sz )
 197         {
 198                 --ei;
 199                 et = 1;
 200         }
 201         if ( si == ei )
 202         {
 203                 double nearest =
 204                         _path[si].nearestPoint(_point, st, et);
 205                 return si + nearest;
 206         }
 207         double t;
 208         double nearest = _path[si].nearestPoint(_point, st);
 209         unsigned int ni = si;
 210         double dsq;
 211         double mindistsq = distanceSq(_point, _path[si].pointAt(nearest));
 212         Rect bb;
 213         for ( unsigned int i = si + 1; i < ei; ++i )
 214         {
 215                 bb = _path[i].boundsFast();
 216                 dsq = distanceSq(_point, bb);
 217                 if ( mindistsq <= dsq ) continue;
 218                 t = _path[i].nearestPoint(_point);
 219                 dsq = distanceSq(_point, _path[i].pointAt(t));
 220                 if ( mindistsq > dsq )
 221                 {
 222                         nearest = t;
 223                         ni = i;
 224                         mindistsq = dsq;
 225                 }
 226         }
 227         bb = _path[ei].boundsFast();
 228         dsq = distanceSq(_point, bb);
 229         if ( mindistsq > dsq )
 230         {
 231                 t = _path[ei].nearestPoint(_point, 0, et);
 232                 dsq = distanceSq(_point, _path[ei].pointAt(t));
 233                 if ( mindistsq > dsq )
 234                 {
 235                         nearest = t;
 236                         ni = ei;
 237                 }
 238         }
 239         return ni + nearest;
 240 }
 241
 242 Rect Path::boundsFast()
 243 {
 244     Rect bound;
 245     if (empty()) return bound;
 246
 247     bound = begin()->boundsFast();
 248     for (iterator it = ++begin(); it != end(); ++it)
 249     {
 250         bound.unionWith(it->boundsFast());
 251     }
 252     return bound;
 253 }
 254
 255 Rect Path::boundsExact()
 256 {
 257     Rect bound;
 258     if (empty()) return bound;
 259
 260     bound = begin()->boundsExact();
 261     for (iterator it = ++begin(); it != end(); ++it)
 262     {
 263         bound.unionWith(it->boundsExact());
 264     }
 265     return bound;
 266 }
 267
 268 //This assumes that you can't be perfect in your t-vals, and as such, tweaks the start
 269 void Path::appendPortionTo(Path &ret, double from, double to) const {
 270   assert(from >= 0 && to >= 0);
 271   if(to == 0) to = size()+0.999999;
 272   if(from == to) { return; }
 273   double fi, ti;
 274   double ff = modf(from, &fi), tf = modf(to, &ti);
 275   if(tf == 0) { ti--; tf = 1; }
 276   const_iterator fromi = inc(begin(), (unsigned)fi);
 277   if(fi == ti && from < to) {
 278     Curve *v = fromi->portion(ff, tf);
 279     ret.append(*v);
 280     delete v;
 281     return;
 282   }
 283   const_iterator toi = inc(begin(), (unsigned)ti);
 284   if(ff != 1.) {
 285     Curve *fromv = fromi->portion(ff, 1.);
 286     //fromv->setInitial(ret.finalPoint());
 287     ret.append(*fromv);
 288     delete fromv;
 289   }
 290   if(from >= to) {
 291     const_iterator ender = end();
 292     if(ender->initialPoint() == ender->finalPoint()) ender++;
 293     ret.insert(ret.end(), ++fromi, ender);
 294     ret.insert(ret.end(), begin(), toi);
 295   } else {
 296     ret.insert(ret.end(), ++fromi, toi);
 297   }
 298   Curve *tov = toi->portion(0., tf);
 299   ret.append(*tov);
 300   delete tov;
 301 }
 302
 303 const double eps = .1;
 304
 305 void Path::append(Curve const &curve) {
 306   if ( curves_.front() != final_ && !are_near(curve.initialPoint(), (*final_)[0], eps) ) {
 307     THROW_CONTINUITYERROR();
 308   }
 309   do_append(curve.duplicate());
 310 }
 311
 312 void Path::append(D2<SBasis> const &curve) {
 313   if ( curves_.front() != final_ ) {
 314     for ( int i = 0 ; i < 2 ; ++i ) {
 315       if ( !are_near(curve[i][0][0], (*final_)[0][i], eps) ) {
 316         THROW_CONTINUITYERROR();
 317       }
 318     }
 319   }
 320   do_append(new SBasisCurve(curve));
 321 }
 322
 323 void Path::append(Path const &other)
 324 {
 325     // Check that path stays continuous:
 326     if ( !are_near( finalPoint(), other.initialPoint() ) ) {
 327         THROW_CONTINUITYERROR();
 328     }
 329
 330     insert(begin(), other.begin(), other.end());
 331 }
 332
 333 void Path::do_update(Sequence::iterator first_replaced,
 334                      Sequence::iterator last_replaced,
 335                      Sequence::iterator first,
 336                     Sequence::iterator last)
 337 {
 338   // note: modifies the contents of [first,last)
 339
 340   check_continuity(first_replaced, last_replaced, first, last);
 341   delete_range(first_replaced, last_replaced);
 342   if ( ( last - first ) == ( last_replaced - first_replaced ) ) {
 343     std::copy(first, last, first_replaced);
 344   } else {
 345     // this approach depends on std::vector's behavior WRT iterator stability
 346     curves_.erase(first_replaced, last_replaced);
 347     curves_.insert(first_replaced, first, last);
 348   }
 349
 350   if ( curves_.front() != final_ ) {
 351     final_->setPoint(0, back().finalPoint());
 352     final_->setPoint(1, front().initialPoint());
 353   }
 354 }
 355
 356 void Path::do_append(Curve *curve) {
 357   if ( curves_.front() == final_ ) {
 358     final_->setPoint(1, curve->initialPoint());
 359   }
 360   curves_.insert(curves_.end()-1, curve);
 361   final_->setPoint(0, curve->finalPoint());
 362 }
 363
 364 void Path::delete_range(Sequence::iterator first, Sequence::iterator last) {
 365   for ( Sequence::iterator iter=first ; iter != last ; ++iter ) {
 366     delete *iter;
 367   }
 368 }
 369
 370 void Path::check_continuity(Sequence::iterator first_replaced,
 371                             Sequence::iterator last_replaced,
 372                             Sequence::iterator first,
 373                             Sequence::iterator last)
 374 {
 375   if ( first != last ) {
 376     if ( first_replaced != curves_.begin() ) {
 377       if ( !are_near( (*first_replaced)->initialPoint(), (*first)->initialPoint(), eps ) ) {
 378         THROW_CONTINUITYERROR();
 379       }
 380     }
 381     if ( last_replaced != (curves_.end()-1) ) {
 382       if ( !are_near( (*(last_replaced-1))->finalPoint(), (*(last-1))->finalPoint(), eps ) ) {
 383         THROW_CONTINUITYERROR();
 384       }
 385     }
 386   } else if ( first_replaced != last_replaced && first_replaced != curves_.begin() && last_replaced != curves_.end()-1) {
 387     if ( !are_near((*first_replaced)->initialPoint(), (*(last_replaced-1))->finalPoint(), eps ) ) {
 388       THROW_CONTINUITYERROR();
 389     }
 390   }
 391 }
 392
 393 } // end namespace Geom
 394
 395 /*
 396   Local Variables:
 397   mode:c++
 398   c-file-style:"stroustrup"
 399   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 400   indent-tabs-mode:nil
 401   fill-column:99
 402   End:
 403 */
 404 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :