🔒 Locked

Point inside the triangle?

Started by TheVoid Apr 28, 2003 at 4:59 AM 11 replies 1.9k views

Original Post

Apr 28, 2003 at 4:59 AM

Let's say I have the triangle ABC and the point P (all in 2D). I want to check if the point P is inside the triangle ABC. So I need to calculate: cosangle1 = Dot(P - A, P - B) / Magnitude(P - A) * Magnitude(P - B); cosangle2 = Dot(P - B, P - C) / Magnitude(P - B) * Magnitude(P - C); cosangle3 = Dot(P - C, P - A) / Magnitude(P - C) * Magnitude(P - A); sum = cosangle1 + cosangle2 + cosangle3; And now I have a question: what will be the sign of 'sum' if the point is inside the triangle and what if it is outside? [edited by - TheVoid on April 28, 2003 6:04:11 AM]

v71

Apr 28, 2003 at 5:55 AM

if ( sum >2*3.14159236 ) return true
else return false

assuming true for inside

Enselic

Apr 28, 2003 at 6:03 AM

Not the sum of the cos values, but the sum of the degrees in radians.

cos v != v

So if v1 + v2 + v3 is close to 2*pi then the point is inside the triangle. And btw, this is true for any convex polygon.

______________________________
Enselic''s Corner Code Sampler

drslush

Apr 28, 2003 at 7:09 AM

Actually, you don''t even need those equations. If you are working in 2d (and even 3d, as long as you project all the coordinates to an abitrary 2d space). All you need to do is cast a ray in any direction from the point and count the number of lines that are crossed. Since it doesnt matter which direction, you can translate the triangle so that the original point becomes the origin of the system, then find how many lines in the triangle cross the positive X-Axis. This is an extremely quick operation, and you can make a great deal of optimizations based on trivial exclusion. If you want some code, I can post some here for you.

grhodes_at_work

Apr 28, 2003 at 12:48 PM

Check out the link near the bottom in the forum FAQ:

Forum FAQ

Its a discussion of point-in-polygon strategies.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

TheVoid

Apr 29, 2003 at 5:50 AM

But what if I have cos of angle not angle in radians? I need to know it!

Edited/Added:
I know I can get the angle in radians using acos() function, but I want to know it when I have cos of angle.

[edited by - TheVoid on April 29, 2003 9:23:12 AM]

drslush

Apr 29, 2003 at 8:23 AM

You have an angle measurement in degrees and want to convert to radians? 2*PI radians = 360 deg, so just multiply your degrees by PI/180.

TheVoid

Apr 29, 2003 at 8:31 AM

No, no. Please, read it carefully.

drslush

Apr 29, 2003 at 9:14 AM

Aight... so you have the cos of the angle, and you want to find the angle itself? Whats the problem with acos? Please clarify.

TheVoid

Apr 29, 2003 at 10:12 AM

I need to know the sign of the ''sum'' if the point is inside the triangle and outside. I need to know whether the ''sum'' will be greater, greater or equal, less, less or equal or equal to 0.

Enselic

Apr 29, 2003 at 1:48 PM

The sum of the degrees should be close to pi.
Write something like:


if( sum < 3.07 && sum > 3.21 )

Just change the values to a boundary which fits your needs.

__________________________ ____ ___ __ _
Enselic's Corner - CodeSampler.com

[edited by - Enselic on April 29, 2003 2:49:35 PM]

[edited by - Enselic on April 29, 2003 2:50:16 PM]

TheVoid

Apr 30, 2003 at 9:06 AM

But I have cos of the angle not the angle!

Enselic

May 2, 2003 at 8:35 AM

You want to know what you will end up with if you add the three cos values, don't you? Well I've thought of it for a while and come up with this:

Since v is not propotional to cos v the sum of three cos v with v1 + v2 + v3 = 360° will not have a constant value. I've tried to prove that but I'm not smart enough... Well, consider you have cos v1 + cos v2 + cos v3 and then change the angles but still keep the sum of the angles to equal 360° and the result is not the same (cos (v1 + 30) + cos (v2 - 30) + cos v3)...

Example:
cos 120° + cos 120° + cos 120° = -1.5
cos 150° + cos 90° + cos 120° = -1.366

Anyone disagree or have a better prove?

____________________ ____ ___ __ _
Enselic's Corner - CodeSampler.com

[edited by - Enselic on May 2, 2003 9:35:34 AM]

[edited by - Enselic on May 2, 2003 9:36:04 AM]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.