determine if a point sits inside an arbitrary shape?
Solution 1
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.
Solution 2
If you want to determine whether or not a point P is in an arbitrary shape, I would simply run a flood fill starting at P. If your flood fill leaves a pre-determined bounding box, you are outside the shape. Otherwise if your flood fill terminates, then you're within the shape :)
I believe this algorithm is O(N^2) where N is the number of points, since the maximum area is proportional to N^2.
Wikipedia: Flood Fill
gibo
Updated on July 09, 2022Comments
-
gibo almost 2 years
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: