update 2geom to rev1583

(bzr r6796)

4 files changed, 88 insertions, 41 deletions

diff --git a/src/2geom/basic-intersection.h b/src/2geom/basic-intersection.h
index d464891f9..a7750e015 100644
--- a/src/2geom/basic-intersection.h
+++ b/src/2geom/basic-intersection.h
@@ -35,14 +35,31 @@ find_self_intersections(std::vector<Point> const & A);
  *                      at which crossing happens
  *
  *  This routine is based on the Bezier Clipping Algorithm,
- *  see: Sederberg - Computer Aided Geometric Design
+ *  see: Sederberg, Nishita, 1990 - Curve intersection using Bezier clipping
  */
 void find_intersections (std::vector< std::pair<double, double> > & xs,
                          std::vector<Point> const& A,
                          std::vector<Point> const& B,
                          double precision = 1e-5);
 
-};
+/*
+ * find_collinear_normal
+ *
+ *  input: A, B       - set of control points of two Bezier curve
+ *  input: precision  - required precision of computation
+ *  output: xs        - set of pairs of parameter values
+ *                      at which there are collinear normals
+ *
+ *  This routine is based on the Bezier Clipping Algorithm,
+ *  see: Sederberg, Nishita, 1990 - Curve intersection using Bezier clipping
+ */
+void find_collinear_normal (std::vector< std::pair<double, double> >& xs,
+                            std::vector<Point> const& A,
+                            std::vector<Point> const& B,
+                            double precision = 1e-5);
+
+
+}
 
 /*
   Local Variables:
diff --git a/src/2geom/convex-cover.cpp b/src/2geom/convex-cover.cpp
index 1c2eb8757..c4d8df338 100644
--- a/src/2geom/convex-cover.cpp
+++ b/src/2geom/convex-cover.cpp
@@ -30,8 +30,10 @@
  */
 
 #include <2geom/convex-cover.h>
+#include <2geom/exception.h>
 #include <algorithm>
 #include <map>
+
 /** Todo:
     + modify graham scan to work top to bottom, rather than around angles
     + intersection
@@ -61,12 +63,16 @@ class angle_cmp{
 public:
     Point o;
     angle_cmp(Point o) : o(o) {}
-    
+
+#if 0
     bool
     operator()(Point a, Point b) {
+        // not remove this check or std::sort could crash
+        if (a == b) return false;
         Point da = a - o;
         Point db = b - o;
-        
+        if (da == -db) return false;
+
 #if 1
         double aa = da[0];
         double ab = db[0];
@@ -91,16 +97,33 @@ public:
             return L2sq(da) < L2sq(db);
         return false;
     }
+#else
+    bool operator() (Point const& a, Point const&  b)
+    {
+        // not remove this check or std::sort could generate
+        // a segmentation fault because it needs a strict '<'
+        // but due to round errors a == b doesn't mean dxy == dyx
+        if (a == b) return false;
+        Point da = a - o;
+        Point db = b - o;
+        if (da == -db) return false;
+        double dxy = da[X] * db[Y];
+        double dyx = da[Y] * db[X];
+        if (dxy > dyx) return true;
+        else if (dxy < dyx) return false;
+        return L2sq(da) < L2sq(db);
+    }
+#endif
 };
 
 void
 ConvexHull::find_pivot() {
     // Find pivot P;
     unsigned pivot = 0;
-    for(unsigned i = 1; i < boundary.size(); i++)
+    for (unsigned i = 1; i < boundary.size(); i++)
         if(boundary[i] <= boundary[pivot])
             pivot = i;
-    
+
     std::swap(boundary[0], boundary[pivot]);
 }
 
@@ -111,12 +134,14 @@ ConvexHull::angle_sort() {
     std::sort(boundary.begin()+1, boundary.end(), angle_cmp(boundary[0]));
 }
 
+
 void
 ConvexHull::graham_scan() {
+    if (boundary.size() < 4) return;
     unsigned stac = 2;
     for(unsigned int i = 2; i < boundary.size(); i++) {
-        double o = SignedTriangleArea(boundary[stac-2], 
-                                      boundary[stac-1], 
+        double o = SignedTriangleArea(boundary[stac-2],
+                                      boundary[stac-1],
                                       boundary[i]);
         if(o == 0) { // colinear - dangerous...
             stac--;
@@ -124,8 +149,8 @@ ConvexHull::graham_scan() {
         } else { // remove concavity
             while(o >= 0 && stac > 2) {
                 stac--;
-                o = SignedTriangleArea(boundary[stac-2], 
-                                       boundary[stac-1], 
+                o = SignedTriangleArea(boundary[stac-2],
+                                       boundary[stac-1],
                                        boundary[i]);
             }
         }
@@ -145,7 +170,7 @@ ConvexHull::graham() {
 
 //Mathematically incorrect mod, but more useful.
 int mod(int i, int l) {
-    return i >= 0 ? 
+    return i >= 0 ?
            i % l : (i % l) + l;
 }
 //OPT: usages can often be replaced by conditions
@@ -168,7 +193,7 @@ ConvexHull::find_left(Point p) {
     }
     return -1;
 }
-//OPT: do a spread iteration - quasi-random with no repeats and full coverage. 
+//OPT: do a spread iteration - quasi-random with no repeats and full coverage.
 
 /*** ConvexHull::contains_point
  * In order to test whether a point is inside a convex hull we can travel once around the outside making
@@ -213,7 +238,7 @@ ConvexHull::merge(Point p) {
         out.push_back(boundary[i]);
         pre = cur;
     }
-    
+
     boundary = out;
 }
 //OPT: quickly find an obscured point and find the bounds by extending from there.  then push all points not within the bounds in order.
@@ -247,12 +272,12 @@ ConvexHull::is_clockwise() const {
 bool
 ConvexHull::top_point_first() const {
     std::vector<Point>::const_iterator pivot = boundary.begin();
-    for(std::vector<Point>::const_iterator it(boundary.begin()+1), 
+    for(std::vector<Point>::const_iterator it(boundary.begin()+1),
             e(boundary.end());
         it != e; it++) {
         if((*it)[1] < (*pivot)[1])
             pivot = it;
-        else if(((*it)[1] == (*pivot)[1]) && 
+        else if(((*it)[1] == (*pivot)[1]) &&
                 ((*it)[0] < (*pivot)[0]))
             pivot = it;
     }
@@ -267,7 +292,7 @@ proposed algorithm:  We must be very careful about rounding here.
 bool
 ConvexHull::no_colinear_points() const {
     // XXX: implement me!
-    return true; // TODO return proper value
+    THROW_NOTIMPLEMENTED();
 }
 
 bool
@@ -304,7 +329,7 @@ bridges(ConvexHull a, ConvexHull b) {
             else if(e < 0 && f < 0 && g < 0 && h < 0) bbridges[ib] = ia;
         }
     }
-       
+
     return make_pair(abridges, bbridges);
 }
 
@@ -324,7 +349,7 @@ std::vector<Point> bridge_points(ConvexHull a, ConvexHull b) {
 
 unsigned find_bottom_right(ConvexHull const &a) {
     unsigned it = 1;
-    while(it < a.boundary.size() && 
+    while(it < a.boundary.size() &&
           a.boundary[it][Y] > a.boundary[it-1][Y])
         it++;
     return it-1;
@@ -338,10 +363,10 @@ unsigned find_bottom_right(ConvexHull const &a) {
  */
 ConvexHull sweepline_intersection(ConvexHull const &a, ConvexHull const &b) {
     ConvexHull ret;
-    
+
     unsigned al = 0;
     unsigned bl = 0;
-    
+
     while(al+1 < a.boundary.size() &&
           (a.boundary[al+1][Y] > b.boundary[bl][Y])) {
         al++;
@@ -398,7 +423,7 @@ ConvexHull merge(ConvexHull a, ConvexHull b) {
         if(ab[i] == 0 && i != -1) break;
         i = ab[i];
         start_b:
-        
+
         for(; bb.count(i) == 0; i++) {
             ret.boundary.push_back(b[i]);
             if(i >= (int)b.boundary.size()) return ret;
@@ -411,21 +436,21 @@ ConvexHull merge(ConvexHull a, ConvexHull b) {
 
 ConvexHull graham_merge(ConvexHull a, ConvexHull b) {
     ConvexHull result;
-    
+
     // we can avoid the find pivot step because of top_point_first
     if(b.boundary[0] <= a.boundary[0])
         std::swap(a, b);
-    
+
     result.boundary = a.boundary;
-    result.boundary.insert(result.boundary.end(), 
+    result.boundary.insert(result.boundary.end(),
                            b.boundary.begin(), b.boundary.end());
-    
+
 /** if we modified graham scan to work top to bottom as proposed in lect754.pdf we could replace the
  angle sort with a simple merge sort type algorithm. furthermore, we could do the graham scan
  online, avoiding a bunch of memory copies.  That would probably be linear. -- njh*/
     result.angle_sort();
     result.graham_scan();
-    
+
     return result;
 }
 //TODO: reinstate
diff --git a/src/2geom/convex-cover.h b/src/2geom/convex-cover.h
index ea8718c5a..29f522e91 100644
--- a/src/2geom/convex-cover.h
+++ b/src/2geom/convex-cover.h
@@ -61,11 +61,12 @@ public: // XXX: should be private :)
 public:
     std::vector<Point> boundary;
     //Point centroid;
-    
+
     void merge(Point p);
     bool contains_point(Point p);
-    
+
     inline Point operator[](int i) const {
+
         int l = boundary.size();
         if(l == 0) return Point();
         return boundary[i >= 0 ? i % l : (i % l) + l];
@@ -86,7 +87,11 @@ public:
 
     template <typename T>
     ConvexHull(T b, T e) :boundary(b,e) {}
-    
+
+    ~ConvexHull()
+    {
+    }
+
 public:
     /** Is the convex hull clockwise?  We use the definition of clockwise from point.h
     **/
@@ -94,30 +99,31 @@ public:
     bool no_colinear_points() const;
     bool top_point_first() const;
     bool meets_invariants() const;
-    
+
     // contains no points
     bool empty() const { return boundary.empty();}
-    
+
     // contains exactly one point
     bool singular() const { return boundary.size() == 1;}
 
     //  all points are on a line
     bool linear() const { return boundary.size() == 2;}
     bool is_degenerate() const;
-    
+
     // area of the convex hull
     double centroid_and_area(Geom::Point& centroid) const;
     double area() const {
         Point tmp;
         return centroid_and_area(tmp);
     }
-    
-    // furthest point in a direction (lg time) 
+
+    // furthest point in a direction (lg time)
     Point const * furthest(Point direction) const;
 
     bool is_left(Point p, int n);
     int find_left(Point p);
     double narrowest_diameter(Point &a, Point &b, Point &c);
+
 };
 
 // do two convex hulls intersect?
@@ -143,9 +149,9 @@ unsigned find_bottom_right(ConvexHull const &a);
  */
 template <class T> ConvexHull operator*(ConvexHull const &p, T const &m) {
     ConvexHull pr;
-    
+
     pr.boundary.reserve(p.boundary.size());
-    
+
     for(unsigned i = 0; i < p.boundary.size(); i++) {
         pr.boundary.push_back(p.boundary[i]*m);
     }
@@ -159,7 +165,7 @@ ConvexHull clip(ConvexHull const & ch, Point n, double d);
 public:
     Path const* path;
     std::vector<ConvexHull> cc;
-    
+
     ConvexCover(Path const &sp);
 };*/
 
diff --git a/src/2geom/rect.h b/src/2geom/rect.h
index 21cdcf849..f8ac7a2f7 100644
--- a/src/2geom/rect.h
+++ b/src/2geom/rect.h
@@ -35,9 +35,8 @@
  *   MenTaLguY <mental@rydia.net>
  */
 
-#ifdef _2GEOM_D2  /*This is intentional: we don't actually want anyone to
-                    include this, other than D2.h.  If somone else tries, D2
-                    won't be defined.  If it is, this will already be included. */
+#include <2geom/d2.h>
+
 #ifndef _2GEOM_RECT
 #define _2GEOM_RECT
 
@@ -188,7 +187,7 @@ double distance( Point const& p, Rect const& rect )
 } // end namespace Geom
 
 #endif //_2GEOM_RECT
-#endif //_2GEOM_D2
+
 /*
   Local Variables:
   mode:c++