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
11bool pointInTriangle(const Triangle& triangle, const _Point& pt) {
12// Compute vectors
13    _Vector v0 = triangle[2] - triangle[0];
14    _Vector v1 = triangle[1] - triangle[0];
15    _Vector 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}
32