Point in triangle algorithm
Author 
Message 
Mazer

Posted: Sun Sep 19, 2004 7:45 am Post subject: Point in triangle algorithm 


I've been reading up on collision detection, and most tutorials talk about how there are many algorithms for determining whether or not a point is on a triangle. But they all talk about one algorithm which involves getting angles and checking to see if their sum is ~2*Pi. They also tend to say that this algorithm, while simple, isn't the best.
Does anybody know which is the "best"? Or, of the algorithms you do know, which do you think is the best? 





Sponsor Sponsor



thegoose

Posted: Mon Sep 20, 2004 11:17 am Post subject: (No subject) 


The solution I'm familar with involves the usage of vectors. Essentially, you cycle through the edges on every two pairs of lines from a point. Then using cross product to check if the point is between the two lines using the cross product. If it's verified for all 3 points, then the point is inside the triangle. The good thing about this method is that it does not create any floatpoint errors which happens if you check for angles. 





Mazer

Posted: Mon Sep 20, 2004 12:48 pm Post subject: (No subject) 


Could you possibly explain that differently?
thegoose wrote: the edges on every two pairs of lines from a point. This line in particular, please. 





bugzpodder

Posted: Mon Sep 20, 2004 2:55 pm Post subject: (No subject) 


An easier way than what Richie mentioned is to the following:
if a point P is inside triangle ABC, then
Area PAB+Area PBC +Area PAC=Area ABC
notice that if P is on the edge of AB, BC, or CA, the above hold. But effectively, one of the area PAB, PBC, PAC is 0 (so just make sure you check that).
if P is outside, the above equality does NOT hold...
How to determine area? you have two options:
1) Heron's theorem, involves sqrt, slower
2) the more perferred way is the cross products (or effectively, the half of absolute value of (sum of the down products minus the sum of up products))
for example, if A=(x1,y1) B=(x2,y2), C=(x3,y3)
Area= abs(x1*y2+x2*y3+x3*y1x1*y3x3*y2x2*y1)/2
also you might want to be careful about floating point errors... instead of checking for strict inequality, check for abs(ba)<eps, where eps can be a small value, such as 1e12 (0.000000000001) 





Mazer

Posted: Mon Sep 20, 2004 3:54 pm Post subject: (No subject) 


Ah. Slick. But out of curiosity, are there more efficient methods? 





Paul

Posted: Mon Sep 20, 2004 7:40 pm Post subject: (No subject) 


speaking of algorithms, can anyone provide a list of commonly used algorithms for programming? cause... you need to learn this stuff for programming contests and such, and if I need to memorize them, I'll have to start now.
I found that this site: www.nist.gov/dads/
contains alot of info, but there's too much, plus I don't think ur allowed to use them for contests. 





bugzpodder

Posted: Tue Sep 21, 2004 11:07 am Post subject: (No subject) 


Mazer wrote: Ah. Slick. But out of curiosity, are there more efficient methods?
what do you mean by more efficent?? this is a constant time algorithm, and only a couple of lines 





bugzpodder

Posted: Tue Sep 21, 2004 11:14 am Post subject: (No subject) 


Paul wrote: speaking of algorithms, can anyone provide a list of commonly used algorithms for programming? cause... you need to learn this stuff for programming contests and such, and if I need to memorize them, I'll have to start now.
I found that this site: www.nist.gov/dads/
contains alot of info, but there's too much, plus I don't think ur allowed to use them for contests.
acm.uva.es
train.usaco.org
examples of algorithms are:
two things that are very common in a contest setting is Dynamic Programming/Memoization (which is a technique and not an "algorithm") and graph theory
there are a few typics of dynamic programming, such as Coin Change, edit distance, longest common subsequence, longest increasing subsequence, matrix manipulation, edit distance, etc
some examples of Graph theory
Depth first Search, Breadth first search (basic techniques)
Prim's (Minimum spanning Tree)
Dijkstra, Bellman Ford (single source shortest path)
FloydWarshall (multiple source shortest path)
network flow
some lesser common problems involves optimization, computational geometry, strings, big integers, and math problems
go get yourself an algorithm book
Intro to Algorithms 2 ed  MIT Press
The Art of Computer Programming  Donald E Knuth
Algorithm design mannual  steve Skiena
Algorithms in (C/C++/Java)  Robert Sedgewick
note most of those topics are covered in a typical 3rd4th year university class 





Sponsor Sponsor



Mazer

Posted: Wed Sep 22, 2004 10:51 am Post subject: (No subject) 


bugzpodder wrote: Mazer wrote: Ah. Slick. But out of curiosity, are there more efficient methods?
what do you mean by more efficent?? this is a constant time algorithm, and only a couple of lines
I wasn't trying to say that this way looked at all inefficient. But I'll be using this for collision detection, one freaking hell of a lot. I'm just looking for the best way to do it, if there is one. 





bugzpodder

Posted: Wed Sep 22, 2004 12:06 pm Post subject: (No subject) 


right, i realize that... but i wasnt sure what you had in mind. well now i know... but i think it is as efficient as it gets... 





Martin

Posted: Wed Sep 22, 2004 12:34 pm Post subject: (No subject) 


check to make sure that the distance that the other triangle is to the first triangle is within a range where collision is possible would speed things up a bit. 





Mazer

Posted: Wed Sep 22, 2004 1:00 pm Post subject: (No subject) 


Wouldn't that slow it down because of the square roots? Or do you mean to use an approximate distance function? And I'm already cutting out alot of tests by doing bounding box checks first. 





Martin

Posted: Wed Sep 22, 2004 2:02 pm Post subject: (No subject) 


So don't do square roots. Make it a cube or something fast like that. 





zylum

Posted: Wed Sep 22, 2004 2:54 pm Post subject: (No subject) 


if youre checking distance you dont even need to use square root, you could just do:
if (dist^2 >= x^2+y^2) 






