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