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

Accepted answer
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.

Wiki: http://en.wikipedia.org/wiki/Point_in_polygon

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