[ACCEPTED]-determine if a point sits inside an arbitrary shape?-shape
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.
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
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
We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.