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.

user31238
  • 119
  • 1
  • 2
  • 3

3 Answers3

8

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.

Uwe Raabe
  • 45,288
  • 3
  • 82
  • 130
  • 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 '08 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 '08 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).

tfinniga
  • 6,693
  • 3
  • 32
  • 37
  • 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 '12 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.

Stephen Deken
  • 3,665
  • 26
  • 31
  • 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 '08 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 '18 at 14:21