caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2012 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
| 8 | #include "SkPathOpsTriangle.h" |
| 9 | |
| 10 | // http://www.blackpawn.com/texts/pointinpoly/default.html |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 11 | // return true if pt is inside triangle; false if outside or on the line |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 12 | bool SkDTriangle::contains(const SkDPoint& pt) const { |
| 13 | // Compute vectors |
| 14 | SkDVector v0 = fPts[2] - fPts[0]; |
| 15 | SkDVector v1 = fPts[1] - fPts[0]; |
| 16 | SkDVector v2 = pt - fPts[0]; |
| 17 | |
| 18 | // Compute dot products |
| 19 | double dot00 = v0.dot(v0); |
| 20 | double dot01 = v0.dot(v1); |
| 21 | double dot02 = v0.dot(v2); |
| 22 | double dot11 = v1.dot(v1); |
| 23 | double dot12 = v1.dot(v2); |
| 24 | |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 25 | // original code doesn't handle degenerate input; isn't symmetric with inclusion of corner pts; |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 26 | // introduces error with divide; doesn't short circuit on early answer |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 27 | #if 0 |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 28 | // Compute barycentric coordinates |
| 29 | double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); |
| 30 | double u = (dot11 * dot02 - dot01 * dot12) * invDenom; |
| 31 | double v = (dot00 * dot12 - dot01 * dot02) * invDenom; |
| 32 | |
| 33 | // Check if point is in triangle |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 34 | return (u >= 0) && (v >= 0) && (u + v <= 1); |
| 35 | #else |
| 36 | double w = dot00 * dot11 - dot01 * dot01; |
| 37 | if (w == 0) { |
| 38 | return false; |
| 39 | } |
| 40 | double wSign = w < 0 ? -1 : 1; |
| 41 | double u = (dot11 * dot02 - dot01 * dot12) * wSign; |
| 42 | if (u <= 0) { |
| 43 | return false; |
| 44 | } |
| 45 | double v = (dot00 * dot12 - dot01 * dot02) * wSign; |
| 46 | if (v <= 0) { |
| 47 | return false; |
| 48 | } |
skia.committer@gmail.com | f54ad6f | 2013-11-02 07:02:02 +0000 | [diff] [blame] | 49 | return u + v < w * wSign; |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 50 | #endif |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 51 | } |