How to determine if a point is outside or inside a curve

Question

Let curve $C_1$ be defined parametrically $$\begin{aligned} &x(t)=0.5\cos(t)-0.3\cos(3t),\\ &y(t)=1.2+0.6\sin(t)-0.07\sin(3t)+0.2\sin(7t) \end{aligned}$$

How do I find if an arbitrary point $P(x,y)$ is inside or outside of this curve?

Also, for another curve $C_2$

$$ \begin{aligned} &x(t)=0.4+\big(0.19+0.07\sin(5t)\big)\cos(t)\\ &y(t)=0.4+\big(0.19+0.07\sin(5t)\big)\sin(t) \end{aligned} $$ I tried with the set $r=0.19+0.07\sin(5t)$ and $t=\tan^{-1}(y/x)$:

if $(x-0.4)^2+(y-0.4)^2\leq r^2$ I supposed that point is inside, but this is not correct for some points.

Answer 1

There's a simple test to see if a point $(x, y)$ is enclosed within a curve. Draw a ray from $(x, y)$ to infinity, and count how many times it crosses the curve; if the count is odd, then $(x, y)$ is inside the enclosed region; otherwise, it's outside.

To turn this into a practical algorithm, you could first build polygonal approximation of the curve and look for all segments that the ray from $(x, y)$ intersects. This operation is linear in the number of segments of the polygon. Once you have all the candidate segments, you can use these as the basis for a Newton search to find a more exact point of intersection of the ray with the curve.

The last step might seem overly cautious, but if the point is closer to the curve than the accuracy of the piecewise-linear approximation, you can easily get a wrong answer. Since you have an analytic expression for the curve, you can also analytically compute its derivative; if the ray is really close to being tangent to the curve, expect trouble.

Even for curves that are exactly polygonal, the even/odd rule can fail in finite precision arithmetic. Computational geometry is tricky because there are often bizarre, unintuitive edge cases.

The book by de Berg and Cheong is a great reference on the subject; if you want a Python library to experiment with, I've had good luck with Shapely.

Answer 2

There's also the winding number test, described in the same Wikipedia article that Daniel linked to. The two algorithms give equivalent results for simple curves like yours, but they can differ for self-intersecting curves like this:

The ray casting method considers both points to lie outside the curve. On the other hand, the winding numbers of $p$ and $q$ are $2$ and $0$ respectively, so if you want to consider points like $p$ to lie inside the curve you can use the nonzero rule instead of the even-odd rule.

Of course, the caveats Daniel mentioned about sufficient sampling apply to both methods.