4
$\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
    $\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$ – Rahul Nov 30 '14 at 15:44
9
$\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$
6
$\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, privacy policy and cookie policy

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