Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
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?

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 float-point 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.
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*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

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)
Floyd-Warshall (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 3rd-4th year university class

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)
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 14 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: