CODEWITHSUNDEEP
algorithmmathgeometryshapes
gibo
gibo

Reputation: 537

determine if a point sits inside an arbitrary shape?

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

Upvotes: 21

Views: 24886

Answers (3)

tskuzzy
tskuzzy

Reputation: 36446

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

Upvotes: 1

Grigor Gevorgyan
Grigor Gevorgyan

Reputation: 6853

Actually, if you are given an array of points, you can check the closeness of the shape as follows:
Consider pairs of points P[i] and P[i+1] given in the array - they form some segment of the border of your shape. What you need to check is if there exist two such segments that intersect, which can be checked in O(N^2) time (just by checking all possible pairs of such segments). If there exists an intersection, that means that your shape is closed.
Note: you must be attentive not to forget to check the segment P[0],P[n-1] either (i.e. first and last points in the array).

Upvotes: 0

Mikola
Mikola

Reputation: 9326

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.

Upvotes: 36

Related Questions