| caryclark@google.com | beda389 | 2013-02-07 13:13:41 +0000 | [diff] [blame] | 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 "TriangleUtilities.h" |
| 9 | |
| 10 | // http://www.blackpawn.com/texts/pointinpoly/default.html |
| 11 | bool pointInTriangle(const Triangle& triangle, const _Point& pt) { |
| 12 | // Compute vectors |
| 13 | _Point v0 = triangle[2] - triangle[0]; |
| 14 | _Point v1 = triangle[1] - triangle[0]; |
| 15 | _Point v2 = pt - triangle[0]; |
| 16 | |
| 17 | // Compute dot products |
| 18 | double dot00 = v0.dot(v0); |
| 19 | double dot01 = v0.dot(v1); |
| 20 | double dot02 = v0.dot(v2); |
| 21 | double dot11 = v1.dot(v1); |
| 22 | double dot12 = v1.dot(v2); |
| 23 | |
| 24 | // Compute barycentric coordinates |
| 25 | double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); |
| 26 | double u = (dot11 * dot02 - dot01 * dot12) * invDenom; |
| 27 | double v = (dot00 * dot12 - dot01 * dot02) * invDenom; |
| 28 | |
| 29 | // Check if point is in triangle |
| 30 | return (u >= 0) && (v >= 0) && (u + v < 1); |
| 31 | } |