11

I'm trying to find a way to calculate the intersection between a b-spline and a straight line. So far Google hasn't been much help.

3 Answers 3

9

A pure mathematical approach:

  • Transform the spline and the line so that the line lies on the X axis.
  • Calculate the points on the spline where Y = 0 (depends on the order of the spline).
  • Transform these points back to your original cordinate system.

If this is the way you are going I can work out the necessary formulas.

2
  • I like the approach, but how do you solve for when the spline's Y = 0? Is there a way other than evaluating the spline segments and trying to approximate it?
    – Herms
    Oct 24, 2008 at 17:29
  • 1
    Depending on the order of the spline there are existing solutions to the spline equations (at least up to cubic splines). The formulas tend to get really awkward and they are not guaranteed to be low in numerical errors. As I said: a pure mathematical approach.
    – Uwe Raabe
    Oct 24, 2008 at 18:43
8

The most efficient algorithm that I've heard of is called Bezier clipping.

Here's a book chapter on curve and spline intersection (pdf).

1
  • 1
    I have had success implementing a solution from this source, specifically looking at section 7.3, since polynomial root finding for bezier and B Spline functions is easy.
    – J Collins
    Jul 26, 2012 at 15:56
6

Your best approach might be to break down your spline into individual line segments and test each line segment for intersection with the line. The spline may intersect the line in more than one point, so you'll also have to decide which one you're interested in.

2
  • I agree, this is the usually recommended method. It's usually more efficient if you do this iteratively, refining the line segments where you find an intersection until you get the desired resolution.
    – Kena
    Oct 24, 2008 at 16:56
  • Won't this miss some intersections, especially those that intersect a curvy part of the spline twice without intersecting with the approximation-line-segment?
    – bukwyrm
    Sep 26, 2018 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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