Determining whether images of two curves are close to each other

Question

I am coding an implementation of Boolean operations on SVG paths, and need to solve the following problem:

Given two sequences of curves, determine whether the distance between their images never exceeds $\varepsilon$.

I can assume that my curves are specified as polynomials is Bernstein basis (aka Bezier curves) or in symmetric power basis. I also have arcs, but I can approximate them by Bernstein or S-basis polynomials. I only need an approximate result.

A curve is a function from $[0, 1]$ to $\mathbb{R}^2$. Importantly, I need to determine whether the images of curves are close, so I can't simply calculate a difference and test whether it never exceeds some threshold. My goal would be to compute the nearest distance from one curve to the other at every point, and verify that it never exceeds some threshold.

I can compute the nearest distance from the curve $C(t)$ to the point $p$ by calculating the polynomial $(C_x(t)-p_x)^2 + (C_y(t)-p_y)^2$ and finding its roots, but I don't know how to generalize this so that I can find a function that gives the nearest distance at every point of the other curve. If I had a function $D(t)$ that would give the distance between $C^1(t)$ and the nearest point on curve $C^2$, I could just check whether $D(t)$ never exceeds $\varepsilon$.

I do not want to find $s$, $t$ that minimize the distance between $C^1(t)$ and $C^2(s)$. I need to verify that for every possible $t$, the nearest point on $C^2$ is no further than $\varepsilon$ away.

Answer 1

Let $C=(C_x^i,C_y^i)$, $i=1,2$ be the two curves. To find the distance between them you must minimize $$ F(s,t)=\bigl(C_x^1(s)-C_x^2(t)\bigr)^2+\bigl(C_y^1(s)-C_y^2(t)\bigr)^2,\quad0\le s,t\le1. $$ Taking partial derivatives with respect to $s$ and $t$ and equating to $0$ we get a system of two equations and two unknowns: $$\begin{align} \bigl(C_x^1(s)-C_x^2(t)\bigr)(C_x^1)'(s)+\bigl(C_y^1(s)-C_y^2(t)\bigr)(C_y^1)'(s)&=0\\ \bigl(C_x^1(s)-C_x^2(t)\bigr)(C_x^2)'(t)+\bigl(C_y^1(s)-C_y^2(t)\bigr)(C_y^2)'(t)&=0 \end{align} $$ You must also consider the possibility that the minimum is achieved at a point where $s$ or $t$ equals $0$ or $1$.

Answer 2

Given a curve $C_1(s) = (x_1(s), y_1(s))$ and a curve $C_2(t) = (x_2(t), y_2(t))$, we want to find the point

$$ (s^*, t^*) := \arg\!\!\!\!\!\!\!\!\!\min\limits_{(s,t) \in [0,1]^2~~~~~~~~~} \!\!\!\!\!\!\!\!\|C_1(s) - C_2(t)\|^2$$

To have a hope of doing this with calculus, it's necessary to assume that the distance function $\|C_1(s) - C_2(t)\|$ is at least locally continuous in $s$ and $t$ (though it's certainly not, in general, continuous) and that it has derivatives in a few places. Then, you can write something like $$z = z(s,t) := \|C_1(s) - C_2(t)\|^2$$ and search for minima in the usual way - look for roots of the partial derivatives, and check the Jacobian determinant of $z$ to verify local minima, $$|J(z)| = \left|\array{\frac{\partial^2 z}{\partial s^2} & \frac{\partial^2 z}{\partial s \partial t}\\ \frac{\partial^2 z}{\partial s \partial t} & \frac{\partial^2 z}{\partial t^2}}\right|$$