2
$\begingroup$

Given a set of three-dimensional quadratic Bézier curves.

I'm looking for some analytical solution to find the nearest curve to an arbitrary point in space.

Example

I already have a brute force solution with the calculation of the closest point on each curve and selection one with the minimum distance. But this algorithm requires a lot of computational resources.

$\endgroup$
  • $\begingroup$ If you put boxes around all of your curves, take the centre-points of the boxes, and order them, then calculate the distance to the curve with the smallest centre-point distance, you have a lower bound on the smallest distance. You can now exclude all boxes which have all of their corners more than this distance from the target point. Then continue in the same way. $\endgroup$ – J.J. Green May 7 at 12:29
1
$\begingroup$

Too long to comment.

The square of the distance from a point $P$ to a point on a quadratic Bezier curve (parametrized by $t$) is a quartic in $t$. So, choose a Bezier curve and determine this quartic polynomial function. The minima $t^*$ in the range $[0,1]$ can lie at one of the critical points (gradient equal to zero) or the boundaries $0$ or $1$. The points at which the gradient vanishes are all roots of the cubic polynomial obtained by differentiating the quartic. One can then use Cordano's formula (https://en.wikipedia.org/wiki/Cubic_equation) to find a closed form for the roots. Choose all the real roots within $[0,1]$ and evaluate the quartic at these points. Similarly, evaluate the quartic at $0$ and $1$. Finally, choose a point which yields the minimum value.

Do the above for each Bezier curve and choose the one with the lowest minimum value.

Hope this helps.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

It sounds like you already have a way to calculate the distance from a point to a Bézier curve, and you’d just like to speed things up by avoiding doing this calculation for every curve in your collection.

The way to do this is as outlined in the comment from @J.J Green -— you need to enclose each curve in some simple shape for which distance calculations are easy. Then, for a given curve, if the distance to its enclosing shape is larger than your current minimum, you don’t need to bother calculating distance to that curve itself.

Suitable enclosing shapes For quadratic Bézier curves are spheres, axis-aligned bounding boxes, or triangles

| cite | improve this answer | |
$\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.