What methods exist for returning all points within an arbitrary closed shape?

I have been reading about range search algorithms, but most that I read apply only to a simple range (such as a standard rectangle in 2d).

In a similar fashion, what options exist for range search algorithms across arbitrary closed shapes? For example, if I had a binary image of a person, and random points across the image, how do I determine which points lie on the portion of the person?

• Have you tried Google? – Janoma Oct 13 '11 at 1:46
• It's not clear to me if you really want range search in your application. – Yoshio Okamoto Oct 13 '11 at 13:37

For any set of $n$ points, if you want to answer range queries for arbitrary ranges, all $2^n$ subsets are possible answers. (In fact, for any set of $n$ points in convex position, every subset is the intersection with some convex range.) It follows immediately that any query algorithm (describable as a decision tree) requires $\Omega(n)$ time, no matter how much time and space you spend preprocessing the points.