Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / skia / 639df891487e40925a4f8d9a34fd3dc0c18b40a7 / . / experimental / Intersection / LineIntersection.cpp
blob: d23401ed2df2b3a314fdb651b673f3374a13db5e [file] [log] [blame]
caryclark@google.com639df892012-01-10 21:46:10 +0000[diff] [blame^]1#include "DataTypes.h"
2#include "LineIntersection.h"
3#include "LineParameters.h"
4
5
6static bool no_intersection(_Point* result) {
7 result->x = 0;
8 result->y = 0;
9 return false;
10}
11
12/*
13 Determine the intersection point of two line segments
14 Return FALSE if the lines don't intersect
15 from: http://paulbourke.net/geometry/lineline2d/
16 min: 8 subs, 4 muls, 4 cmps
17*/
18
19bool lineIntersect(const _Line& a, const _Line& b, _Point* result) {
20 LineParameters paramsA, paramsB;
21 double axLen = a[1].x - a[0].x;
22 double ayLen = a[1].y - a[0].y;
23 double bxLen = b[1].x - b[0].x;
24 double byLen = b[1].y - b[0].y;
25 double denom = byLen * axLen - ayLen * bxLen;
26 if (approximately_zero_squared(denom)) { // is either 'a' or 'b' a point?
27 bool aIsPoint = approximately_zero(axLen) && approximately_zero(ayLen);
28 bool bIsPoint = approximately_zero(bxLen) && approximately_zero(byLen);
29 if (aIsPoint & bIsPoint) {
30 if (!approximately_equal(a[0].x, b[0].x)
31 || !approximately_equal(a[0].y, b[0].y)) {
32 return no_intersection(result);
33 }
34 } else {
35 double ptToLineDistance;
36 if (aIsPoint) {
37 paramsB.lineEndPoints(b);
38 ptToLineDistance = paramsB.pointDistance(a[0]);
39 } else {
40 paramsA.lineEndPoints(a);
41 ptToLineDistance = paramsA.pointDistance(b[0]);
42 }
43 if (!approximately_zero(ptToLineDistance)) {
44 return no_intersection(result);
45 }
46 }
47 if (aIsPoint) {
48 result->x = a[0].x;
49 result->y = a[0].y;
50 } else {
51 result->x = b[0].x;
52 result->y = b[0].y;
53 }
54 return true;
55 }
56 double ab0y = a[0].y - b[0].y;
57 double ab0x = a[0].x - b[0].x;
58 double numerA = ab0y * bxLen - byLen * ab0x;
59 double numerB;
60 if (numerA < 0 && denom > numerA || numerA > 0 && denom < numerA) {
61 return no_intersection(result);
62 }
63 numerB = ab0y * axLen - ayLen * ab0x;
64 if (numerB < 0 && denom > numerB || numerB > 0 && denom < numerB) {
65 return no_intersection(result);
66 }
67 /* Are the line coincident? See if they overlap */
68 paramsA.lineEndPoints(a);
69 double b0dist = paramsA.pointDistance(b[0]);
70 bool b0on = approximately_zero_squared(b0dist);
71 double b1dist = paramsA.pointDistance(b[1]);
72 bool b1on = approximately_zero_squared(b1dist);
73 if (b0on | b1on) {
74 if (b0on & b1on) {
75 result->x = (b[0].x + b[1].x) / 2;
76 result->y = (b[0].y + b[1].y) / 2;
77 return true;
78 }
79 paramsB.lineEndPoints(b);
80 double a0dist = paramsB.pointDistance(a[0]);
81 bool a0on = approximately_zero_squared(a0dist);
82 double a1dist = paramsB.pointDistance(a[1]);
83 bool a1on = approximately_zero_squared(a1dist);
84 if (a0on | a1on) {
85 if (a0on & a1on) {
86 result->x = (a[0].x + a[1].x) / 2;
87 result->y = (a[0].y + a[1].y) / 2;
88 return true;
89 }
90 const _Point& aPt = a0on ? a[0] : a[1];
91 const _Point& bPt = b0on ? b[0] : b[1];
92 if (aPt.approximatelyEqual(bPt)) {
93 *result = aPt;
94 return true;
95 }
96 result->x = (aPt.x + bPt.x) / 2;
97 result->y = (aPt.y + bPt.y) / 2;
98 return true;
99 }
100 }
101
102 /* Is the intersection along the the segments */
103 double mua = numerA / denom;
104 result->x = a[0].x + mua * (a[1].x - a[0].x);
105 result->y = a[0].y + mua * (a[1].y - a[0].y);
106 return true;
107}
108
109
110// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py
111// 4 subs, 2 muls, 1 cmp
112static bool ccw(const _Point& A, const _Point& B, const _Point& C) {
113 return (C.y - A.y) * (B.x - A.x) > (B.y - A.y) * (C.x - A.x);
114}
115
116// 16 subs, 8 muls, 6 cmps
117bool testIntersect(const _Line& a, const _Line& b) {
118 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1])
119 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]);
120}