#### Archived

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

# Point-in-polygon test

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

## 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 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 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.

##### 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 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 on other sites
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 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 on other sites
OK, so you want a point in polygon test for deformed squares (quads).

------------|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 triangleif( Pt2dInTri(A, C, D, P) ) return(1);    // point is in the second trianglereturn(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 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?

Andos,

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 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 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 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 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 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 ?

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]