Как найти точки пересечения между двумя кубическими кривыми Безье
У меня есть две кривые Безье,
кривая 1: - 1-я опорная точка (a1x, a1y), 1-я контрольная точка (c1x, c1y), 2-я контрольная точка (c2x, c2y), 2-я опорная точка (a2x, a2y)
кривая 2: - 1-я опорная точка (a3x,a3y), 1-я контрольная точка (c2x,c3y), 2-я контрольная точка (c4x,c4y), 2-я опорная точка (a4x,a4y)
Теперь я хочу найти точки пересечения между этими двумя кривыми Безье;
Как это сделать? Любой справочный документ с алгоритмом поможет мне;
3 ответа
Существует два основных способа найти пересечение кривой Безье:
- Рекурсивное подразделение использует свойство выпуклой оболочки кривых Безье и обычно проверяет пересечение ограничивающих прямоугольников своих сегментов кривой.
Код из книги Graphics Gems IV с некоторым текстовым описанием
- Численное решение системы двух кубических уравнений. Это приводит к полиномиальному уравнению 9-го порядка и может иметь 9 действительных корней (случай двух S-образных кривых). Обратите внимание, что решение численно нестабильно.
Код JS и интерактивная демонстрация И я думаю, что код C++ может быть в библиотеке Geometric Tools WildMagic.
Кривая Безье - это уравнение кубического полинома. Если вы хотите найти, когда две кубики пересекаются, то вы хотите найти, когда две кубики равны, т.е.
a1 x3 + b1 x2 + c1 x + d1 = a2 x3 + b2 x2 + c2 x + d2
Тогда это то же самое, что найти корни кубического уравнения
(a1 - a2) x3 + (b1 - b2) x2 + (c1 - c2) x + (d1 - d2) = 0
Подобные кубические уравнения могут быть решены аналитически, см., Например , метод Кардано. В качестве альтернативы, такой метод, как Ньютон-Рафсон, может быть использован для итерации к решению. Остерегайтесь, однако, кубики могут иметь до 3 очков, где они равны нулю.
Если допускается некоторая аппроксимация, вы можете преобразовать кривые Безье в множество маленьких прямых линий, а затем вычислить пересечения между их парами, сгенерированными из обеих кривых. Это гораздо проще решить, так как вам нужно решать только линейные уравнения и может обеспечить достаточную производительность и точность для вашего случая использования.
Мое предложение может быть не очень эффективным, но оно может работать. Вы можете попытаться сравнить расстояния между точками двух кривых, и ближайшие две точки будут вашими перекрестными "точками".