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:

You have to tell how the shape is defined by an array of points. If you mean that the array of points is the set of points within the shape, then the question is trivial.

The image in my post might explain it a little better.. I know the points along the blue line, but do not know where the cross closing the shape

Is the shape a polygon, or can the shape be defined by any mathematical function (e. g., x^2+2y^2 = r^2)?

3 Answers 3

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.

Note that this only works for manifold shapes.

This doesn't seem to work with the shape shown in the question, because of the two extremities outside of the polygon. A needed preprocessing step would be to identify the closing point and discard those two extremities.

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.

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).

When will p[i],p[i+1] and p[j],p[j+1] intersect? I think it would tell whether the shape is a simple polygon or a complex polygon. Also, you didn't answer the original question on how to find whether the point lies in the polygon.

@logic_max: Well, I answered the part of the question about how to check if the shape is closed, and, according to the problem statement, it must not necessary be a polygon, it can be an arbitrary polyline. Presence of any p[i],p[i+1] and p[j],p[j+1] intersection will only tell us that the shape has a closed part. What about the point inside - Mikola's answer is correct about it.

That doesn't work. What if you take a closed polygon, then add a dangling edge to it? In fact, I am not sure exactly what you are testing, and how it is related to the question?

@Mikola: Imagine you're standing in some corner of the shape, and want to know if it has a closed part (i.e. contains loop). If you move along the border and meet some point where the border intersects itself, that means that the shape contains a closed part (i.e. there exists a loop), and you can apply any method you like to check out if the point is inside. Otherwise, the shape may be just a curve in the space, and you can get wrong result if you start checking if the point is inside at once.

• algorithm
• math
• geometry
• shapes