#### Archived

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

# PointInPolygon

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

## Recommended Posts

How check if point x,y is inside polygon shape which has four verticies? Pekka Heikura

##### Share on other sites
I haven''t tried this, but my idea is that you would have to get the slow for each line in that polygon, and check the X and Y values of your point against each of X and Y values that you get by plugging in the your X/Y value into the line formula for each of those lines. I hope this makes some sense. If it doesn''t then let me know, and I''ll try to implement it.

------------------------------------
That's just my 200 bucks!

##### Share on other sites
Honestly, I have no idea what this is doing, but it does seem to work.
  bool PointInPoly( int npol, float *xp, float *yp, float x, float y ) { int i, j, c = 0; for( i = 0, j = npol - 1; i < npol; j = i++ ) { if (((( yp <= y) && ( y < yp[j] )) || (( yp[j] <= y ) && ( y < yp ))) && ( x < ( xp[j] - xp[i] ) * ( y - yp[i] ) / ( yp[j] - yp[i] ) + xp[i] )) c = !c; } return c; }

I'm not sure what this returns if the point is on an edge.

-Sirius
Confucius say: Do not disturb sleeping dragon, for you are crunchy and will taste good with ketchup.

Edited by - Sirius on July 17, 2000 1:08:52 PM

##### Share on other sites
Here's the function I use in "The Class Library That Still Has No Codename". It's basically the same, but class-ized.

The Count() function returns the number of points in the polygon. The [] operator returns the nth point. The rest should be pretty self-explanatory.

  bool Polygon::Inside(const Point &rPt){ bool RetVal = false; for (ui16 i=0, j=Count()-1; iY() <= rPt.Y()) && (rPt.Y() < pPtj->Y())) || ((pPtj->Y() <= rPt.Y()) && (rPt.Y() < pPti->Y()))) && (rPt.X() < (pPtj->X() - pPti->X()) * (rPt.Y() - pPti->Y()) / (pPtj->Y() - pPti->Y()) + pPti->X())) RetVal = !RetVal; } return RetVal;}

Edited by - johnhattan on July 17, 2000 1:43:21 PM

##### Share on other sites
It''s the same as the other code given. Can anyone please explain the algorithm behind it? Is there a formula for calculating if a point is inside a polygon (with 4 cvertices) or what?

-------------------------------------
That's just my 200 bucks!

##### Share on other sites
You could also use a general algorithm... it even works in 3D...

Just calculate the sum of the angles for each angle of the polygon... so what does that mean exactly....

imagine that you have a square...

v0---v1
| |
| p |
| |
v2---v3

now you calculate the angles for p-v0, p-v1, p-v2, p-v3 if the sum of the angles is in the neighborhood of 360 degrees (or 2Pi) then the point is in... otherwise it is out.

If you do not fully understand this... mail me at:

mitolah@hotmail.com (although I will not reply before next Friday)

Greetings Dark

##### Share on other sites
Sorry about my image... it is f#cked up

B.T.W Sirius... your method is quite nice... I understand what it does... although it has one major drawback... If you try to implement is for ##-ngons (where ## is a large number) it is slowwww....

Dark

##### Share on other sites
quote:

It''s the same as the other code given. Can anyone please explain the algorithm behind it? Is there a formula for calculating if a point is inside a polygon (with 4 cvertices) or what?

This Delphi code should do it easily...
(Got this one through the DelphiGames ML long ago and it works fine for me )

function PointInQuad(x0, y0, x1, y1, x2, y2, x3, y3, x, y: single): boolean;
begin
if ((y0 - y1) * (x - x1) + (x1 - x0) * (y - y1) > -1) then
if ((y1 - y2) * (x - x2) + (x2 - x1) * (y - y2) > -1) then
if ((y2 - y3) * (x - x3) + (x3 - x2) * (y - y3) > -1) then
if ((y3 - y0) * (x - x0) + (x0 - x3) * (y - y0) > -1) then begin PointInQuad := true; Exit; end;
if ((y0 - y1) * (x - x1) + (x1 - x0) * (y - y1) < 1) then
if ((y1 - y2) * (x - x2) + (x2 - x1) * (y - y2) < 1) then
if ((y2 - y3) * (x - x3) + (x3 - x2) * (y - y3) < 1) then
if ((y3 - y0) * (x - x0) + (x0 - x3) * (y - y0) < 1) then PointInQuad := true;
end;

--
Kyodai Mahjongg
kyodai.com

##### Share on other sites
>Can anyone please explain the algorithm behind it?

The previous functions use intersections, here is how it works:
- trace an horizontal line, passing through your points
- count the number of intersection between this line and polygon''s edges that are to the right (or left if you wish, does not matter) of your point

If the number of intersection is 1, 3, 5, 7... (nb impairs) your point is inside the polygon, if it is 0, 2, 4, 6, 8... (nb pairs) your point is outside. In the algorithm a boolean is used to count the line, because the number of intersection itself does not matter, only its parity is used.

Try it with a paper and pencil and you''ll see the logic, it works for all polygons, convex or not.

PS: are 1, 3, 5, 7... odd or even numbers ? always messing up the translation on this one

Eric Grange

##### Share on other sites

if ((y0 - y1) * (x - x1) + (x1 - x0) * (y - y1) > 0) then the point (x,y) is to the right of line (x0,y0)-(x1,y1) This comes from the equation that determines the distance from a point to the nearest point on a line.

if you move clockwise around from (x0,y0)-(x1,y1) to (x1,y1)-(x2,y2) to (x2,y2)-(x3,y3) then back to (x0,y0) and (x,y) always lies to the right, then the point is within the quad.

Now do the same for counter clockwise (just look to see if the point is to the left)

This should work for any triangle, quad, or n-gon as long as the shape in convex.

[ turbo | turbo.gamedev.net ]

1. 1
Rutin
46
2. 2
3. 3
4. 4
5. 5
JoeJ
18

• 13
• 10
• 12
• 10
• 13
• ### Forum Statistics

• Total Topics
632998
• Total Posts
3009802
• ### Who's Online (See full list)

There are no registered users currently online

×