src/2geom/curve-helpers.cpp

   1 /*
   2  *
   3  * Authors:
   4  *              MenTaLguY <mental@rydia.net>
   5  *              Marco Cecchetti <mrcekets at gmail.com>
   6  *
   7  * Copyright 2007-2008  authors
   8  *
   9  * This library is free software; you can redistribute it and/or
  10  * modify it either under the terms of the GNU Lesser General Public
  11  * License version 2.1 as published by the Free Software Foundation
  12  * (the "LGPL") or, at your option, under the terms of the Mozilla
  13  * Public License Version 1.1 (the "MPL"). If you do not alter this
  14  * notice, a recipient may use your version of this file under either
  15  * the MPL or the LGPL.
  16  *
  17  * You should have received a copy of the LGPL along with this library
  18  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  * You should have received a copy of the MPL along with this library
  21  * in the file COPYING-MPL-1.1
  22  *
  23  * The contents of this file are subject to the Mozilla Public License
  24  * Version 1.1 (the "License"); you may not use this file except in
  25  * compliance with the License. You may obtain a copy of the License at
  26  * http://www.mozilla.org/MPL/
  27  *
  28  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  29  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  30  * the specific language governing rights and limitations.
  31  */
  32
  33
  34 #include <2geom/curve.h>
  35 #include <2geom/ord.h>
  36
  37
  38 namespace Geom
  39 {
  40
  41 int CurveHelpers::root_winding(Curve const &c, Point p) {
  42     std::vector<double> ts = c.roots(p[Y], Y);
  43
  44     if(ts.empty()) return 0;
  45
  46     double const fudge = 0.01; //fudge factor used on first and last
  47
  48     std::sort(ts.begin(), ts.end());
  49
  50     // winding determined by crossings at roots
  51     int wind=0;
  52     // previous time
  53     double pt = ts.front() - fudge;
  54     for ( std::vector<double>::iterator ti = ts.begin()
  55         ; ti != ts.end()
  56         ; ++ti )
  57     {
  58         double t = *ti;
  59         if ( t <= 0. || t >= 1. ) continue; //skip endpoint roots
  60         if ( c.valueAt(t, X) > p[X] ) { // root is ray intersection
  61             // Get t of next:
  62             std::vector<double>::iterator next = ti;
  63             next++;
  64             double nt;
  65             if(next == ts.end()) nt = t + fudge; else nt = *next;
  66
  67             // Check before in time and after in time for positions
  68             // Currently we're using the average times between next and previous segs
  69             Cmp after_to_ray =  cmp(c.valueAt((t + nt) / 2, Y), p[Y]);
  70             Cmp before_to_ray = cmp(c.valueAt((t + pt) / 2, Y), p[Y]);
  71             // if y is included, these will have opposite values, giving order.
  72             Cmp dt = cmp(after_to_ray, before_to_ray);
  73             if(dt != EQUAL_TO) //Should always be true, but yah never know..
  74                 wind += dt;
  75             pt = t;
  76         }
  77     }
  78
  79     return wind;
  80 }
  81
  82
  83 }  // end namespace Geom
  84
  85 /*
  86   Local Variables:
  87   mode:c++
  88   c-file-style:"stroustrup"
  89   c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  90   indent-tabs-mode:nil
  91   fill-column:99
  92   End:
  93 */
  94 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :