Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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