OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 #include "SkIntersections.h" | 7 #include "SkIntersections.h" |
8 #include "SkPathOpsLine.h" | 8 #include "SkPathOpsLine.h" |
9 | 9 |
10 /* Determine the intersection point of two lines. This assumes the lines are not
parallel, | 10 /* Determine the intersection point of two lines. This assumes the lines are not
parallel, |
11 and that that the lines are infinite. | 11 and that that the lines are infinite. |
12 From http://en.wikipedia.org/wiki/Line-line_intersection | 12 From http://en.wikipedia.org/wiki/Line-line_intersection |
13 */ | 13 */ |
14 SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) { | 14 SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) { |
15 double axLen = a[1].fX - a[0].fX; | 15 double axLen = a[1].fX - a[0].fX; |
16 double ayLen = a[1].fY - a[0].fY; | 16 double ayLen = a[1].fY - a[0].fY; |
17 double bxLen = b[1].fX - b[0].fX; | 17 double bxLen = b[1].fX - b[0].fX; |
18 double byLen = b[1].fY - b[0].fY; | 18 double byLen = b[1].fY - b[0].fY; |
19 double denom = byLen * axLen - ayLen * bxLen; | 19 double denom = byLen * axLen - ayLen * bxLen; |
20 SkASSERT(denom); | 20 SkASSERT(denom); |
21 double term1 = a[1].fX * a[0].fY - a[1].fY * a[0].fX; | 21 double term1 = a[1].fX * a[0].fY - a[1].fY * a[0].fX; |
22 double term2 = b[1].fX * b[0].fY - b[1].fY * b[0].fX; | 22 double term2 = b[1].fX * b[0].fY - b[1].fY * b[0].fX; |
23 SkDPoint p; | 23 SkDPoint p; |
24 p.fX = (term1 * bxLen - axLen * term2) / denom; | 24 p.fX = (term1 * bxLen - axLen * term2) / denom; |
25 p.fY = (term1 * byLen - ayLen * term2) / denom; | 25 p.fY = (term1 * byLen - ayLen * term2) / denom; |
26 return p; | 26 return p; |
27 } | 27 } |
28 | 28 |
29 int SkIntersections::computePoints(const SkDLine& line, int used) { | 29 int SkIntersections::computePoints(const SkDLine& line, int used) { |
30 fPt[0] = line.xyAtT(fT[0][0]); | 30 fPt[0] = line.ptAtT(fT[0][0]); |
31 if ((fUsed = used) == 2) { | 31 if ((fUsed = used) == 2) { |
32 fPt[1] = line.xyAtT(fT[0][1]); | 32 fPt[1] = line.ptAtT(fT[0][1]); |
33 } | 33 } |
34 return fUsed; | 34 return fUsed; |
35 } | 35 } |
36 | 36 |
37 int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { | 37 int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { |
38 double axLen = a[1].fX - a[0].fX; | 38 double axLen = a[1].fX - a[0].fX; |
39 double ayLen = a[1].fY - a[0].fY; | 39 double ayLen = a[1].fY - a[0].fY; |
40 double bxLen = b[1].fX - b[0].fX; | 40 double bxLen = b[1].fX - b[0].fX; |
41 double byLen = b[1].fY - b[0].fY; | 41 double byLen = b[1].fY - b[0].fY; |
42 /* Slopes match when denom goes to zero: | 42 /* Slopes match when denom goes to zero: |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
95 double axLen = a[1].fX - a[0].fX; | 95 double axLen = a[1].fX - a[0].fX; |
96 double ayLen = a[1].fY - a[0].fY; | 96 double ayLen = a[1].fY - a[0].fY; |
97 double bxLen = b[1].fX - b[0].fX; | 97 double bxLen = b[1].fX - b[0].fX; |
98 double byLen = b[1].fY - b[0].fY; | 98 double byLen = b[1].fY - b[0].fY; |
99 /* Slopes match when denom goes to zero: | 99 /* Slopes match when denom goes to zero: |
100 axLen / ayLen == bxLen / byLen | 100 axLen / ayLen == bxLen / byLen |
101 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen | 101 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen |
102 byLen * axLen == ayLen * bxLen | 102 byLen * axLen == ayLen * bxLen |
103 byLen * axLen - ayLen * bxLen == 0 ( == denom ) | 103 byLen * axLen - ayLen * bxLen == 0 ( == denom ) |
104 */ | 104 */ |
105 double denom = byLen * axLen - ayLen * bxLen; | 105 double axByLen = axLen * byLen; |
106 if (0 != denom) { | 106 double ayBxLen = ayLen * bxLen; |
| 107 // detect parallel lines the same way here and in SkOpAngle operator < |
| 108 // so that non-parallel means they are also sortable |
| 109 bool parallel = AlmostEqualUlps(axByLen, ayBxLen); |
| 110 if (!parallel) { |
107 double ab0y = a[0].fY - b[0].fY; | 111 double ab0y = a[0].fY - b[0].fY; |
108 double ab0x = a[0].fX - b[0].fX; | 112 double ab0x = a[0].fX - b[0].fX; |
109 double numerA = ab0y * bxLen - byLen * ab0x; | 113 double numerA = ab0y * bxLen - byLen * ab0x; |
110 double numerB = ab0y * axLen - ayLen * ab0x; | 114 double numerB = ab0y * axLen - ayLen * ab0x; |
| 115 double denom = axByLen - ayBxLen; |
111 if (between(0, numerA, denom) && between(0, numerB, denom)) { | 116 if (between(0, numerA, denom) && between(0, numerB, denom)) { |
112 fT[0][0] = numerA / denom; | 117 fT[0][0] = numerA / denom; |
113 fT[1][0] = numerB / denom; | 118 fT[1][0] = numerB / denom; |
114 return computePoints(a, 1); | 119 computePoints(a, 1); |
115 } | 120 } |
116 } | 121 } |
117 if (fAllowNear || 0 == denom) { | 122 if (fAllowNear || parallel) { |
118 for (int iA = 0; iA < 2; ++iA) { | 123 for (int iA = 0; iA < 2; ++iA) { |
119 if ((t = b.nearPoint(a[iA])) >= 0) { | 124 if ((t = b.nearPoint(a[iA])) >= 0) { |
120 insert(iA, t, a[iA]); | 125 insert(iA, t, a[iA]); |
121 } | 126 } |
122 } | 127 } |
123 for (int iB = 0; iB < 2; ++iB) { | 128 for (int iB = 0; iB < 2; ++iB) { |
124 if ((t = a.nearPoint(b[iB])) >= 0) { | 129 if ((t = a.nearPoint(b[iB])) >= 0) { |
125 insert(t, iB, b[iB]); | 130 insert(t, iB, b[iB]); |
126 } | 131 } |
127 } | 132 } |
(...skipping 173 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
301 // 4 subs, 2 muls, 1 cmp | 306 // 4 subs, 2 muls, 1 cmp |
302 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { | 307 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { |
303 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); | 308 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); |
304 } | 309 } |
305 | 310 |
306 // 16 subs, 8 muls, 6 cmps | 311 // 16 subs, 8 muls, 6 cmps |
307 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { | 312 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { |
308 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) | 313 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) |
309 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); | 314 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); |
310 } | 315 } |
OLD | NEW |