Archived

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

Andos

Point-in-polygon test

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
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
Yann L:
I don''t understand you code here:
if( Pt2dInTri(A, B, C, P) ) return(1);

What is the mathematical formula?
Like:
if bla bla bla return (1)

What does "p" do? It''s in the formula.

Share this post


Link to post
Share on other sites
Hey at maby you could write an extension for me. The extension SDK can be found at the download section of www.clickteam.com
You know... I''m making games with the Multimedia Fusion program and people that can code in C or something can make extensions to that. Creating those extension shold be an easy task for you hardcore programmers. Try out the demo for MMF 1.5 You''ll love it. Then you can understand how extensions work.

Share this post


Link to post
Share on other sites
Ahh. Forgot to explain what an extensions is... An extension for Multimedia Fusion is an object (.cox) file that can things that MMF can''t do.

Share this post


Link to post
Share on other sites
quote:

I don't understand you code here:
if( Pt2dInTri(A, B, C, P) ) return(1);


It's just a function call to the Pt2dInTri() function I posted above.

quote:

What does "p" do? It's in the formula


P are the coordinates of the point you want to test, if it is in the quad or not.

quote:

What is the mathematical formula?
Like:
if bla bla bla return (1)


It's not that easy, I'm affraid. A point in polygon test is much too complex to be squeezed in a simple mathematical equation. It's an algorithm that requires lots of separate equations and conditional branching depending on their result. Can't put that into a single formula.

What programming language do you use ?

[Edit]
S1CA: very nice article. The timing tables are interesting, gave me some ideas to optimize my collision detection...

[edited by - Yann L on March 21, 2002 4:02:58 PM]

Share this post


Link to post
Share on other sites