Определение наилучших начальных и конечных точек для отрезка на многоугольнике

У меня проблемы с поиском лучшего способа решить следующую проблему. Я опробовал несколько методов их решения, но я всегда сталкиваюсь с некоторыми крайними случаями.

Проблема заключается в следующем:

  1. У тебя есть List координат (точки x и y), образующих замкнутый многоугольник. Этот список гарантированно сформирует многоугольник с точками, упорядоченными по часовой стрелке.
  2. Вам дают Set координаты (точки х и у), которые из List координат.
  3. Вы должны выяснить начальную и конечную точки сформированной линии, используя все точки в приведенном выше Set,

У меня проблема в том, что я не могу понять, как найти "лучшие" начальные и конечные точки. Для многих сценариев вы можете выбрать первую и последнюю точку (используя индексы List), чтобы сформировать начальную и конечную точки, однако это может привести к линии, которая длиннее, чем должна быть.

Например, допустим, у нас есть следующий многоугольник:0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 0И следующее Set координаты нашего отрезка должны содержать: 0, 7, 3,

Если мы найдем минимальный и максимальный индексы, мы получим index(0), index(7)так что мы можем сформировать линию 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, которая является допустимой строкой, но она длиннее, чем должна быть. Лучший сегмент линии будет 7 -> 0 -> 1 -> 2 -> 3,

Как я могу найти лучший (самый короткий, который содержит все точки в Set) линейный отрезок эффективным способом?

Для контекста: я работаю над приложением, которое использует JTS Geometries для рисования фигур. Рисованные фигуры сглаживаются с использованием кривых Безье, в результате чего получаются "изогнутые края". После рисования фигур (путем удаления точек) пользователи могут редактировать фигуру. Мы хотим выяснить начальную и конечную точки, используя точки, которые они изменяют (формирует Set выше), поэтому мы можем "сгладить" только пораженную область.

Источник

2 ответа

Решение

Преобразуйте ваш набор в отсортированный список, объедините этот список с его копией, где каждый элемент добавлен с количеством вершин многоугольника N, затем найдите самый длинный пустой прогон (разность соседей) в этом двойном списке. Затем получите подсписок нужной длины, преобразуйте его в непрерывный диапазон (но возьмите элементы по модулю N)

(0,3,7) + (0+8,3+8,7+8) = (0,3,7,8,11,15)

Максимальная разница составляет 7-3, поэтому подсписок в лучшем случае начинается с 7, это

 (7%8 .. 11%8) = (7,0,1,2,3)
Источник

Так что у нас есть Set и нам нужно пройти этот набор в порядке индекса в List,

перерабатывать ISet знак равно [Index(i, List) for i in Set]

следующий вид ISet

для пар последовательных предметов в ISet и пара (последняя, ​​первая) вычисляет расстояния для этой пары.

оштрафовал пару на максимальные расстояния. Тогда лучший конец и начало этой пары.

Источник
Другие вопросы по тегам