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 | 7 |
8 #include "SkPathOpsTriangle.h" | 8 #include "SkPathOpsTriangle.h" |
9 | 9 |
10 // http://www.blackpawn.com/texts/pointinpoly/default.html | 10 // http://www.blackpawn.com/texts/pointinpoly/default.html |
11 // return true if pt is inside triangle; false if outside or on the line | 11 // return true if pt is inside triangle; false if outside or on the line |
12 bool SkDTriangle::contains(const SkDPoint& pt) const { | 12 bool SkDTriangle::contains(const SkDPoint& pt) const { |
13 // Compute vectors | 13 // Compute vectors |
14 SkDVector v0 = fPts[2] - fPts[0]; | 14 SkDVector v0 = fPts[2] - fPts[0]; |
15 SkDVector v1 = fPts[1] - fPts[0]; | 15 SkDVector v1 = fPts[1] - fPts[0]; |
16 SkDVector v2 = pt - fPts[0]; | 16 SkDVector v2 = pt - fPts[0]; |
17 | 17 |
18 // Compute dot products | 18 // Compute dot products |
19 double dot00 = v0.dot(v0); | 19 double dot00 = v0.dot(v0); |
20 double dot01 = v0.dot(v1); | 20 double dot01 = v0.dot(v1); |
21 double dot02 = v0.dot(v2); | 21 double dot02 = v0.dot(v2); |
22 double dot11 = v1.dot(v1); | 22 double dot11 = v1.dot(v1); |
23 double dot12 = v1.dot(v2); | 23 double dot12 = v1.dot(v2); |
24 | 24 |
25 // original code doesn't handle degenerate input; isn't symmetric with inclusion
of corner pts; | 25 // original code doesn't handle degenerate input; isn't symmetric with inclusion
of corner pts; |
26 // introduces necessary error with divide; doesn't short circuit on early answer | 26 // introduces error with divide; doesn't short circuit on early answer |
27 #if 0 | 27 #if 0 |
28 // Compute barycentric coordinates | 28 // Compute barycentric coordinates |
29 double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); | 29 double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); |
30 double u = (dot11 * dot02 - dot01 * dot12) * invDenom; | 30 double u = (dot11 * dot02 - dot01 * dot12) * invDenom; |
31 double v = (dot00 * dot12 - dot01 * dot02) * invDenom; | 31 double v = (dot00 * dot12 - dot01 * dot02) * invDenom; |
32 | 32 |
33 // Check if point is in triangle | 33 // Check if point is in triangle |
34 return (u >= 0) && (v >= 0) && (u + v <= 1); | 34 return (u >= 0) && (v >= 0) && (u + v <= 1); |
35 #else | 35 #else |
36 double w = dot00 * dot11 - dot01 * dot01; | 36 double w = dot00 * dot11 - dot01 * dot01; |
37 if (w == 0) { | 37 if (w == 0) { |
38 return false; | 38 return false; |
39 } | 39 } |
40 double wSign = w < 0 ? -1 : 1; | 40 double wSign = w < 0 ? -1 : 1; |
41 double u = (dot11 * dot02 - dot01 * dot12) * wSign; | 41 double u = (dot11 * dot02 - dot01 * dot12) * wSign; |
42 if (u <= 0) { | 42 if (u <= 0) { |
43 return false; | 43 return false; |
44 } | 44 } |
45 double v = (dot00 * dot12 - dot01 * dot02) * wSign; | 45 double v = (dot00 * dot12 - dot01 * dot02) * wSign; |
46 if (v <= 0) { | 46 if (v <= 0) { |
47 return false; | 47 return false; |
48 } | 48 } |
49 return u + v < w * wSign; | 49 return u + v < w * wSign; |
50 #endif | 50 #endif |
51 } | 51 } |
OLD | NEW |