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

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

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

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

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

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

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

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

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

Как указывает 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. Хорошо, чтобы ваш код был закрытым, если вы не распространяете программный код или двоичные файлы.

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

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

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

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

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

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

Существует реализация ST_ConcaveHull в магистрали PostGIS. http://postgis.net/docs/ST_ConcaveHull.html

Я создал высокоэффективный инструмент под названием [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

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

О реализации R Alpha-Shapes есть статья о «Преобразовании Alpha-Shapes в объекты SP»

Он основан на альфа-корпусе, sp и spgrass6 http://casoilresource.lawr.ucdavis.edu/drupal/node/919

Вот функция 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))      
   }

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

Говоря о JTS, вы можете использовать Geoscript для управления библиотекой JTS. http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html для статьи о выпуклой оболочке. Реализации GeoScript доступны в JavaScript, Python, Scala и Groovy. Официальный сайт: http://geoscript.org

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

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

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

• Выпуклая оболочка (2D) - Вычислительная геометрия в Си , Джозеф О'Рурк (1998)

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

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

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

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

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

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

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

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

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

Доступно новое дополнение для GRASS GIS 7: v.concave.hull . Смотрите также http://grasswiki.osgeo.org/wiki/Create_concave_hull

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

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

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

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