Для личного проекта мне нужно выяснить, пересекаются ли две кубические кривые Безье. Мне не нужно знать где: мне просто нужно знать, знают ли они. Однако мне нужно сделать это быстро.
Я обыскал это место и нашел несколько ресурсов. В основном здесь есть этот вопрос, на который есть многообещающий ответ.
Итак, после того как я понял, что такое матрица Сильвестра, что такое определитель, что такое результирующий и почему это полезно, я подумал, что понял, как работает решение. Однако реальность требует отличия, и это работает не так хорошо.
Возиться
Я использовал свой графический калькулятор, чтобы нарисовать два пересекающихся сплайна Безье (которые мы назовем 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
После этого я создал функцию C ++ для вычисления определителей матриц с помощью разложения Лапласа:
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.
Это ошибка с моей стороны или с их стороны? Как правильно узнать, пересекаются ли две кубические кривые Безье?
(-P0 + 3*P1 - 3*P2 + P4) * t^3 + 3*(P0 - 2*P1 + P2) * t^2 - 3*(P0 - P1) * t + P0; и два уравнения, которые я показал, - это просто функции для X и Y двух вычитаемых кривых. WolframAlpha подтверждает, что они идентичны. - person zneak schedule 28.10.2010