michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "SkPathOpsTriangle.h"
michael@0: 
michael@0: // http://www.blackpawn.com/texts/pointinpoly/default.html
michael@0: // return true if pt is inside triangle; false if outside or on the line
michael@0: bool SkDTriangle::contains(const SkDPoint& pt) const {
michael@0: // Compute vectors
michael@0:     SkDVector v0 = fPts[2] - fPts[0];
michael@0:     SkDVector v1 = fPts[1] - fPts[0];
michael@0:     SkDVector v2 = pt - fPts[0];
michael@0: 
michael@0: // Compute dot products
michael@0:     double dot00 = v0.dot(v0);
michael@0:     double dot01 = v0.dot(v1);
michael@0:     double dot02 = v0.dot(v2);
michael@0:     double dot11 = v1.dot(v1);
michael@0:     double dot12 = v1.dot(v2);
michael@0: 
michael@0: // original code doesn't handle degenerate input; isn't symmetric with inclusion of corner pts;
michael@0: // introduces necessary error with divide; doesn't short circuit on early answer
michael@0: #if 0
michael@0: // Compute barycentric coordinates
michael@0:     double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
michael@0:     double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
michael@0:     double v = (dot00 * dot12 - dot01 * dot02) * invDenom;
michael@0: 
michael@0: // Check if point is in triangle
michael@0:     return (u >= 0) && (v >= 0) && (u + v <= 1);
michael@0: #else
michael@0:     double w = dot00 * dot11 - dot01 * dot01;
michael@0:     if (w == 0) {
michael@0:         return false;
michael@0:     }
michael@0:     double wSign = w < 0 ? -1 : 1;
michael@0:     double u = (dot11 * dot02 - dot01 * dot12) * wSign;
michael@0:     if (u <= 0) {
michael@0:         return false;
michael@0:     }
michael@0:     double v = (dot00 * dot12 - dot01 * dot02) * wSign;
michael@0:     if (v <= 0) {
michael@0:         return false;
michael@0:     }
michael@0:     return u + v < w * wSign;
michael@0: #endif
michael@0: }