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 11 // return true if pt is inside triangle; false if outside or on the line contains(const SkDPoint & pt) const12bool 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 25 // original code doesn't handle degenerate input; isn't symmetric with inclusion of corner pts; 26 // introduces error with divide; doesn't short circuit on early answer 27 #if 0 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 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 } 49 return u + v < w * wSign; 50 #endif 51 } 52