1

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?

Codie CodeMonkey
  • 188
  • since you're a programmer, have you considered how robust a winding number calculation is on a computer? – cactus314 Aug 01 '13 at 23:08
  • @johnmangual, the fact that winding numbers are integers covers a multitude of rounding and truncation errors, but if I wanted to work harder I'd use a more robust method like vector crossing counts. I was using winding numbers as a quick way to get Mathematica's RegionPlot function to work with a fairly simple boundary. Anyway, my question is more one of curiousity, it's not tied to my work. – Codie CodeMonkey Aug 01 '13 at 23:19

2 Answers2

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

bubba
  • 43,483
  • 3
  • 61
  • 122
  • Good idea for the star case, although I was hoping for something for general simple-closed boundaries. – Codie CodeMonkey Aug 02 '13 at 00:50
  • I did have an idea ... fire a ray in the horizontal direction. Let $d1$ and $d2$ be the distances to the first boundary intersections on the left and the right. Do the same thing with a vertical ray, and get two more distances $d3$ and $d4$. Compute some composite distance as a function of $d1$ through $d4$ (e.g. their minimum, or root mean square, or something). This would give you what you want, but it seems hopelessly complex, so I didn't write it as an answer. – bubba Aug 02 '13 at 01:17
  • yeah, your post gave me the same idea, which lead me to the idea of using the medial axis to give a metric. See if you like it. – Codie CodeMonkey Aug 02 '13 at 01:58
1

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.

Codie CodeMonkey
  • 188