Как выяснить, пересекаются ли две кубических кривых безье с помощью алгоритма (не перебором)? Приветствую!
Есть необходимость вычислить, пересекаются ли две кубические кривые Безье на плоскости заданные координатами опорных точек.
Сами точки пересечения и их координаты не важны.
Первым делом отметаю все те, у которых оболочки по опорным точкам не пересекаются.
Но как быть дальше?
Есть какой-либо алгоритм, который бы позволил однозначно ответить пересекаются или нет не используя деление на отрезки?

Предыдущий
вопрос Следующий
вопрос

Для проверки пересечения двух кубических кривых Безье на плоскости можно воспользоваться алгоритмом, основанным на вычислении пересечения их уравнений.

Пусть у нас есть две кубические кривые, заданные уравнениями:
C1(t) = P0(1-t)^3 + 3P1t(1-t)^2 + 3P2t^2(1-t) + P3t^3
C2(s) = Q0(1-s)^3 + 3Q1s(1-s)^2 + 3Q2s^2(1-s) + Q3s^3

где P0, P1, P2, P3 - опорные точки первой кривой, Q0, Q1, Q2, Q3 - опорные точки второй кривой, t и s - параметры.

Для определения пересечения кривых необходимо решить систему уравнений:
C1(t) = C2(s)
dC1(t)/dt = dC2(s)/ds

где dC/dt - производная по параметру.

Если данная система имеет хотя бы одно решение, то кривые пересекаются.

Данный метод позволяет определить пересечение двух кривых Безье без разбиения их на отдельные отрезки.