#python #polyline
#python #полилиния
Вопрос:
Рассмотрим следующее…
Задан упорядоченный массив вершин
[ [1.11, 2.22], [4.44, 3.33], [5.55, 6.66] …]
где каждая вершина представляет собой координату x, y, представленную как (x = 11.11, y = 2.22) на плоскости, а массив в целом представляет собой ломаную линию. Какой самый быстрый способ в Python обнаружить самопересечение и удалить «узел» в «завязанной» строке, чтобы в результате получилось следующее.
Ответ №1:
Определение проблемы расплывчато. Было бы полезно понять, что вы определяете как «узел». Я понимаю, что вы хотите: 1. Найти первое и последнее пересечения в полилинии. 2. Возьмите части [Vn, первое пересечение] и [последнее пересечение, V 5] и сформируйте из них полилинию.
Вы могли бы использовать алгоритм Бентли-Оттмана (https://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm ) чтобы обнаружить все пересечения и отсортировать их, затем выполните все остальное.
С наилучшими пожеланиями