• ### Popular Now

• 15
• 15
• 11
• 9
• 10

#### Archived

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

# Point-in-polygon test

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