2geom update (rev. 1578); fixes node editing of some degenerate paths

[inkscape.git] / src / 2geom / convex-cover.cpp

diff --git a/src/2geom/convex-cover.cpp b/src/2geom/convex-cover.cpp
index 2d11b74190226f6d6361cc0fae4e450267eb0418..5b6d36c493776fbbec4e4231dd592a29c45433e8 100644 (file)
--- a/src/2geom/convex-cover.cpp
+++ b/src/2geom/convex-cover.cpp
@@ -29,7 +29,7 @@
  *
  */
 
-#include "convex-cover.h"
+#include <2geom/convex-cover.h>
 #include <algorithm>
 #include <map>
 /** Todo:
@@ -114,7 +114,7 @@ ConvexHull::angle_sort() {
 void
 ConvexHull::graham_scan() {
     unsigned stac = 2;
-    for(int i = 2; i < boundary.size(); i++) {
+    for(unsigned int i = 2; i < boundary.size(); i++) {
         double o = SignedTriangleArea(boundary[stac-2], 
                                       boundary[stac-1], 
                                       boundary[i]);
@@ -136,6 +136,8 @@ ConvexHull::graham_scan() {
 
 void
 ConvexHull::graham() {
+    if(is_degenerate()) // nothing to do
+        return;
     find_pivot();
     angle_sort();
     graham_scan();
@@ -264,7 +266,7 @@ proposed algorithm:  We must be very careful about rounding here.
 */
 bool
 ConvexHull::no_colinear_points() const {
-
+    // XXX: implement me!
 }
 
 bool
@@ -292,8 +294,8 @@ bridges(ConvexHull a, ConvexHull b) {
     map<int, int> abridges;
     map<int, int> bbridges;
 
-    for(int ia = 0; ia < a.boundary.size(); ia++) {
-        for(int ib = 0; ib < b.boundary.size(); ib++) {
+    for(unsigned ia = 0; ia < a.boundary.size(); ia++) {
+        for(unsigned ib = 0; ib < b.boundary.size(); ib++) {
             Point d = b[ib] - a[ia];
             Geom::Coord e = cross(d, a[ia - 1] - a[ia]), f = cross(d, a[ia + 1] - a[ia]);
             Geom::Coord g = cross(d, b[ib - 1] - a[ia]), h = cross(d, b[ib + 1] - a[ia]);
@@ -336,8 +338,8 @@ unsigned find_bottom_right(ConvexHull const &a) {
 ConvexHull sweepline_intersection(ConvexHull const &a, ConvexHull const &b) {
     ConvexHull ret;
     
-    int al = 0;
-    int bl = 0;
+    unsigned al = 0;
+    unsigned bl = 0;
     
     while(al+1 < a.boundary.size() &&
           (a.boundary[al+1][Y] > b.boundary[bl][Y])) {
@@ -348,8 +350,9 @@ ConvexHull sweepline_intersection(ConvexHull const &a, ConvexHull const &b) {
         bl++;
     }
     // al and bl now point to the top of the first pair of edges that overlap in y value
-    double sweep_y = std::min(a.boundary[al][Y],
-                              b.boundary[bl][Y]);
+    //double sweep_y = std::min(a.boundary[al][Y],
+    //                          b.boundary[bl][Y]);
+    return ret;
 }
 
 /*** ConvexHull intersection(ConvexHull a, ConvexHull b);
@@ -357,12 +360,13 @@ ConvexHull sweepline_intersection(ConvexHull const &a, ConvexHull const &b) {
  * (Proof: take any two points both in a and in b.  Any point between them is in a by convexity,
  * and in b by convexity, thus in both.  Need to prove still finite bounds.)
  */
-ConvexHull intersection(ConvexHull a, ConvexHull b) {
+ConvexHull intersection(ConvexHull /*a*/, ConvexHull /*b*/) {
     ConvexHull ret;
+    /*
     int ai = 0, bi = 0;
     int aj = a.boundary.size() - 1;
     int bj = b.boundary.size() - 1;
-    
+    */
     /*while (true) {
         if(a[ai]
     }*/
@@ -382,13 +386,13 @@ ConvexHull merge(ConvexHull a, ConvexHull b) {
     ab[-1] = 0;
     bb[-1] = 0;
 
-    int i = -1;
+    int i = -1; // XXX: i is int but refers to vector indices
 
     if(a.boundary[0][1] > b.boundary[0][1]) goto start_b;
     while(true) {
         for(; ab.count(i) == 0; i++) {
             ret.boundary.push_back(a[i]);
-            if(i >= a.boundary.size()) return ret;
+            if(i >= (int)a.boundary.size()) return ret;
         }
         if(ab[i] == 0 && i != -1) break;
         i = ab[i];
@@ -396,7 +400,7 @@ ConvexHull merge(ConvexHull a, ConvexHull b) {
         
         for(; bb.count(i) == 0; i++) {
             ret.boundary.push_back(b[i]);
-            if(i >= b.boundary.size()) return ret;
+            if(i >= (int)b.boundary.size()) return ret;
         }
         if(bb[i] == 0 && i != -1) break;
         i = bb[i];
@@ -431,6 +435,66 @@ ConvexHull graham_merge(ConvexHull a, ConvexHull b) {
     }
 }*/
 
+double ConvexHull::centroid_and_area(Geom::Point& centroid) const {
+    const unsigned n = boundary.size();
+    if (n < 2)
+        return 0;
+    if(n < 3) {
+        centroid = (boundary[0] + boundary[1])/2;
+        return 0;
+    }
+    Geom::Point centroid_tmp(0,0);
+    double atmp = 0;
+    for (unsigned i = n-1, j = 0; j < n; i = j, j++) {
+        const double ai = -cross(boundary[j], boundary[i]);
+        atmp += ai;
+        centroid_tmp += (boundary[j] + boundary[i])*ai; // first moment.
+    }
+    if (atmp != 0) {
+        centroid = centroid_tmp / (3 * atmp);
+    }
+    return atmp / 2;
+}
+
+// TODO: This can be made lg(n) using golden section/fibonacci search three starting points, say 0,
+// n/2, n-1 construct a new point, say (n/2 + n)/2 throw away the furthest boundary point iterate
+// until interval is a single value
+Point const * ConvexHull::furthest(Point direction) const {
+    Point const * p = &boundary[0];
+    double d = dot(*p, direction);
+    for(unsigned i = 1; i < boundary.size(); i++) {
+        double dd = dot(boundary[i], direction);
+        if(d < dd) {
+            p = &boundary[i];
+            d = dd;
+        }
+    }
+    return p;
+}
+
+
+// returns (a, (b,c)), three points which define the narrowest diameter of the hull as the pair of
+// lines going through b,c, and through a, parallel to b,c TODO: This can be made linear time by
+// moving point tc incrementally from the previous value (it can only move in one direction).  It
+// is currently n*O(furthest)
+double ConvexHull::narrowest_diameter(Point &a, Point &b, Point &c) {
+    Point tb = boundary.back();
+    double d = INFINITY;
+    for(unsigned i = 0; i < boundary.size(); i++) {
+        Point tc = boundary[i];
+        Point n = -rot90(tb-tc);
+        Point ta = *furthest(n);
+        double td = dot(n, ta-tb)/dot(n,n);
+        if(td < d) {
+            a = ta;
+            b = tb;
+            c = tc;
+            d = td;
+        }
+        tb = tc;
+    }
+    return d;
+}
 
 };