Jump to content
  • Advertisement
Sign in to follow this  
Codedummie

Point inside quadrangle?

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

Hi, I'm looking for an efficient way to determine if a point is on or inside an quadrangle (that is given by the x-y coordinates of the 4 points). Thanks in advance

Share this post


Link to post
Share on other sites
Advertisement
Since you say x-y I'm assuming 2D. For an arbitrary 4-sided polygon, you can determine if a point is inside the polygon by finding its signed pseudo-distance from the supporting line for each edge. If the signs are all the same, the point is inside the polygon. Or, if you know that the inside of the polygon is on the positive or negative side of the edges, you can early out. Here's a code sample which assumes the line normals point inward:


bool PointInQuad(
const Vector2& p // Point to test
Vector2 v[]} // Quad vertices
{
for (int i = 0; i < 4; ++i)
{
int j = (i + 1) % 4;
Vector2 edge = v[j] - v;
Vector2 diff = p - v;
float dot = edge.PerpDot(diff); // PerpDot() is -y*vx + x*vy or y*vx - x*vy
if (dot < 0.0f)
return false;
}
return true;
}


That's untested and not proofread, so there may be errors. But maybe it will be of some use to you.

Share this post


Link to post
Share on other sites
I'm not sure if jyk already said this and I just didn't noticed it , but if you find the angle between the point you are checking and the sides of the quadrangle and the angle is less than 90 degrees in all four cases, then the point is within the quad.

Here is an article explaining what I just tried to say:
clicky

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Since you say x-y I'm assuming 2D. For an arbitrary 4-sided polygon, you can determine if a point is inside the polygon by finding its signed pseudo-distance from the supporting line for each edge. If the signs are all the same, the point is inside the polygon. Or, if you know that the inside of the polygon is on the positive or negative side of the edges, you can early out. Here's a code sample which assumes the line normals point inward:

*** Source Snippet Removed ***
That's untested and not proofread, so there may be errors. But maybe it will be of some use to you.


Your algorithm should work for *convex* polygons, but if you have a reflex vertex this will not work. For an arbitrary quadrilateral, you can instead do the following, which reduces the number of dot products by one for the convex case. Let the counterclockwise ordered vertices be V[0], V[1], V[2], V[3]. If there is a reflex vertex, let it be V[0]. First test the point to see which side of the line through V[0] and V[2] it occurs. If it is on the side that contains V[1], then you have only two more which-side tests, one for the line through V[0] and V[1] and one for the line through V[1] and V[2]. If it is on the side that contains V[3], you have two more which-side tests. In total, you have three which-side tests.

Share this post


Link to post
Share on other sites
Quote:
Your algorithm should work for *convex* polygons...
Sorry, I should have specified that. My mistake. Regardless, point taken that four dot products is one too many :-)

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!