Archived

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

clapton

Point Vs non-convex polygon

Recommended Posts

Hello! I have a polygon which is not convex and a point P. Let''s say that I already have all vector maths implemented. How can I check if the point is inside the polygon? Thanks in advance! ----------------- ... you got me on my knees, Layla

Share this post


Link to post
Share on other sites
1. test if point is on polygon's plane.
- insert point p into plane equation N dot p + d = 0
where d = -N dot p, N = normal to plane
-if the result is true (equation is 0), then point is on plane, continue
-if result is positive (p on N's side of plane) or negative (on opposite side as N), then break; b/c if it's not on plane then it can't be in polygon.

2. construct a plane for each edge of polygon, the planes should be parallel to the polygon's normal
-cross the poly normal with the an edge vector (v1 - v0). b/c cross product is not commutative, you have to do the difference (v1-v0) of edge vertices in ccw order if you want to return a plane normal that points to the inside of polygon. If you do it the other way around your normals will point to the outside of the polygon hull. So it all depends on how you plan on testing against the normal in the next step.

3. for each plane made you have to do what you did in step 1. Obviously if you get zero, then according to limited precision calculation the point is on the edge of the polygon and it's up to you whether or not it's part of polygon. If the normals of the plane edges point inward then the plane equation should return a positive amount. If the result is negative then your point is outside the polygon.

This is probably the most computationally expensive method but it's easily implemented with a vector library, so...

EDIT: scratch everything i just said. The above only works for convex polys no matter what order you try to test the edges in. But i've found a solution: As you are iterating over the edges in some order around the poly, you'll have to test each two edges and see if they make the polygon whole concave. If they do you'll have to project the surrounding edges so that they form a convex polygon that's not part of the original poly. Then test against both polys, ie, if a point passes the first test then test it against the new polygon, if it's inside this then you know it's not in the original poly. Another method would probably first transform the poly into sub polys that are convex, but you are effectively doin that with the said method.

EDIT2: Crap again, it turns out that there are some extreme cases that will escape the above methods. I think the only solution is to break the convave poly into all sub convex polys and then use the first test method on all. And that should work for an arbitrary complexity poly.

[edited by - temp_ie_cant_thinkof_name on April 5, 2004 4:18:21 PM]

Share this post


Link to post
Share on other sites
Is it a 2D-polygon?

Assuming it is a 2D-polygon:

your point p(x0,y0).

for each line of the polygon, do this:
{
Get the first point of the line (x1,y1).
Get the 2nd point of the line (x2,y2)
if y0 is between y1 and y2, do this:
{
Calculate the x-coordinate of the line in y=y0.
store this value in a list.
}
}

You now have a list with x-coordinates. Put x0 in the list, sort it, and count the amount of x-coordinates before x0.
If this number is odd (I am not sur if this is the correct term, English is not my native language. I mean that you can''t divide it by 2), than the point is in the polygon.

Share this post


Link to post
Share on other sites
A more robust solution is go through the list of edges, computing the angle from your point (with sign). Add all the angles. The resulting sum is 2*PI*N, where N is the number of times that the polygonal path goes around the point. For simple polygons, N should be 1 or -1 (depending on orientation) if the point is inside, and 0 if it''s outside.

Share this post


Link to post
Share on other sites
Hey guys! Great thanks for your help. Now I''ll check out all what you''ve said. I''ll let to you know when I manage to solve the problem.

Bye!

--------------


... you got me on my knees, Layla

Share this post


Link to post
Share on other sites
You could always split up the polygon into convex parts then use a more traditional method.

Share this post


Link to post
Share on other sites
generalization of what Koroljov said:

trace (an infinitely long) line from the point in any direction along the polygon''s plane. If it intersects an odd number of the polygon''s edges then the point is inside, otherwise it''s out.

(optimize by using something like +x for the line direction in 2d, which is how his algo works)

Share this post


Link to post
Share on other sites
quote:
Original post by Fingers_
generalization of what Koroljov said:

trace (an infinitely long) line from the point in any direction along the polygon''s plane. If it intersects an odd number of the polygon''s edges then the point is inside, otherwise it''s out.



Aa! Now I get it! I didn''t actually know how the code works and when I tried to write it didn''t work. I must have implemented it badly. I have to say that the method is very convincing.

Anyway, I tried to use a ready-solution. I''ve used some mathematics taken form www.gametutorials.com and everything works pretty well now.

I''ll go for the Koroljov''s solution also.

Thanks for your help!

-------------------




... you got me on my knees, Layla

Share this post


Link to post
Share on other sites