Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Point in triangle algorithm
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Mazer




PostPosted: 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
Sponsor
sponsor
thegoose




PostPosted: 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 float-point errors which happens if you check for angles.
Mazer




PostPosted: 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




PostPosted: 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*y1-x1*y3-x3*y2-x2*y1)/2

also you might want to be careful about floating point errors... instead of checking for strict inequality, check for abs(b-a)<eps, where eps can be a small value, such as 1e-12 (0.000000000001)
Mazer




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

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




PostPosted: 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




PostPosted: 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




PostPosted: 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)
Floyd-Warshall (multiple source shortest path)
network flow

some lesser common problems involves optimization, computational geometry, strings, big integers, and math problems Smile

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 3rd-4th year university class
Mazer




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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




PostPosted: 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)
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 14 Posts ]
Jump to:   


Style:  
Search: