Got a tip for us? Let us know
Jul 21, 2006, 08:47 PM  #1 
question for the geometry folks
Is there a formula, procedure, or function, that given the location of the three vertices of a triangle, you can tell if a given point is within the area of that triangle?
Thank you, and sorry if I'm missing something obvious. 

0 
Jul 22, 2006, 01:00 AM  #2 
Here's a way. It's based on the idea of a point being to the left or right of a line (or directly on it). If you think of a line formed from two points starting at one point and traveling toward the second point, then another point could be:
1. To the left of the line. 2. To the right of the line. 3. Directly on the line. For a triangle, there are three lines formed. If you think about going around the triangle, from point to point in one direction, a point is inside the triangle if it is either to the right of all three lines, or to the left of all three lines. And it turns out to be easy to compute if a point is to the left, right, or on a line formed by two points: Given the line formed by points (v0.x, v0.y) and (v1.x, v1.y), and the point (p.x, p.y) you compute this value: d = (v1.xv0.x) * (p.yv0.y)  (v1.yv0.y) * (p.xv0.x) if d is greater than zero, p is to the right of the line. If d is less than zero, p is to the left of the line. And if d is zero, then the point is on the line. So you can do the computation for all three sides of the triangle formed by v0, v1, and v2: d0 = (v1.xv0.x) * (p.yv0.y)  (v1.yv0.y) * (p.xv0.x) d1 = (v2.xv1.x) * (p.yv1.y)  (v2.yv1.y) * (p.xv1.x) d2 = (v0.xv2.x) * (p.yv2.y)  (v0.yv2.y) * (p.xv2.x) now, if (d0 < 0 and d1 < 0 and d2 < 0) or (d0 > 0 and d1 > 0 and d2 > 0) then the point is in the triange. If you want to count being on the edge of the triangle as being in it, then you would use (d0 <= 0 and d1 <= 0 and d2 <= 0) or (d0 >= 0 and d1 >= 0 and d2 >= 0). In C++ code: Code:
bool isPointInsideTriangle(int px, int py, int v0x, int v0y, int v1x, int v1y, int v2x, int v2y) { int d0 = (v1xv0x) * (pyv0y)  (v1yv0y) * (pxv0x); int d1 = (v2xv1x) * (pyv1y)  (v2yv1y) * (pxv1x); int d2 = (v0xv2x) * (pyv2y)  (v0yv2y) * (pxv2x); return (d0 < 0 && d1 < 0 && d2 < 0)  (d0 > 0 && d1 > 0 && d2 > 0); } 

0 
Jul 22, 2006, 12:47 PM  #3 
Thank you. Your function works well.
EDIT: By the way, where'd you get that info? Last edited by wala; Jul 23, 2006 at 03:43 AM. 

0 
«
Previous Thread

Next Thread
»
Thread Tools  Search this Thread 
Display Modes  
Similar Threads  
thread  Thread Starter  Forum  Replies  Last Post 
Dynamic geometry application for Mac  Eugeny  Mac Applications and Mac App Store  0  Apr 8, 2014 02:16 PM 
Calculus, algebra, geometry etc apps  patent10021  iPad Apps  0  Feb 1, 2014 03:40 PM 
Sound question for you fine folks  lightz39  MacBook Pro  0  Jun 26, 2013 02:22 PM 
To all the know it all folks out there  bigjim83  Wasteland  7  Sep 16, 2012 12:49 AM 
Price Advice: tax free weekend question for NC folks  exchen83  Buying Tips and Advice  3  Aug 2, 2012 10:25 AM 

All times are GMT 5. The time now is 07:14 AM.