src/2geom/path.cpp

   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  */
  29
  30 #include "path.h"
  31
  32 #include "ord.h"
  33
  34 namespace Geom {
  35
  36 int CurveHelpers::root_winding(Curve const &c, Point p) {
  37     std::vector<double> ts = c.roots(p[Y], Y);
  38
  39     if(ts.empty()) return 0;
  40
  41     double const fudge = 0.01; //fudge factor used on first and last
  42
  43     std::sort(ts.begin(), ts.end());
  44
  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;
  61
  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     }
  73
  74     return wind;
  75 }
  76
  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 }
  84
  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 }
  92
  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 }
 100
 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 }
 108
 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 }
 143
 144 const double eps = .1;
 145
 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 }
 152
 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 }
 163
 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)
 170
 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   }
 180
 181   if ( curves_.front() != final_ ) {
 182     final_->setPoint(0, back().finalPoint());
 183     final_->setPoint(1, front().initialPoint());
 184   }
 185 }
 186
 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 }
 194
 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 }
 200
 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 }
 223
 224 } // end namespace Geom
 225
 226 /*
 227   Local Variables:
 228   mode:c++
 229   c-file-style:"stroustrup"
 230   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
 231   indent-tabs-mode:nil
 232   fill-column:99
 233   End:
 234 */
 235 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :