Нахождение граничных координат из заданного набора точечных координат?

18

Учитывая набор координат, Как мы находим граничные координаты.
набор координат <== Рисунок 1.
Учитывая координаты в указанном выше наборе, Как я могу получить координаты на красной границе? Граница - это многоугольник, который образован входными координатами для вершин таким образом, что он максимизирует площадь.

Я работаю над приложением, которое ищет свойства в пределах «х» миль от города . Что у меня есть:

  1. Координаты всех свойств.
  2. Набор координат для каждого города (у меня есть одна координата для каждого почтового индекса. И поскольку большинство городов имеют более одного почтового индекса, у каждого города есть набор координат)

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

изогнутый многоугольник <== Рисунок 2

Что мне нужно, это алгоритм, чтобы придумать набор координат для границы. Алгоритм, который позволит мне придумать граничные координаты для рисунка 1 .

algorithm polygon-creation vertices convex-hull Хаджа Минхаджуддин
источник
1
возможный дубликат вогнутой оболочки: определение, алгоритмы и практические решения
Ян Тертон
4
Нет, не дубликат, это выпуклый корпус, а не вогнутый
Никлас Авен
1
Вы ищете код, теоретические ссылки или решения в конкретных существующих программных средах?
WolfOdrade
1
@ Khaja Нет, вы не хотите максимизировать площадь, вы хотите минимизировать ее среди всех выпуклых многоугольников, содержащих точки. (Единственный способ максимизировать область - использовать весь мир в качестве содержащего многоугольника.)
whuber
1
@whuber Да, теперь я понимаю, что вы имеете в виду, я хочу выпуклый многоугольник с минимальной площадью. Моя конечная цель - поиск близости. Мы хотим, чтобы наш поиск близости работал: В данном городе (выпуклый корпус), если мы ищем дома (у каждого дома есть координата) в пределах «х» миль, это должно дать мне все дома, которые находятся внутри выпуклый корпус или находятся на ортогональном расстоянии менее «х» миль
Хаджа Минхаджуддин

Ответы:

21

Есть много алгоритмов для решения этой проблемы ( Википедия "Convex_hull_algorithms" ):

  • Упаковка подарков ака Jarvis march - O (nh): один из самых простых алгоритмов. Он имеет O (nh) временную сложность, где n - количество точек в наборе, а h - количество точек в корпусе. В худшем случае сложность O (n2).
  • Сканирование Грэма - O (n log n): немного более сложный, но гораздо более эффективный алгоритм. Если точки уже отсортированы по одной из координат или по углу к фиксированному вектору, то алгоритм занимает O (n) времени. [ псевдокод ]
  • QuickHull: Как и алгоритм быстрой сортировки, он имеет ожидаемую временную сложность O (n log n), но в худшем случае может выродиться в O (nh) = O (n2). [ иллюстрированное описание ]
  • Разделяй и властвуй - O (n log n): Этот алгоритм также применим к трехмерному случаю.
  • Монотонная цепь - O (n log n): вариант сканирования Грэма, который сортирует точки лексикографически по их координатам. Когда входные данные уже отсортированы, алгоритм занимает O (n) времени.
  • Алгоритм инкрементальной выпуклой оболочки - O (n log n)
  • Брак до завоевания - O (n log h): оптимальный алгоритм, чувствительный к выходу.
  • Алгоритм Чана - O (n log h): более простой оптимальный алгоритм, чувствительный к выходу.
Подземье
источник
Спасибо за то, что перечислили эти @underdark ... какой из них вы выбрали?
Марин
3

То, что вы хотите, это выпуклая оболочка. В PostGIS есть функция (на самом деле GEOS), которая дает вам выпуклую оболочку ST_ConvexHull (геометрия) .

В википедии много информации о вогнутых корпусах.

Никлас Авен
источник
1

Если вы хотите, чтобы алгоритм делал это (а не пакеты, которые могут это сделать), то я бы подумал, что вам нужно будет триангулировать данные; или в основном определить линию от каждой точки до каждой другой точки. Затем, начиная с (скажем) точки с наибольшим значением Y, проследите маршрут вокруг внешней стороны, следующей за соединенной линией с наименьшим внешним углом / подшипником.

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

Кстати, FME будет делать то же самое с преобразователями ConvexHullAccumulator или ConvexHullReplacer!

Марк Ирландия
источник
1

Если вам интересно посмотреть на существующий алгоритм, реализованный в коде, у NetTopologySuite есть алгоритм для этого

Смотрите ConvexHull.cs

Кстати, NTS и куча других библиотек обернуты в классный проект под названием DotSpatial, который можно найти здесь.

WolfOdrade
источник