determine if a point sits inside an arbitrary shape?

gibo picture gibo · Jun 26, 2011 · Viewed 19.1k times · Source

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:

enter image description here

Answer

Mikola picture Mikola · Jun 26, 2011

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.