Алгоритм построения схемы

Мне задали эту задачу моей женой, так что это главный приоритет: -)

У меня есть набор пунктов (на самом деле Нортингс и Истенинг, но это не имеет особого значения). Я хочу взять эти точки и создать набор векторов, которые представляют контур, поэтому я могу строить сюжет на земле Google.

Итак, что-то вроде:

  #                       #
           #             #       #
#             #    #
      #   #

            #

Давал бы:

  #-----------------------#--
 /                            \ --#
#                  #------------/
 \-----#         /
         \     /
            #

Возможное решение, с которым я столкнулся, состоит в том, чтобы вычислить векторы между каждой точкой и отбросить каждый вектор, который перекрывается другим вектором. Я еще не реализовал это (не совсем уверен, как), но я подумал, есть ли другие способы.

Алгоритм должен запускаться только пару раз, поэтому, если он занимает час за ход и гаджеты ОЗУ, это не проблема.

Ответы

Ответ 1

Формулировка потенциальных полигонов

Кажется, что вы ищете многоугольник таким образом, чтобы

  • все его вершины находятся в вашем наборе точек
  • содержит каждую точку вашего набора точек

Это определяет допустимый набор полигонов-кандидатов по отношению к вашему набору точек.

Выпуклая оболочка?

Одной объективной функцией может быть "Среди этих полигонов выберите один с минимальным числом вершин". Это будет выпуклый корпус вашего точечного набора. Другие ответы касаются этого подхода, поэтому я больше не буду говорить об этом.

Что-то еще...

Но это не единственная целевая функция, которую вы могли бы выбрать. Например, вместо этого вы можете иметь компромисс между меньшим количеством вершин, имеющим меньшую общую площадь и имеющим менее острые углы в вершинах. Я не знаю каких-либо существующих алгоритмов для этой проблемы, но это определенно интересный.

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

Например, это:

enter image description here

Стало бы это, потянув край по верхней части:

enter image description here

Этот второй многоугольник может быть более "естественным" для набора точек, хотя это не выпуклая оболочка набора точек.

Ответ 2

Вероятно, вы ищете выпуклую оболочку очков; существует множество алгоритмов для нахождения этого.

Ответ 3

Здесь - это библиотека для обнаружения выпуклой оболочки с code.google.com

Здесь - это библиотека github для одной и той же вещи, но с использованием Jarvis Match Выпуклый алгоритм корпуса.

Надеюсь, они помогут!