NP > Math >

Determining if a point is in a triangle

Suppose you have 3 points in 2D space that represent a triangle. Now suppose you have another point and you want to know if that point is inside the triangle. How do you do that algorithmically without plotting it and doing a visual confirmation?

This method is called walking-around-the-edge. Pretend you are walking around the edges of the triangle. Let's call our 3 corners A, B, and C. Let's call the point you're trying to figure out if it's inside or outside of the triangle P.

• Start at A.
• Walk to B.
• Then Walk to C.
• Then walk back to A.
• If P was to your left the entire time, then it must have been inside the triangle and you must have been walking counter-clockwise.
• If P was to your right the entire time, then it also must have been inside the triangle and you must have been walking clockwise.
• If P switched from your left to right or vice versa, then it couldn't have been inside the triangle.

(Go ahead and draw some test examples if you aren't convinced)

So now, given a vector, how do you determine if a point is to the left or the right? Cross product.

Cross Product Refresher

Point Q = (q_x, q_y)
Point R = (r_x, r_y)
Point S = (s_x, s_y)
Point T = (t_x, t_y)

Vector QR = (r_x - q_x), (r_y - q_y)
Vector ST = (t_x - s_x), (t_y - s_y)

QR × ST = (r_x - q_x) * (t_y - s_y) - (t_x - s_x) * (r_y - q_y)

If AP × AB, BP × BC, and CP × CA all have the same sign, then P is inside triangle ABC. If not, then P is outside triangle ABC. If 2 of the cross products are 0 then P is at a corner. If 1 of the cross products is 0 then P is inside ABC if the other two cross products have the same sign. If 1 cross product is 0, another one is positive, and another is negative, then P is outside ABC.

The beauty of this method is that it requires no complex math to implement. Everything you see is multiplication and subtraction. Also, if your original points are integers, then all your math will be in integers also. That makes computational time very fast when you do this on a computer making this ideal for use inside 3D graphics engines.

Here is an example. See if the point is inside or outside the triangle. If you get stuck, raise your hand.

A: (1, 2)
B: (3, 5)
C: (8, 3)

P: (5, 4)

Other sites I run: Two Cans & String | Linked List | Crayon Programming Language | An ordinary blog | asdfjkl; | asdf;lkj

© 2024 Nerd Paradise