save work in progress

git-svn-id: http://skia.googlecode.com/svn/trunk@3141 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 71 insertions, 80 deletions

diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp
index c9bc616ede..99b9e82788 100644
--- a/experimental/Intersection/LineIntersection.cpp
+++ b/experimental/Intersection/LineIntersection.cpp
@@ -1,113 +1,104 @@
 #include "DataTypes.h"
 #include "LineIntersection.h"
-#include "LineParameters.h"
+#include <algorithm> // used for std::swap
 
 
-static bool no_intersection(_Point* result) {
-    result->x = 0;
-    result->y = 0;
-    return false;
-}
-
 /*
    Determine the intersection point of two line segments
    Return FALSE if the lines don't intersect
    from: http://paulbourke.net/geometry/lineline2d/
-   min: 8 subs, 4 muls, 4 cmps
 */
 
-bool lineIntersect(const _Line& a, const _Line& b, _Point* result) {
-    LineParameters paramsA, paramsB;
+int intersect(const _Line& a, const _Line& b, double aRange[2], double bRange[2]) {
     double axLen = a[1].x - a[0].x;
     double ayLen = a[1].y - a[0].y;
     double bxLen = b[1].x - b[0].x;
     double byLen = b[1].y - b[0].y;
+    /* Slopes match when denom goes to zero: 
+                      axLen / ayLen ==                   bxLen / byLen
+    (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
+             byLen  * axLen         ==  ayLen          * bxLen
+             byLen  * axLen         -   ayLen          * bxLen == 0 ( == denom )
+     */
     double denom  = byLen * axLen - ayLen * bxLen;
-    if (approximately_zero_squared(denom)) { // is either 'a' or 'b' a point?
-        bool aIsPoint = approximately_zero(axLen) && approximately_zero(ayLen);
-        bool bIsPoint = approximately_zero(bxLen) && approximately_zero(byLen);
-        if (aIsPoint & bIsPoint) {
-            if (!approximately_equal(a[0].x, b[0].x)
-                    || !approximately_equal(a[0].y, b[0].y)) {
-                return no_intersection(result);
-            }
-        } else {
-            double ptToLineDistance;
-            if (aIsPoint) {
-                paramsB.lineEndPoints(b);
-                ptToLineDistance = paramsB.pointDistance(a[0]);
+    if (approximately_zero_squared(denom)) {
+       /* See if the axis intercepts match:
+                  ay - ax * ayLen / axLen  ==          by - bx * ayLen / axLen
+         axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
+         axLen *  ay - ax * ayLen          == axLen *  by - bx * ayLen
+        */
+        if (approximately_equal_squared(axLen * a[0].y - ayLen * a[0].x,
+                axLen * b[0].y - ayLen * b[0].x)) {
+            const double* aPtr;
+            const double* bPtr;
+            if (fabs(axLen) > fabs(ayLen) || fabs(bxLen) > fabs(byLen)) {
+                aPtr = &a[0].x;
+                bPtr = &b[0].x;
             } else {
-                paramsA.lineEndPoints(a);
-                ptToLineDistance = paramsA.pointDistance(b[0]);
+                aPtr = &a[0].y;
+                bPtr = &b[0].y;
             }
-            if (!approximately_zero(ptToLineDistance)) {
-                return no_intersection(result);
+            double aMin = aPtr[0];
+            double aMax = aPtr[2];
+            double bMin = bPtr[0];
+            double bMax = bPtr[2];
+            if (aMin > aMax) {
+                std::swap(aMin, aMax);
             }
+            if (bMin > bMax) {
+                std::swap(bMin, bMax);
+            }
+            if (aMax < bMin || bMax < aMin) {
+                return 0;
+            }
+            if (aRange) {
+                aRange[0] = bMin <= aMin ? 0 : (bMin - aMin) / (aMax - aMin);
+                aRange[1] = bMax >= aMax ? 1 : (bMax - aMin) / (aMax - aMin);
+            }
+            if (bRange) {
+                bRange[0] = aMin <= bMin ? 0 : (aMin - bMin) / (bMax - bMin);
+                bRange[1] = aMax >= bMax ? 1 : (aMax - bMin) / (bMax - bMin);
+            }
+            return 2;
         }
-        if (aIsPoint) {
-            result->x = a[0].x;
-            result->y = a[0].y;
-        } else {
-            result->x = b[0].x;
-            result->y = b[0].y;
-        }
-        return true;
     }
     double ab0y = a[0].y - b[0].y;
     double ab0x = a[0].x - b[0].x;
     double numerA = ab0y * bxLen - byLen * ab0x;
-    double numerB;
     if (numerA < 0 && denom > numerA || numerA > 0 && denom < numerA) {
-        return no_intersection(result);
+        return 0;
     }
-    numerB = ab0y * axLen - ayLen * ab0x;
+    double numerB = ab0y * axLen - ayLen * ab0x;
     if (numerB < 0 && denom > numerB || numerB > 0 && denom < numerB) {
-        return no_intersection(result);
-    }
-    /* Are the line coincident? See if they overlap */
-    // FIXME: allow returning range of coincidence, instead of or in
-    // addition to midpoint
-    paramsA.lineEndPoints(a);
-    double b0dist = paramsA.pointDistance(b[0]);
-    bool b0on = approximately_zero_squared(b0dist);
-    double b1dist = paramsA.pointDistance(b[1]);
-    bool b1on = approximately_zero_squared(b1dist);
-    if (b0on | b1on) {
-        if (b0on & b1on) {
-            result->x = (b[0].x + b[1].x) / 2;
-            result->y = (b[0].y + b[1].y) / 2;
-            return true;
-        }
-        paramsB.lineEndPoints(b);
-        double a0dist = paramsB.pointDistance(a[0]);
-        bool a0on = approximately_zero_squared(a0dist);
-        double a1dist = paramsB.pointDistance(a[1]);
-        bool a1on = approximately_zero_squared(a1dist);
-        if (a0on | a1on) {
-            if (a0on & a1on) {
-                result->x = (a[0].x + a[1].x) / 2;
-                result->y = (a[0].y + a[1].y) / 2;
-                return true;
-            }
-            const _Point& aPt = a0on ? a[0] : a[1];
-            const _Point& bPt = b0on ? b[0] : b[1];
-            if (aPt.approximatelyEqual(bPt)) {
-                *result = aPt;
-                return true;
-            }
-            result->x = (aPt.x + bPt.x) / 2;
-            result->y = (aPt.y + bPt.y) / 2;
-            return true;
-        }
+        return 0;
     }
-
     /* Is the intersection along the the segments */
-    double mua = numerA / denom;
-    result->x = a[0].x + mua * (a[1].x - a[0].x);
-    result->y = a[0].y + mua * (a[1].y - a[0].y);
-    return true;
+    if (aRange) {
+        aRange[0] = numerA / denom;
+    }
+    if (bRange) {
+        bRange[0] = numerB / denom;
+    }
+    return 1;
 }
 
+int horizontalIntersect(const _Line& line, double y, double tRange[2]) {
+    double min = line[0].y;
+    double max = line[1].y;
+    if (min > max) {
+        std::swap(min, max);
+    }
+    if (min > y || max < y) {
+        return 0;
+    }
+    if (approximately_equal(min, max)) {
+        tRange[0] = 0;
+        tRange[1] = 1;
+        return 2;
+    }
+    tRange[0] = (y - line[0].y) / (line[1].y - line[0].y);
+    return 1;
+}
 
 // from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
 // 4 subs, 2 muls, 1 cmp