# Distance estimation to an implicit function graph

Writing an implicit equation as $f(x,y) = 0$, the closer $f(x,y)$ is to $0$ the closer a point is to the graph of the implicit equation. For $y^x = x \cos(xy)$, $f(x,y)$ would be $y^x - x \cos(xy)$, for example.

Simply using $f(x,y)$ to calculate the distance results in a very uneven estimate; the faster $f(x,y)$ is changing, the smaller the estimated distance. To compensate for this I divide by the magnitude of the rate of change in $x$ and $y$:

$$d(x,y) = \dfrac{f(x,y)}{\sqrt{\left(\frac{\partial}{\partial x} f(x,y)\right)^2 + \left(\frac{\partial}{\partial y} f(x,y)\right)^2}}$$

This is the best approximation for the distance $d$ that I've come up with that estimates distance from a point to a general implicit curve. When graphing $d(x,y) = r$ where $r$ is the approximate distance from $(x,y)$ to the graph of $f(x,y) = 0$, $d(x,y) = r$ should be approximately the same distance from $f(x,y) = 0$ at each nearest pair of points.

It seems accurate enough visually for most functions, for some functions like $e^x$ are particularly troublesome. For small values of $r$ the image looks acceptable but for values > 1 the distance gets incorrectly shrunken for $x > 0$, which blows the graph way out of proportion when $x > 0$.

Is there a way to do this more accurately?

Edit: The motivation for this is to rasterize user-defined implicit functions, so the distance function will be sampled for each pixel in the image.

-
@jhm2: reminds the Gauss method for solution of nonlinear equations. –  Ilya Aug 22 '11 at 16:53
add comment

## 2 Answers

There is no really accurate way to do this from "local" information, because the derivatives are not constant and can change in an unpredictable way before you get to the curve. The next level of approximation would be to use second derivatives as well as first derivatives, basically approximating $f(x,y)$ as a quadratic $q(x,y)$ in the neighbourhood of the point in question; then $q(x,y) = 0$ describes a conic section, and you take the distance to that.

The exact solution might be obtained as follows. If $(x_0, y_0)$ is your given point and $(x_1, y_1)$ is the closest point to it on the curve, then $\nabla f(x_0,y_0)$ is a scalar multiple of $(x_1 - x_0, y_1 - y_0)$. So solve, if you can, the system of equations $$\begin{eqnarray*} f(x_1,y_1) &= 0 \\ (y_1 - y_0) \frac{\partial f}{\partial x}(x_1, y_1) - (x_1 - x_0) \frac{\partial f}{\partial y}(x_1,y_1) &= 0 \end{eqnarray*}$$ There may be several solutions, in which case you take the closest one to $(x_0, y_0)$.

-
add comment

You can use higher-order terms. See Distance approximations for rasterizing implicit curves by Taubin.

-
+1. Here's the link on CiteSeer: citeseerx.ist.psu.edu/viewdoc/… –  jnm2 Aug 22 '11 at 17:16
add comment