Что такое определение, алгоритмы и практические решения для вогнутой оболочки? [закрыто]

116

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

Выпуклая оболочка формы определяется как:

В математике выпуклая оболочка или выпуклая оболочка для множества точек X в вещественном векторном пространстве V является минимальным выпуклым множеством, содержащим X ( Википедия )

Википедия хорошо это визуализирует, используя аналогию с резинкой, и есть несколько хороших алгоритмов для ее вычисления .

Вогнутый корпус

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

Вогнутый корпус может быть решением некоторых реальных проблем (например, найти разумную границу города).

введите описание изображения здесь

Мне не удалось найти правильное определение, алгоритм и практическое решение для понятия вогнутой оболочки. Grass Wiki имеют некоторые описания и изображения , и есть коммерческое решение в concavehull.com .

Есть идеи, алгоритмы и ссылки?

Адам Матан
источник
В каком контексте вы хотите создавать вогнутые оболочки / альфа-формы? В PostGIS, ArcMap, веб-карте, вашем собственном программном обеспечении?
Fmark
И PostGIS, и мои собственные скрипты на Python.
Адам Матан
Существует ли C ++ Linux-совместимая версия реализации алгоритма вогнутой оболочки?
Sylv255
Если у вас есть новый вопрос, задайте его, нажав кнопку « Задать вопрос» . Включите ссылку на этот вопрос, если это помогает обеспечить контекст. - Из Обзора
Злой Гений
Библиотека алгоритмов вычислительной геометрии (CGAL) - это библиотека C ++ с альфа-формами. Он имеет загрузку для Linux и лицензирован как GPL / LGPL для версии> = 4.0.
Klewis

Ответы:

57

Как указывает scw , вы хотите реализовать α-формы .

Альфа-формы можно считать обобщением выпуклой оболочки. Они были впервые описаны в 1981 году в:

Эдельсбруннер, Х .; Kirkpatrick, D .; Seidel, R .; «О форме множества точек на плоскости», Теория информации, IEEE Transactions, т.29, № 4, с. 551-559, июль 1983 г.

Реализации с открытым исходным кодом существуют для интересующих вас сред:

PostGIS

Если вы используете стек PostGIS, необязательное расширение расстояния пробега pgRouting предоставляет реализацию в форме альфа. Однако я не уверен, что вы можете изменить параметр альфа.

Использование ниже:

SELECT the_geom AS alpha_shape 
FROM 
  points_as_polygon(
    'SELECT id, ST_X(your_geom) AS x, ST_Y(your_geom) AS y FROM your_table');

питон

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

Имейте в виду, что части CGAL лицензируются в соответствии с QPL, что означает, что если вы распространяете свою программу, связанную с CGAL, вам может потребоваться выпустить ее в соответствии с QPL. Хорошо, чтобы ваш код был закрытым, если вы не распространяете программный код или двоичные файлы.

fmark
источник
Я не могу заставить оболочки Python CGAL компилироваться - кажется, что они не поддерживаются некоторое время и больше не работают с последней версией CGAL.
Конрадле
2
@fmark: Вторая ссылка, которую вы разместили, кажется мертвой.
Радек
1
@fmark Ссылки PostGIS кажутся мертвыми ..
radek
41

Вот то, что вы ищете.

Вы можете скачать и протестировать программу: (в Java, под лицензией GPL)

альтернативный текст

Бумага, представляющая алгоритм там:

Duckham, M., Kulik, L., Worboys, MF, Galton, A. (2008) Эффективная генерация простых многоугольников для характеристики формы множества точек на плоскости. Распознавание образов v41, 3224-3236

жюльен
источник
29

Кажется, это конкретное применение альфа-форм , которые, как я понял, являются более общей формой этой проблемы. R имеет модуль alphahull , который имеет отличную документацию по вычислению альфа-форм . Также проверьте этот подробный фон на альфа-фигурах. Если вы хотите вычислить только выпуклые / вогнутые оболочки, проверьте lasboundary , часть lastools , он хорошо масштабируется и может обрабатывать миллионы входных точек.

Наконец, это интересное приложение альфа-форм от Flickr сделало несколько раундов назад, показывая их полезность для агрегирования сгенерированного пользователем точечного контента:

Альфа-Корпус Техаса от Flickr

SCW
источник
1
OMG источник написан на ФОРТРАНЕ :-)
Адам Матан
Есть пакет clustr, написанный на C ++, если он вам больше подходит; но будьте осторожны с лицензированием на CGAL: github.com/straup/Clustr
scw
2
Хороший пример из реальной жизни.
DavidF
19

Я создал высокоэффективный инструмент под названием [lasboundary] [1,2], который вычисляет вогнутый корпус для LIDAR в формате LAS / LAZ / SHP / ASCII и сохраняет результат в виде векторного полигона в формате ESRI Shapefile или гео. файл с ссылками KML.

Вот пример запуска:

C:\lastools\bin>lasboundary -i SerpentMound.las -o SerpentMound_boundary.shp
reading 3265110 points and computing convex hull for 3265110 points
growing inward towards concave hull (with concavity = 50)
outputting the concave hull
concave hull has 1639 points

Некоторые результаты фотографии здесь .

Мартин Изенбург
источник
10

Вот функция R, которая реализует модель Alpha Hull. На выходе получается объект sp polygon. Пожалуйста, посмотрите пример в шапке. Требуются пакеты sp, alphahull и maptools.

** Обновление (01-15-2018) Произошли многочисленные изменения в результирующих объектах, созданных пакетом alphahull. Поэтому мне нужно было переписать функцию. Я добавил выпуклую функцию к пакету SpaceEco. Однако из-за лицензионных ограничений в пакете alphahull эта функция доступна только в версии для разработчиков на GitHub. Версию для разработки можно установить с помощью:

library(devtools)
install_github("jeffreyevans/spatialEco")

Вот пример использования функций

library(sp)
library(spatialEco)
data(meuse)
 coordinates(meuse) = ~x+y
a <- convexHull(meuse, alpha=100000)
  plot(a)
    points(meuse, pch=19)

Преобразовать полученный SpatialLinesDataFrame в SpatialPolygonsDataFrame

library(sf)
a <- sf::st_as_sf(a) 
a <- sf::st_polygonize(a)
class( a <- as(a, "Spatial") )
  plot(a)

Проверьте несколько значений альфа

par(mfcol=c(2,2))
   for (a in c(500, 1500, 5000, 100000)) {
   ch <- convexHull(meuse, alpha = a)
     plot(ch)
      points(meuse, pch=19)
        title( paste0("alpha=", a))      
   }

различные параметры альфа-канала

Джеффри Эванс
источник
+1 Не могли бы вы объяснить, чем это отличается от пакета альфа-фигур ?
whuber
3
Выходные данные объекта alphahull хранятся в виде матрицы и должны быть приведены к используемому sp-объекту. Я бы посчитал это вспомогательной функцией для создания многоугольника, который можно экспортировать в формат ГИС. Эта функция использует пакет alphahull для создания объекта матрицы оболочки, создает объект sp, а затем разрывает слот многоугольника, чтобы он представлял собой объект Dataframe из многоугольника, состоящий из одной части. В справке по пакету ничего не отображается, но может быть вновь реализовано собственное приведение к объекту класса sp, о котором я не знаю. Если это так, пожалуйста, дайте мне знать, чтобы я мог отключить эту функцию.
Джеффри Эванс
Какой язык программирования?
Адам Матан
Спасибо @JeffreyEvans, мне удалось заставить это работать. Не могли бы вы объяснить параметры? Я посмотрел на связанную бумагу jstatsoft, но она довольно непроницаема.
геоэтерия
9

JTS ( http://tsusiatsoftware.net/jts/main.html ) обеспечивает реализацию выпуклой оболочки. Мартин Дэвис также упомянул, что в работе есть алгоритм Alpha Shape, так что вы можете проверить SVN-репозиторий, чтобы увидеть, работает ли он, если вы этого хотите.

Ян Тертон
источник
Насколько я могу судить, по состоянию на июнь 2012 года реализации вогнутых корпусов и альфа-форм еще не было.
blah238
Все еще ничего в мае 2013 года.
Crescent Fresh
JTS жив? Последняя версия от 19 декабря 2006 года. Vividsolutions.com/jts/JTSHome.htm
angelcervera
попробуй ссылку в ответе
Ian Turton
JTS сейчас на Github и приближается к версии 1.15: github.com/locationtech/jts Хотя, насколько я могу судить, реализация Alpha Shapes, похоже, все еще отсутствует.
Колин Вудбери
7

Вот программа, написанная на C, которая вычисляет выпуклые оболочки, альфа-формы, триангуляции Делоне и объемы Вороного:

  • Халл - Кен Кларксон (2002)

Другой алгоритм выпуклой оболочки с реализациями C и Java находится здесь:

blah238
источник
7

Чтобы добавить к предыдущим ответам на этот пост, по крайней мере, в QGIS 2.6 действительно есть алгоритм вогнутой оболочки

Параметры
Введите точечный слой [vector: point]
поместите описание параметра здесь

Порог (0-1, где 1 эквивалентен выпуклой оболочке) [число]
положить описание параметра здесь
По умолчанию: 0,3

Разрешить отверстия [логическое значение]
положить описание параметра здесь
По умолчанию: True

Разбить многокомпонентную геометрию на одночастную геометрию [логическое значение]
По умолчанию: False

Выходы Вогнутый корпус [вектор]
поместите описание выхода здесь

Использование консоли
processing.runalg ('qgis: concavehull', вход, альфа, дыры, no_multigeometry, выход)

Также в Esri есть инструмент Minimum Bounding Geometry (Управление данными)

Что позволяет выбрать тип геометрии, который включает в себя выпуклый корпус

введите описание изображения здесь

whyzar
источник
3

Чтобы помочь с частью «правильного определения» вашего вопроса; Возможно, вы заглянули на https://en.wikipedia.org/wiki/Convex_hull и получили то, что вполне можно считать «правильным» определением, но обнаружили, что его не хватает, поэтому, возможно, более «полезное» определение:

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

Это полезно, потому что, учитывая точку, вы можете построить линию через нее и проверить, построена ли эта линия, пересекающая сегменты корпуса.

  • Нет пересечения, точка не находится в корпусе.
  • Одно пересечение точки находится на корпусе.
  • Два пересечения точка находится внутри корпуса
  • Прямая не может пересекать выпуклый корпус более двух раз
user29206
источник
2
опера задает