1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ since you're a programmer, have you considered how robust a winding number calculation is on a computer? $\endgroup$ – cactus314 Aug 1 '13 at 23:08
  • $\begingroup$ @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. $\endgroup$ – Codie CodeMonkey Aug 1 '13 at 23:19
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Good idea for the star case, although I was hoping for something for general simple-closed boundaries. $\endgroup$ – Codie CodeMonkey Aug 2 '13 at 0:50
  • $\begingroup$ 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. $\endgroup$ – bubba Aug 2 '13 at 1:17
  • $\begingroup$ 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. $\endgroup$ – Codie CodeMonkey Aug 2 '13 at 1:58
1
$\begingroup$

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.

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