work in progress for shape operations
A experimental/Intersection
A experimental/Intersection/Intersections.h
A experimental/Intersection/DataTypes.cpp
A experimental/Intersection/QuadraticReduceOrder.cpp
A experimental/Intersection/IntersectionUtilities.cpp
A experimental/Intersection/CubicIntersection_Tests.h
A experimental/Intersection/LineParameteters_Test.cpp
A experimental/Intersection/ReduceOrder.cpp
A experimental/Intersection/QuadraticIntersection.cpp
A experimental/Intersection/Extrema.h
A experimental/Intersection/CubicIntersection_TestData.h
A experimental/Intersection/QuadraticParameterization_Test.cpp
A experimental/Intersection/TestUtilities.cpp
A experimental/Intersection/CubicRoots.cpp
A experimental/Intersection/QuadraticParameterization.cpp
A experimental/Intersection/QuadraticSubDivide.cpp
A experimental/Intersection/LineIntersection_Test.cpp
A experimental/Intersection/LineIntersection.cpp
A experimental/Intersection/CubicParameterizationCode.cpp
A experimental/Intersection/LineParameters.h
A experimental/Intersection/CubicIntersection.h
A experimental/Intersection/CubeRoot.cpp
A experimental/Intersection/SkAntiEdge.h
A experimental/Intersection/ConvexHull_Test.cpp
A experimental/Intersection/CubicBezierClip_Test.cpp
A experimental/Intersection/CubicIntersection_Tests.cpp
A experimental/Intersection/CubicBezierClip.cpp
A experimental/Intersection/CubicIntersectionT.cpp
A experimental/Intersection/Inline_Tests.cpp
A experimental/Intersection/ReduceOrder_Test.cpp
A experimental/Intersection/QuadraticIntersection_TestData.h
A experimental/Intersection/DataTypes.h
A experimental/Intersection/Extrema.cpp
A experimental/Intersection/EdgeApp.cpp
A experimental/Intersection/CubicIntersection_TestData.cpp
A experimental/Intersection/IntersectionUtilities.h
A experimental/Intersection/CubicReduceOrder.cpp
A experimental/Intersection/CubicCoincidence.cpp
A experimental/Intersection/CubicIntersection_Test.cpp
A experimental/Intersection/CubicIntersection.cpp
A experimental/Intersection/QuadraticUtilities.h
A experimental/Intersection/SkAntiEdge.cpp
A experimental/Intersection/TestUtilities.h
A experimental/Intersection/CubicParameterization_Test.cpp
A experimental/Intersection/LineIntersection.h
A experimental/Intersection/CubicSubDivide.cpp
A experimental/Intersection/CubicParameterization.cpp
A experimental/Intersection/QuadraticBezierClip_Test.cpp
A experimental/Intersection/QuadraticBezierClip.cpp
A experimental/Intersection/BezierClip_Test.cpp
A experimental/Intersection/ConvexHull.cpp
A experimental/Intersection/BezierClip.cpp
A experimental/Intersection/QuadraticIntersection_TestData.cpp
git-svn-id: http://skia.googlecode.com/svn/trunk@3005 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/experimental/Intersection/LineIntersection.cpp b/experimental/Intersection/LineIntersection.cpp
new file mode 100644
index 0000000..d23401e
--- /dev/null
+++ b/experimental/Intersection/LineIntersection.cpp
@@ -0,0 +1,120 @@
+#include "DataTypes.h"
+#include "LineIntersection.h"
+#include "LineParameters.h"
+
+
+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;
+ 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;
+ 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]);
+ } else {
+ paramsA.lineEndPoints(a);
+ ptToLineDistance = paramsA.pointDistance(b[0]);
+ }
+ if (!approximately_zero(ptToLineDistance)) {
+ return no_intersection(result);
+ }
+ }
+ 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);
+ }
+ 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 */
+ 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;
+}
+
+
+// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
+// 4 subs, 2 muls, 1 cmp
+static bool ccw(const _Point& A, const _Point& B, const _Point& C) {
+ return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x);
+}
+
+// 16 subs, 8 muls, 6 cmps
+bool testIntersect(const _Line& a, const _Line& b) {
+ return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1])
+ && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]);
+}