X-Git-Url: https://git.tokkee.org/?a=blobdiff_plain;f=src%2F2geom%2Fconvex-cover.cpp;h=e8ea2280d9d77ed808ef50e2e5f9a5efe8346d19;hb=698cd69991e23d81f6dccf30b2014d8cf0981d11;hp=c4d8df3385bf77d6036550d6878fd081b91e33ec;hpb=6ff97eac7dc8dade4002a37b0f6f0442d6b49bb6;p=inkscape.git

diff --git a/src/2geom/convex-cover.cpp b/src/2geom/convex-cover.cpp
index c4d8df338..e8ea2280d 100644
--- a/src/2geom/convex-cover.cpp
+++ b/src/2geom/convex-cover.cpp
@@ -179,6 +179,13 @@ int mod(int i, int l) {
  * Tests if a point is left (outside) of a particular segment, n. */
 bool
 ConvexHull::is_left(Point p, int n) {
+    return SignedTriangleArea((*this)[n], (*this)[n+1], p) >= 0;
+}
+
+/*** ConvexHull::strict_left
+ * Tests if a point is left (outside) of a particular segment, n. */
+bool
+ConvexHull::is_strict_left(Point p, int n) {
     return SignedTriangleArea((*this)[n], (*this)[n+1], p) > 0;
 }
 
@@ -193,6 +200,20 @@ ConvexHull::find_left(Point p) {
     }
     return -1;
 }
+
+
+/*** ConvexHull::find_positive
+ * May return any number n where the segment n -> n + 1 (possibly looped around) in the hull such
+ * that the point is on the wrong side to be within the hull.  Returns -1 if it is within the hull.*/
+int
+ConvexHull::find_strict_left(Point p) {
+    int l = boundary.size(); //Who knows if C++ is smart enough to optimize this?
+    for(int i = 0; i < l; i++) {
+        if(is_strict_left(p, i)) return i;
+    }
+    return -1;
+}
+
 //OPT: do a spread iteration - quasi-random with no repeats and full coverage.
 
 /*** ConvexHull::contains_point
@@ -203,6 +224,14 @@ ConvexHull::contains_point(Point p) {
     return find_left(p) == -1;
 }
 
+/*** ConvexHull::strict_contains_point
+ * In order to test whether a point is strictly inside (not on the boundary) a convex hull we can travel once around the outside making
+ * sure that each triangle made from an edge and the point has positive area. */
+bool
+ConvexHull::strict_contains_point(Point p) {
+    return find_strict_left(p) == -1;
+}
+
 /*** ConvexHull::add_point
  * to add a point we need to find whether the new point extends the boundary, and if so, what it
  * obscures.  Tarjan?  Jarvis?*/
@@ -219,9 +248,9 @@ ConvexHull::merge(Point p) {
 
     bool pushed = false;
 
-    bool pre = is_left(p, -1);
+    bool pre = is_strict_left(p, -1);
     for(int i = 0; i < l; i++) {
-        bool cur = is_left(p, i);
+        bool cur = is_strict_left(p, i);
         if(pre) {
             if(cur) {
                 if(!pushed) {