Jump to content
  • Advertisement

Archived

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

Andos

Point-in-polygon test

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

Please show me some simple formulas to find out if a point is in a deformed square. ( a square polygon ) I''ve seen LOTS of tutorials to make the point in polygon tests but I don''t understand anything of it... I''m from Denmark and I''m only 16 years old...

Share this post


Link to post
Share on other sites
Advertisement
quote:

Please show me some simple formulas to find out if a point is in a deformed square


There is no ''simple'' one. For a standard bounding rectangle it''s trivial. But as soon as it becomes a general polygon, it''s more complex.

The simplest way would be to treat the quad as two triangles and perform a point in triangle test, which is not that problematic. This would also allow concave quads.
You''ll get point in triangle tests on almost any computational geometry page (read: Google), it''s a standard algorithm.

Share this post


Link to post
Share on other sites
For a point in polygon test, couldn''t you take the normalized normal of the triangle / polygon and the normalized normal of point + 2 verticies of the triangle / polygon and if they''re equal, it''s in the triangle, if they aren''t it''s not? If you wind it right, a coplanar point in the polygon will have the same normal and a coplanar point outside the polygon will have the inverse of it''s normal.

Please...It''s a question, not an answer.

Share this post


Link to post
Share on other sites
Hmm, well it kind of works. You''ll have to be very carefull when selecting the 2 reference vertices, or it might fail. It won''t work on concave polygons.

This is the easiest and fastest point-in-triangle code I know of. It uses a somewhat similar method to yours, but takes all points into account to determine normal (vertex ordering) differences. It only works on triangles. If you want to use it for arbitrary polygons (incl. concave), triangulate them first.


  
//----------------------------------------------------------------------------

// CHECKS IF 2D POINT P IS IN TRIANGLE ABC. RETURNS 1 IF IN, 0 IF OUT

// Given a triangle ABC and a point P, determines if P is inside

// of ABC (regardless of vertex ordering - CCW or CW). 2D version only, but

// this handles the 3D case if appropriately projected to the XY, YZ, or XZ

// planes (by dropping corresponding component; i.e. drop Z in XY projection).

//----------------------------------------------------------------------------

int Pt2dInTri(Vect2d A, Vect2d B, Vect2d C, Vect2d P)
{
// FIRST CHECK THE SIGN OF THE Z-COMPONENT OF THE NORMAL BY CALCULATING

// THE CROSS-PRODUCT (ABxBC). THIS WILL DETERMINE THE ORDERING OF THE

// VERTICES. IF NEGATIVE, VERTICES ARE CLOCKWISE ORDER; OTHERWISE CCW.

// THEN EVALUATE SIGN OF Z-COMPONENTS FOR ABxAP, BCxBP, and CAxCP TO

// DETERMINE IF P IS IN "INSIDE" HALF-SPACE FOR EACH EDGE IN TURN ("INSIDE"

// IS DETERMINED BY SIGN OF Z OF NORMAL (VERTEX ORDERING).

// NOTE: FULL CROSS-PRODS ARE NOT REQUIRED; ONLY THE Z-COMPONENTS

Vect2d dAB=B-A, dBC=C-B; // "REPEATS"

if ((dAB.x*dBC.y-dAB.y*dBC.x) < 0) // CW

{
if (dAB.x*(P.y-A.y) >= dAB.y*(P.x-A.x)) return(0); // ABxAP

if (dBC.x*(P.y-B.y) >= dBC.y*(P.x-B.x)) return(0); // BCxBP

if ((A.x-C.x)*(P.y-C.y) >= (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP

}
else // CCW

{
if (dAB.x*(P.y-A.y) < dAB.y*(P.x-A.x)) return(0); // ABxAP

if (dBC.x*(P.y-B.y) < dBC.y*(P.x-B.x)) return(0); // BCxBP

if ((A.x-C.x)*(P.y-C.y) < (A.y-C.y)*(P.x-C.x)) return(0); // CAxCP

}
return(1); // "INSIDE" EACH EDGE''S IN-HALF-SPACE (PT P IS INSIDE TRIANGLE)

};

Share this post


Link to post
Share on other sites
I don''t understand this.
You use complicated english.

Trivial, vertices, concave, arbitary, coplanar, inverse of it''s normal?
What does this mean?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
convex polygon:

walk through every edge (side, line whatever its called) of the polygon, and test the point against it. if it''s on the left side of every line in the polygon (or directly on the line if you will), the point is inside.

Share this post


Link to post
Share on other sites
But how do I check if the dot is on the other side of the sides/lines?
I''ve asked my math teacher but she didn''t know how to do it.
Do you know any formulas or some other ways to find out?

Share this post


Link to post
Share on other sites
OK, so you want a point in polygon test for deformed squares (quads).

Your polygon is something like:


------------
|A B|
| |
| |
|D C|
------------
(Damn, I suck at ASCII, I hope this thing doesn''t screw up...)

A,B,C,D are the 4 corner points (vertices) of your polygon.

Now divide it into 2 triangles: A,B,C and A,C,D. just think of it, as if you would slice it in two halfs, with a line through A->C.

Finally, you use the algorithm I posted earlier to test your point (P) against both triangles:


if( Pt2dInTri(A, B, C, P) ) return(1); // point is in the first triangle
if( Pt2dInTri(A, C, D, P) ) return(1); // point is in the second triangle
return(0); // point is in neither one, so it is not in the polygon


It will return 1, if the point P is in the quad A,B,C,D.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
<<But how do I check if the dot is on the other side of the <<sides/lines?
<<I''ve asked my math teacher but she didn''t know how to do it.
<<Do you know any formulas or some other ways to find out?


Andos,

your math teacher sucks! :-)


check out this link, it covers the thing i talked about before (on which side the point is in respect to the line):

http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/

Share this post


Link to post
Share on other sites
By coincidence this topic came up on GDAlgorithms recently. Eric Haines has done an article about point in polygon methods (and their relative performance):

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

--
Simon O''Connor
Creative Asylum Ltd
www.creative-asylum.com

Share this post


Link to post
Share on other sites

  • 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!