save work in progress
git-svn-id: http://skia.googlecode.com/svn/trunk@3141 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp
index c9bc616..99b9e82 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);
+ return 0;
}
- /* 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;
- }
- }
-
/* 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