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