Archived

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

PointInPolygon

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

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!

..-=gLaDiAtOr=-..

Share this post


Link to post
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<i> ))) &&
( 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 this post


Link to post
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; i<Count(); j=i++)
{
const Point *pPti = (Point *)operator[](i), *pPtj = (Point *)operator[](j);
if ((((pPti->Y() <= 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 this post


Link to post
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!

..-=gLaDiAtOr=-..

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
quote:
Original post by Gladiator

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?


4 vertices? You''re talking about a quad?
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
PointInQuad := false;
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
>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 this post


Link to post
Share on other sites
The concept behind PointInQuad is

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 ]

Share this post


Link to post
Share on other sites
It looks like the dot product of two vectors to me. I don''t know, I''m just getting started with 3D graphics, and I need to learn all the formulas that are used all the time in 3D programming.

btw, Any recommendations of websites that can teach me some of the maths in 3D programming (linear algebra, etc..) that has to do with programming and not only math. I would like to see it from the programmer''s view on those topics. Also, does anyone know where I can see a detailed description of the point to line intersection formula, and maybe a picture that depicts the theory? Thank you!

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

..-=gLaDiAtOr=-..

Share this post


Link to post
Share on other sites