Признак сжатия кривой до замыкания ее на саму себя
Решаю задачу численными методами. Имеем замкнутую непересекающуюся внутри кривую сложной формы.
Исходные данные: таблица координат N точек: x,y
Расширяю и сжимаю (плавно) кривую в отдельных ее областях. Иногда при втягивании во внутрь какойто области (локальном сжимании) возникает проблема - она пересекается с другой внутренней областю моей кривой. Сейчас я задачу решаю в лоб -вычисляю расстояния между всеми точками (возможных комбинации N*(N-1)/2 ) Это отьедает колоссальное колво ресурсов. Вопрос: нет ли математического решения узнать, пересекаются внутри области или нет? Требуется ответ: Да/Нет
Ответы (2 шт):
Есть структуры данных, такие как R-tree и kd-tree, специально предназначенные для пространственного поиска. Они иерархически разбивают пространство на прямоугольники, и сложность поиска становится логарифмической.
Я нашел способ существенно сократить объем вычислений.
Так как кривая замкнута, то у каждой точки легко вычисляется признак: выпуклая точка или невыпуклая (простое вычисление по двум соседним точкам).
Выпуклая точка никогда не может явиться причиной замыкания на саму себя изнутри кривой.
Поэтому просто перебираем все невыпуклые точки.