Menu
Given a point's coordinates, how can I determine if it is within an arbitrary shape?
The shape is defined by an array of points, I do not know where the shape is 'closed', the part I really need help is to work out where the shape is closed.
Here's an image to illustrate what I mean a little better:
898
Draw a horizontal line to the right of each point and extend it to infinity. Count the number of times the line intersects with polygon edges. A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon. If none of the conditions is true, then point lies outside.
Think about the 2d case: You can check if a point is within the square at x=a,b y=c,d ,(that is: a<x<b, c<y<d) by checking that x>a, x<b, y>c, y<d. The distance between your point and all the planes can not be zero, or you have a zero sized shape.
An arbitrary shape. The word arbitrary in this context means any as in: not a specified, or specific, kind of shape.
Easiest way to do it is cast a ray from that point and count how many times it crosses the boundary. If it is odd, the point is inside, even the point is outside.
Wiki: http://en.wikipedia.org/wiki/Point_in_polygon
Note that this only works for manifold shapes.
80
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
