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
12bool 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