Generalizations of winding numbers

Question

This question came up because I needed a predicate that returns true if a point in $\mathbb{R}^2$ is interior to a simple closed contour and false otherwise. My initial choice was to use winding numbers.

But I was wondering if there were generalizations with better continuity properties than winding numbers. One could imagine that the contour might be a level set of some function $f:\mathbb{R}^2 \mapsto \mathbb{R}$ that is $C^1$ everywhere except finite points where the contour is $C^0$. Such a function would have the benefit that one could numerically test for nearness to the boundary.

I could construct such a function as $f_c(x,y)=d_c(x,y)W_c(x,y)$ where $W_c(x,y)$ is the winding number function with respect to contour $C$, and $d_c(x,y)$ is the square of the minimum distance to $C$, but that adds quite a lot of computational baggage to the already expensive winding numbers. Are there better choices?

Answer 1

A partial solution (which works only on star-shaped sets) ...

Take some "center" point $C$ in the star center. For each angle $\theta$, imagine a ray (a half-line) through $C$ at angle $\theta$. Intersect this ray with the boundary. Let the $d(\theta)$ be the distance from $C$ to the boundary intersection.

Approximate the function $d(\theta)$ by some easy-to-evaluate function, $f(\theta)$. For example, you could measure the value of $d(\theta)$ at some sample points in $[0, 2\pi]$, and fit some simple curve, like a cubic spline to these measured $d(\theta)$ values.

Then, given a test point $P$, you find the corresponding angle $\theta$ and test to see if the distance from $P$ to $C$ is less than $f(\theta)$. The ratio $\text{dist}(P,C)/f(\theta)$ gives you a measure of "how far inside" the test point $P$ is.

If you have to test a large number of points, this process is very fast, since it only requires that you calculate $\theta$ and the function value $f(\theta)$.

There is a connection with your idea of using level sets of some height function: the height function we're using is a "cone" whose apex is above the point $C$.

Answer 2

Bubba's answer gave me this idea:

Compute medial axis $M_C$ of the region $C$. For each point $m$ on $M_C$, assign $r_C(m)$ equal to the distance from $m$ to nearest point on $C$.

Now let $f_C(x,y)=r_C(m_C(x,y))-d((x,y),m_C(x,y))$, where $d$ is just the distance function.

$f_C$ has these properties:

• $f_C \leq max(r_C(m)) \;\;\; (m\epsilon M_C$)
• $f_C(m) = r_C(m) \;\;\; (m\epsilon M_C$)
• $f_C(c) = 0 \;\;\; (c\epsilon C$)
• $f_C(x) > 0$ on the interior of the contour
• $f_C(x) < 0$ on the exterior.

Then on the medial axis, $f_C$ is the distance to the contour, on the boundary $f_C$ is 0 (which follows from the definition of the medial axis and $r_C$. Inside of the contour $f_C$ is positive, and outside it's negative.

Although in applications $M_C$ and $r_C$ will have to be approximated (which will be expensive), it needs only to be done once for the contour. When actually evaluating $f$, the distance to $M_C$ has to be computed, but that's no harder than computing a distance to the contour.