1beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com/* 2beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com * Copyright 2012 Google Inc. 3beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com * 4beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 5beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com * found in the LICENSE file. 6beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com */ 7beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com 8beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com#include "TriangleUtilities.h" 9beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com 10beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com// http://www.blackpawn.com/texts/pointinpoly/default.html 11beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.combool pointInTriangle(const Triangle& triangle, const _Point& pt) { 12beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com// Compute vectors 137ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector v0 = triangle[2] - triangle[0]; 147ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector v1 = triangle[1] - triangle[0]; 157ff5c841bf669826b4cbd708ae1a6b3527f15dcacaryclark@google.com _Vector v2 = pt - triangle[0]; 16beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com 17beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com// Compute dot products 18beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double dot00 = v0.dot(v0); 19beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double dot01 = v0.dot(v1); 20beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double dot02 = v0.dot(v2); 21beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double dot11 = v1.dot(v1); 22beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double dot12 = v1.dot(v2); 23beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com 24beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com// Compute barycentric coordinates 25beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double invDenom = 1 / (dot00 * dot11 - dot01 * dot01); 26beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double u = (dot11 * dot02 - dot01 * dot12) * invDenom; 27beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com double v = (dot00 * dot12 - dot01 * dot02) * invDenom; 28beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com 29beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com// Check if point is in triangle 30beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com return (u >= 0) && (v >= 0) && (u + v < 1); 31beda389e646d6be3cfef853584a78ca8ba39d0fccaryclark@google.com} 32