For a personal project, I'd need to find out if two cubic Bézier curves intersect. I don't need to know where: I just need to know if they do. However, I'd need to do it fast.
I've been scavenging the place and I found several resources. Mostly, there's this question here that had a promising answer.
So after I figured what is a Sylvester matrix, what is a determinant, what is a resultant and why it's useful, I thought I figured how the solution works. However, reality begs to differ, and it doesn't work so well.
(1, 1) (2, 4) (3, 4) (4, 3)
(3, 5) (3, 6) (0, 1) (3, 1)
x = 9t^3 - 9t^2 - 3t + 2
y = 9t^3 - 9t^2 - 6t + 4
9 -9 -3 2 0 0
0 9 -9 -3 2 0
0 0 9 -9 -3 2
9 -9 -6 4 0 0
0 9 -9 -6 4 0
0 0 9 -9 -6 4
float determinant(float* matrix)
float total = 0;
float sign = 1;
float temporaryMatrix[(size - 1) * (size - 1)];
for (int i = 0; i < size; i++)
if (matrix[i] != 0)
for (int j = 1; j < size; j++)
float* targetOffset = temporaryMatrix + (j - 1) * (size - 1);
float* sourceOffset = matrix + j * size;
int firstCopySize = i * sizeof *matrix;
int secondCopySize = (size - i - 1) * sizeof *matrix;
memcpy(targetOffset, sourceOffset, firstCopySize);
memcpy(targetOffset + i, sourceOffset + i + 1, secondCopySize);
float subdeterminant = determinant<size - 1>(temporaryMatrix);
total += matrix[i] * subdeterminant * sign;
sign *= -1;
float determinant<1>(float* matrix)
Although they don't explain the algorithm they actually use there, except to say that it's from p. 137 of "The Metafont Book", it appears that the key to it is two important properties of Bezier curves (which are explained elsewhere on that site though I can't find the page right now):
With these two properties and an algorithm for intersecting polygons, you can recurse to arbitrary precision:
This will be fast if the curves don't intersect -- is that the usual case?
[EDIT] It looks like the algorithm for splitting a Bezier curve in two is called de Casteljau's algorithm.