Curve-Line Intersection

[cbrunschen]

The current text fairly simply reduces this problem to

first we translate/rotate both the line and curve together, in such a way that the line coincides with the x-axis [...] the problem of finding intersections between a curve and a line has now become the problem of performing root finding on our translated/rotated curve, as we already covered in the section on finding extremities.

However, https://www.particleincell.com/2013/cubic-line-intersection/ gives a simple solution that does not require translations or rotations, but directly constructs a polynomial, by starting from the polynomial form of the curve, p(t) = b3 t^3 + b2 t^2 + b1 t + b0 <=> x(t) = b3.x t^3 + b2.x t^2 + b1.x t * b0.x and analogously for y(t).

The line's equation is of course a x + b y + c == 0. Put x(t) and y(t) into the equation for the line and expand x(t) and y(t) and then gather all the t^1, t^2, t and constant terms together and you get

   t^3 * (a * b3.x + b * b3.y) 
 + t^2 * (a * b2.x + b * b2.y) 
 +   t * (a * b1.x + b * b1.y) 
 +       (a * b0.x + b * b0.y) + c 
 == 0

This polynomial that can be fed into Cardano's algorithm and produce the t values where the line and the curve intersect.

The same can of course be done for a Quadratic curve.

[Pomax]

Right, but we're also programming, and while that solution works, it's also more expensive to run. That said, it's probably worth adding as a way to find the solution solution, but it's basically a worse solution for computers (even if on paper it's more elegant).

[cbrunschen]

Would you care to explain what leads you to conclude that this is more expensive to run, and a worse solution for computers? Because to me, it doesn't immediately seem that way.

I don't think the sketched approach necessarily has to be particularly a lot slower / more expensive to run, plus I think this may have some accuracy advantages.

Both approaches require finding the roots of cubic function, so that is going to take the same amount of time; any difference in expense is going to be in the calculation of the coefficients to feed into the root-finding function.

The current align-to-the-x-axis approach requires one atan2() call, as well as a sin() and and cos(), in order to create the affine transformation that is then applied to each of the points to align the curve to the x axis. The sketched approach uses additions/subtractions and multiplications – possibly a few more of them than in the current approach, but it seems like that expense may be balanced by the lack of calls to (usually fairly expensive) trigonometric functions.

This would really have to be benchmarked, and I'm guessing this might differ depending on the choice of language / runtime environment.

I actually wrote and ran a rudimentary benchmark program in C, and the sketched approach was consistently faster (by a factor of about 1.7, taking about 60% of the time) compared to the current approach on my laptop (a 2013 Macbook Pro running Mac OS X 10.13, using LLVM 10.0 – I know, not exactly state of the art, but it is what I use at the moment). This certainly appears to give at least one counterexample to the claim that the sketched approach is more expensive to run, though I am by no means going to conclude that it is always going to be faster – just that it doesn't seem to necessarily always be slower.

The sketched approach may also have an accuracy advantage. While any floating-point calculations may generate an inexact result, if you stick with additions/subtractions and multiplications, there's a fairly wide range of inputs where the results will be exact. However the atan2(), sin() and cos() trigonometric functions will pretty much always produce something that is an approximation – if for no other reason that there's a need to roundtrip the angles through some multiples of PI, which of course cannot be represented exactly.

Consider for example any curves and lines with integer coordinates within +- 2^24 of the origin, where the line is neither horizontal nor vertical.

In the current approach, both the angle, its sin() and cos() are going to be non-integer, non-exact approximations, and thus so will the coordinates of the axis-aligned curve, creating the first small error; this error is then increased trying to find the roots of the already-slightly-erroneous cubic function.

With the sketched approach, all the differences, sums and products are going to involve integers within the 53-bit mantissa of a double, and can thus be represented exactly, with zero error - and the first approximations happen and thus the first errors are introduced in the process of finding the roots of the cubic function.

So while both approaches will of course produce an approximation as part of finding the roots of the cubic function, having less of an error in the inputs to the root finding may produce a more accurate result for the 't' value because there are fewer steps along the calculation where an error has been introduced.