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 void SkIntersections::cleanUpCoincidence() { | 29 int SkIntersections::cleanUpCoincidence() { |
30 SkASSERT(fUsed == 2); | 30 do { |
31 // both t values are good | 31 int last = fUsed - 1; |
32 bool startMatch = fT[0][0] == 0 && (fT[1][0] == 0 || fT[1][0] == 1); | 32 for (int index = 0; index < last; ++index) { |
33 bool endMatch = fT[0][1] == 1 && (fT[1][1] == 0 || fT[1][1] == 1); | 33 if (fT[0][index] == fT[0][index + 1]) { |
34 if (startMatch || endMatch) { | 34 removeOne(index + (int) (fT[1][index] == 0 || fT[1][index] == 1)
); |
35 removeOne(startMatch); | 35 goto tryAgain; |
36 return; | 36 } |
37 } | 37 } |
38 // either t value is good | 38 for (int index = 0; index < last; ++index) { |
39 bool pStartMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; | 39 if (fT[1][index] == fT[1][index + 1]) { |
40 bool pEndMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; | 40 removeOne(index + (int) (fT[0][index] == 0 || fT[0][index] == 1)
); |
41 removeOne(pStartMatch || !pEndMatch); | 41 goto tryAgain; |
| 42 } |
| 43 } |
| 44 return fUsed; |
| 45 tryAgain: ; |
| 46 } while (true); |
42 } | 47 } |
43 | 48 |
44 void SkIntersections::cleanUpParallelLines(bool parallel) { | 49 void SkIntersections::cleanUpParallelLines(bool parallel) { |
45 while (fUsed > 2) { | 50 while (fUsed > 2) { |
46 removeOne(1); | 51 removeOne(1); |
47 } | 52 } |
48 if (fUsed == 2 && !parallel) { | 53 if (fUsed == 2 && !parallel) { |
49 bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; | 54 bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; |
50 bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; | 55 bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; |
51 if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1]
)) { | 56 if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1]
)) { |
(...skipping 340 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
392 // 4 subs, 2 muls, 1 cmp | 397 // 4 subs, 2 muls, 1 cmp |
393 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { | 398 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { |
394 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); | 399 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); |
395 } | 400 } |
396 | 401 |
397 // 16 subs, 8 muls, 6 cmps | 402 // 16 subs, 8 muls, 6 cmps |
398 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { | 403 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { |
399 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) | 404 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) |
400 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); | 405 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); |
401 } | 406 } |
OLD | NEW |