Jump to content
• Advertisement

#### Archived

This topic is now archived and is closed to further replies.

# Calculating if a point is within a triangle?

This topic is 5723 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## Recommended Posts

Im trying to come up with a way using C++ to determain if a point lies within a triangle. Does anyone know how to do this?

Advertisement

#### Share this post

##### Share on other sites
sopose that you have the triangle (v1, v2, v3) and the point p

then if

(v2-v1)x(p-v1), (v3-v2)x(p-v2) and (v1-v3)x(p-v3) have all the same sign the point is in the triangle.

x is the vectorial product

// naher

#### Share this post

##### Share on other sites
MollerTrumbore97
http://www.acm.org/jgt/papers/MollerTrumbore97/

#### Share this post

##### Share on other sites
Basically, three half-plane tests that all have to return the same sign. This allows you to generate your normals in either direction, as long as they''re all consistant.

#### Share this post

##### Share on other sites
but how about p is in line v1 and v3??ie p, v1, v3 are collinear

#### Share this post

##### Share on other sites
Right, so to expand the half-plane test rule, all non-zero numbers have to be the same sign. If two of the numbers are zero though, then it''s automatically inside the triangle, because that means it''s colinear with two of the sides (i.e on the corner).

#### Share this post

##### Share on other sites
could u give a definition of each variable

#### Share this post

##### Share on other sites
Just a quick tip:

If you''re scanning through lots of triangles to see if the point falls within them, it can be handy to use a quick test to test if it DOESN''T lie in the triangle.
E.g. if x-value of the point is less than the x-values of the all the triangle corners, then you can skip that triangle.
Then you only use the proper point-in-triangle stuff if the quick tests pass.

I''m sure you get the idea. This should speed it up a little.

#### Share this post

##### Share on other sites
Each "variable" would be the distance from the point to each side respectively. The distance from the point to a side is defined by:

DotProduct(point, sideNormal) - DotProduct(sideNormal, known point on side)

But like tuita said, always perform the trivial tests first so you can possibly eliminate superfluous calculations.

#### Share this post

##### Share on other sites

• Advertisement

### Announcements

• Advertisement

• ### Popular Contributors

1. 1
2. 2
3. 3
4. 4
Rutin
17
5. 5
• Advertisement

• 11
• 30
• 12
• 12
• 11
• ### Forum Statistics

• Total Topics
631408
• Total Posts
2999922
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!