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

## 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 on other sites
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 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 on other sites
Quote:
 Original post by jykSince 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 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 :-)

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 18
• 20
• 14
• 14
• 9
• ### Forum Statistics

• Total Topics
633377
• Total Posts
3011565
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

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!