Для личного проекта мне нужно выяснить, пересекаются ли две кубические кривые Безье. Мне не нужно знать, где: мне просто нужно знать, если они делают. Тем не менее, мне нужно сделать это быстро.

Я копался в этом месте и нашел несколько ресурсов. В основном, естьэтот вопрос здесь это было многообещающим ответом.

Итак, после того, как я понял, что такоеМатрица Сильвестрачто такоеопределительчто такоерезультирующий а такжепочему это полезноЯ подумал, что понял, как работает решение. Однако реальность требует отличия, и это не так хорошо работает.

Возиться

Я использовал свой графический калькулятор для рисования двух сплайнов Безье (которые мы назовем B0 и Б1) которые пересекаются. Их координаты следующие (P0, П1, П2, П3):

(1, 1) (2, 4) (3, 4) (4, 3)
(3, 5) (3, 6) (0, 1) (3, 1)

Результат следующий, B0 будучи «горизонтальной» кривой и B1 другой:

Следуя указаниям вышеупомянутого вопроса с наибольшим количеством голосов, я вычел B0 в Б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.

Это ошибка с моей стороны или с их стороны? Как правильно определить, пересекаются ли две кубические кривые Безье?