Для личного проекта мне нужно выяснить, пересекаются ли две кривые Безье. Мне не нужно знать, где: мне просто нужно знать, делают ли они это. Тем не менее, мне нужно будет сделать это быстро.
Я убираю место, и я нашел несколько ресурсов. В основном, этот вопрос здесь, который дал многообещающий ответ.
Итак, после того, как я понял, что такое матрица Сильвестра, что является determinant, что означает resultant и почему это полезно, я думал, что понял, как работает решение. Однако реальность заставляет различать, и она не работает так хорошо.
Мессинг вокруг
Я использовал свой графический калькулятор, чтобы нарисовать два сплайна Безье (которые мы будем называть B 0 и B 1), которые пересекаются. Их координаты следуют (P 0, P 1, P 2, P 3):
(1, 1) (2, 4) (3, 4) (4, 3)
(3, 5) (3, 6) (0, 1) (3, 1)
Результат следующий: B 0 является "горизонтальной" кривой и B 1 другой:
В соответствии с вышеизложенным ответом на верхний голос я вычитал B 0 в B 1. Это оставило меня с двумя уравнениями (оси X и Y), которые, согласно моему калькулятору, следующие:
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
После этого я создал функцию С++ для вычисления детерминант матриц с помощью Расширение Лапласа:
template<int size>
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;
}
return total;
}
template<>
float determinant<1>(float* matrix)
{
return matrix[0];
}
Кажется, он работает довольно неплохо на относительно маленьких матрицах (2x2, 3x3 и 4x4), поэтому я ожидаю, что он будет работать и с матрицами 6x6. Однако я не проводил обширных тестов, и есть вероятность, что он сломался.
Проблема
Если я правильно понял ответ от другого вопроса, определитель должен быть 0, так как кривые пересекаются. Однако, подавая мою программу матрицу Сильвестра, которую я сделал выше, она -2916.
Это ошибка на моем конце или на их конце? Каков правильный способ выяснить, пересекаются ли две кубические кривые Безье?
