Как выяснить, пересекаются ли две кубических кривых безье с помощью алгоритма (не перебором)?

Question

[Pavel K]

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

Comments

[Lynn «Кофеман»]

Быстрый поиск говорит, что таки методом деления пополам
pomax.github.io/bezierinfo/#curveintersection
stackoverflow.com/a/4041286/1016033

Answer 1

[GavriKos]

По уравнениям кривой?
alex-black.ru/article.php?content=114

Comments

[Lynn «Кофеман»]

Интересно, почему все идут по пути деления пополам?…

[dom1n1k]

Алексей Тен: Потому что все математические формулы кривых Безье опираются на параметр t, а в реальных задачах нужно оперировать координатами x и y. Переобразование t -> (x, y) просто и понятно, а вот наоборот нет. Получить по координатам параметр t аналитически - нетривиальная задача, у меня вот не получилось (задача была подобна той, что у автора вопроса). Вот и решают все численно.

[Pavel K]

dom1n1k: если найти пересечение просто отрезка и безье ещё можно, то вот безье и безье упирается в полином 9той степени =)

[Lynn «Кофеман»]

dom1n1k: У меня есть подозрение, что деление пополам попросту быстрее и точнее, чем решение по ссылке. Учитывая, что в итоге там всё равно ищут корни уравнения девятой степени численными методами.

[GavriKos]

Алексей Тен По ссылке есть и деление пополам. Первым методом. Ну и точность и скорость зависят только от одного - от погрешности приближения к прямой.

[dom1n1k]

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