107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsTriangle.h" 907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// http://www.blackpawn.com/texts/pointinpoly/default.html 11a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com// return true if pt is inside triangle; false if outside or on the line 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.combool SkDTriangle::contains(const SkDPoint& pt) const { 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Compute vectors 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector v0 = fPts[2] - fPts[0]; 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector v1 = fPts[1] - fPts[0]; 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkDVector v2 = pt - fPts[0]; 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Compute dot products 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dot00 = v0.dot(v0); 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dot01 = v0.dot(v1); 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dot02 = v0.dot(v2); 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dot11 = v1.dot(v1); 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dot12 = v1.dot(v2); 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 25a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com// original code doesn't handle degenerate input; isn't symmetric with inclusion of corner pts; 26dac1d17027dcaa5596885a9f333979418b35001ccaryclark// introduces error with divide; doesn't short circuit on early answer 27a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com#if 0 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Compute barycentric coordinates 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); 3007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double u = (dot11 * dot02 - dot01 * dot12) * invDenom; 3107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double v = (dot00 * dot12 - dot01 * dot02) * invDenom; 3207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 3307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Check if point is in triangle 34a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return (u >= 0) && (v >= 0) && (u + v <= 1); 35a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com#else 36a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com double w = dot00 * dot11 - dot01 * dot01; 37a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (w == 0) { 38a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return false; 39a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 40a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com double wSign = w < 0 ? -1 : 1; 41a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com double u = (dot11 * dot02 - dot01 * dot12) * wSign; 42a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (u <= 0) { 43a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return false; 44a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 45a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com double v = (dot00 * dot12 - dot01 * dot02) * wSign; 46a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com if (v <= 0) { 47a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com return false; 48a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com } 49f54ad6f488845d0fc27734984e39185e15370fbcskia.committer@gmail.com return u + v < w * wSign; 50a2bbc6e19d5332e81784e582c290cc060f40c4c7caryclark@google.com#endif 5107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com} 52