# [ACCEPTED]-determine if a point sits inside an arbitrary shape?-shape

Score: 33

Easiest way to do it is cast a ray from 4 that point and count how many times it crosses 3 the boundary. If it is odd, the point is 2 inside, even the point is outside.

Note 1 that this only works for manifold shapes.

Score: 1

If you want to determine whether or not 8 a point P is in an arbitrary shape, I would 7 simply run a flood fill starting at P. If 6 your flood fill leaves a pre-determined 5 bounding box, you are outside the shape. Otherwise 4 if your flood fill terminates, then you're 3 within the shape :)

I believe this algorithm 2 is O(N^2) where N is the number of points, since 1 the maximum area is proportional to N^2.

Wikipedia: Flood Fill

Score: 0

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

More Related questions