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

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

Проблема в следующем:

  1. У вас есть List координат (точки x и y), образующие замкнутый многоугольник. Этот список гарантированно образует многоугольник с точками, упорядоченными по часовой стрелке.
  2. Вам дается Set координат (точки x и y), которые взяты из 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 для рисования фигур. Нарисованные формы сглаживаются с помощью кривых Безье, что приводит к «изогнутым краям». После рисования фигур (путем опускания точек) пользователи могут редактировать форму. Мы хотим определить начальную и конечную точки, используя точки, которые они изменяют (образует Set выше), чтобы мы могли «сгладить» только затронутую область.


java algorithm jts math geometry
person Abubakr    schedule 27.05.2016    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Преобразуйте свой набор в отсортированный список, объедините этот список с его копией, где каждый элемент добавлен с числом вершин многоугольника 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)
person MBo    schedule 27.05.2016
comment
Цифры в списках соответствуют номерам точек, верно? - person Abubakr; 27.05.2016
comment
Отлично, большое спасибо. Кажется, это отлично работает. Если вы не возражаете, можете ли вы объяснить «математику» этого подхода? Почему это работает? - person Abubakr; 27.05.2016
comment
Необходимо правильно обработать циклическую последовательность с возможным переходом через ноль. Простой способ - удвоить набор данных. - person MBo; 27.05.2016
comment
Отлично, спасибо. Я объединил ваш ответ с ответом Джейкоба, чтобы мой код работал отлично. Для моего конкретного случая использования я просто забочусь о начальной и конечной точках, поэтому простое использование отсортированного набора, а также сравнение первого и последнего кажется более эффективным, чем объединение списка, что было бы лучше, если бы мы хотели все точки (я понимаю, что сформулировал мой вопрос плохо). - person Abubakr; 27.05.2016

arrow_upward
1
arrow_downward

Итак, у нас есть Set, и мы должны пройти этот набор в порядке индекса в List.

конвертировать ISet = [Index(i, List) for i in Set]

следующая сортировка ISet

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

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

person Jacob    schedule 27.05.2016
comment
Под расстояниями вы имеете в виду разницу между двумя парами? - person Abubakr; 27.05.2016
comment
Отлично, спасибо. Я использовал приведенный выше ответ MBo, чтобы создать свой код, но использовал ваш простой трюк, просто сравнив (последний, первый), чтобы избавиться от необходимости копировать набор. - person Abubakr; 27.05.2016