Jump to content
  • Advertisement
Sign in to follow this  
Christopher Harris

A faster way? 2D Point In Tri test

This topic is 4487 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

So heres my code:
float Math::PointToLine (VEC2 &_p, VEC2 &_v1, VEC2 &_v2)
{
        // Distance from Point to Infinite Line
	return ((-(_v2.y - _v1.y))*(_p.x - _v1.x) + (_v2.x - _v1.x)*(_p.y - _v1.y));
}



bool Math::PointInTri (VEC2 &_vec, TRI &_tri)
{
        // Is _vec inside _tri?

	if(!PointInRect(_vec, _tri.rect))
		return false;

	if(PointToLine(_vec, _tri.a, _tri.b) < 0)
		return false;

	if(PointToLine(_vec, _tri.b, _tri.c) < 0)
		return false;

	if(PointToLine(_vec, _tri.c, _tri.a) < 0)
		return false;

	return true;
}



VEC2 is your basic 2D vector class. TRI is 3 VEC2's (a, b, and c) representing the three vertices of a triangle. the method "PointInTri" computes weither or not the given VEC2 _vec is inside of the TRI _tri. I'm only wondering if this is a fast way to test a point inside of a 2D triangle, or if there is a faster way. Sorry about the uncommented / crappy layout code.

Share this post


Link to post
Share on other sites
Advertisement
@The OP: The method you're currently using is actually related to barycentric coordinates. Although it would be good to read Zipster's link (the concept is an important one), for this problem you don't need to compute the actual barycentric coordinates, only their signs.

Your test is fairly optimal as is; it could probably be optimized a bit, but unless you're performing many such tests per frame it probably doesn't need to be.

Share this post


Link to post
Share on other sites
I don't know how many tests I'll be performing, but the entire level is 2D made up of triangles. the triangles (or the indexed triangles) will be held in a quadtree to reduce the ammount of rectangle tests I go through. However, as of right now I'll be using a "stepping" method to test and see if a point intersects a triangle while moving to a second point (only moving 5 or so pixels every step), each of these tests will be navigating though the quadtree.

I'm certain theres a better way to do 2D vector hit tests... Anyone?

Note: The idea is to make a non-tile-based platform game, hopefully incorperating some awesome physics later on.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!