5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ By the way, the title should probably be "How to determine whether a node is outside or inside a curve". Either that or you're forgetting about the cathode? $\endgroup$
    – user3883
    Nov 30, 2014 at 15:44

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Nice idea to first use a piecewise linear approximation and then check for ray-curve intersection with a numerical method on the actual curve. However, what happens if the point is outside the piecewise linear approximation, but inside the actual curve. Won't then the suggested approach fail? $\endgroup$
    – Amos Egel
    Nov 17, 2023 at 14:26
  • $\begingroup$ @AmosEgel I suggested the polygonal approximation more for localizing where on the parametric curve you look. That way you're more likely to start in the quadratic convergence basin if you use Newton's method to find the intersection of the ray and the true curve. You don't actually do any inside/outside queries on the polygon. $\endgroup$ Nov 17, 2023 at 17:14
8
$\begingroup$

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:

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.