Register FAQ / Rules Forum Spy Search Today's Posts Mark Forums Read
Go Back   MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Reply
 
Thread Tools Search this Thread Display Modes
Old Jul 21, 2006, 08:47 PM   #1
wala
macrumors member
 
Join Date: Jun 2005
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.
wala is offline   0 Reply With Quote
Old Jul 22, 2006, 01:00 AM   #2
iSee
macrumors 68030
 
iSee's Avatar
 
Join Date: Oct 2004
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.x-v0.x) * (p.y-v0.y) - (v1.y-v0.y) * (p.x-v0.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.x-v0.x) * (p.y-v0.y) - (v1.y-v0.y) * (p.x-v0.x)
d1 = (v2.x-v1.x) * (p.y-v1.y) - (v2.y-v1.y) * (p.x-v1.x)
d2 = (v0.x-v2.x) * (p.y-v2.y) - (v0.y-v2.y) * (p.x-v2.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 = (v1x-v0x) * (py-v0y) - (v1y-v0y) * (px-v0x);
	int d1 = (v2x-v1x) * (py-v1y) - (v2y-v1y) * (px-v1x);
	int d2 = (v0x-v2x) * (py-v2y) - (v0y-v2y) * (px-v2x);
	
	return (d0 < 0 && d1 < 0 && d2 < 0) || (d0 > 0 && d1 > 0 && d2 > 0);
}
Would work as well using double or float in place of int.
iSee is offline   0 Reply With Quote
Old Jul 22, 2006, 12:47 PM   #3
wala
Thread Starter
macrumors member
 
Join Date: Jun 2005
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.
wala is offline   0 Reply With Quote

Reply
MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Thread Tools Search this Thread
Search this Thread:

Advanced Search
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

Forum Jump

All times are GMT -5. The time now is 04:45 AM.

Mac Rumors | Mac | iPhone | iPhone Game Reviews | iPhone Apps

Mobile Version | Fixed | Fluid | Fluid HD
Copyright 2002-2013, MacRumors.com, LLC