Как выяснить, пересекаются ли две кубических кривых безье с помощью алгоритма (не перебором)?
Приветствую!
Есть необходимость вычислить, пересекаются ли две кубические кривые Безье на плоскости заданные координатами опорных точек.
Сами точки пересечения и их координаты не важны.
Первым делом отметаю все те, у которых оболочки по опорным точкам не пересекаются.
Но как быть дальше?
Есть какой-либо алгоритм, который бы позволил однозначно ответить пересекаются или нет не используя деление на отрезки?
Алексей Тен: Потому что все математические формулы кривых Безье опираются на параметр t, а в реальных задачах нужно оперировать координатами x и y. Переобразование t -> (x, y) просто и понятно, а вот наоборот нет. Получить по координатам параметр t аналитически - нетривиальная задача, у меня вот не получилось (задача была подобна той, что у автора вопроса). Вот и решают все численно.
dom1n1k: У меня есть подозрение, что деление пополам попросту быстрее и точнее, чем решение по ссылке. Учитывая, что в итоге там всё равно ищут корни уравнения девятой степени численными методами.
Да даже если взять банальные кубические уравнения - они ведь неоднозначны, имеют по нескольку корней. То есть потом еще имеем геморрой с сортировкой корней, какой из них нужный, а какие побочные.
Средний
