凹形船体的定义，算法和实用解决方案是什么？

#1 楼

正如scw所指出的，您想要实现α形状。

字母形状可以看作凸包的概括。最早在1981年将它们描述为：


Edelsbrunner，H. Kirkpatrick，D .;
Seidel，R .; ，“关于平面中点集的形状”，信息，
，IEEE期刊，第29卷，第4期，第551-559页，1983年7月


存在您感兴趣的环境的开源实现：

PostGIS

如果使用的是PostGIS堆栈，则pgRouting的可选的Driving Distance扩展程序公开了alpha形状的实现。但是，我不确定是否可以更改alpha参数。

用法如下：

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

可能有很多python模块可以使用。我听说过有关CGAL（C ++计算几何库）的好消息。 Python包装器存在于CGAL的各个部分，包括将CGAL的alpha形状实现公开给Python。

请注意，CGAL的某些部分已获得QPL的许可，这意味着，如果分发与CGAL链接的程序，则可能需要根据QPL发行它。如果不重新分发程序代码或二进制文件，则可以保留代码专有性。

#2 楼

您正在寻找的是这里。

您可以下载并测试程序：
（在Java中，已获得GPL许可）



提出算法的论文在这里：

Duckham，M.，Kulik，L.，Worboys，MF，Galton，A.（2008）有效生成简单的多边形以表征形状平面上的一组点。模式识别v41、3224-3236

#3 楼

这似乎是alpha形状的一种特定应用，从我阅读的该问题的更一般形式中可以看出。 R具有alphahull模块，该模块具有有关计算alpha形状的出色文档。还要检查有关alpha形状的详细背景。如果您只想计算凸/凹包，请检查lastbounds的lasboundary，它可以很好地缩放并可以处理数百万个输入点。四舍五入前，显示了其用于汇总用户生成的点内容的实用程序：

#4 楼

PostGIS干线中有ST_ConcaveHull的实现。
http://postgis.net/docs/ST_ConcaveHull.html

#5 楼

我创建了一个称为lasboundary（1,2）的高效工具，该工具以LAS / LAZ / SHP / ASCII格式为LIDAR计算凹面船体，并将结果存储为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

一些结果图片在这里。

#6 楼

这是实现Alpha Hull模型的R函数。输出是一个sp多边形对象。请参见标题中的示例。它需要sp，alphahull和maptools软件包。

**更新（01-15-2018）
alphahull软件包产生的结果对象发生了许多更改。因此，我需要重写该函数。我在spatialEco包中添加了凸凸函数。但是，由于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)

测试多个Alpha值

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))      
   }

#7 楼

关于R实现Alpha-Shapes，有一篇有关“将Alpha-Shapes转换为SP对象”的文章。

它基于alphahull，sp和spgrass6
http：//casoilresource.lawr.ucdavis。 edu / drupal / node / 919

#8 楼

JTS（https://github.com/locationtech/jts）提供了Convex Hull实现。马丁·戴维斯（Martin Davies）还提到了正在使用的Alpha Shape算法，因此您可能需要检查SVN存储库以查看它是否在其中。

#9 楼

谈到JTS，您可以使用Geoscript来操纵JTS库。
http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html上有关凸包的文章。
GeoScript实现可在JavaScript，Python，Scala和Groovy中使用。
官方网站：http://geoscript.org

#10 楼

这是一个用C语言编写的程序，用于计算凸包，alpha形状，Delauney三角剖分和Voronoi体积：



船体-Ken Clarkson（2002）

另一种具有C和Java实现的凸包算法在这里：


凸包（2D）-C语言中的计算几何，约瑟夫·奥洛克（1998）

#11 楼

为了补充本文的以前的答案，至少从QGIS 2.6开始，它具有凹壳算法。


参数参数描述在这里

阈值（0-1，其中1与凸包相等）[数字]
参数描述在这里
默认值：0.3

允许孔[boolean]
在此处放置参数说明
默认值：True

将多部分几何图形拆分为单部分几何图形[boolean]

默认值：False

输出
凹包[vector]
将输出描述放在此处

控制台用法
processing.runalg（'qgis：concavehull'，输入，alpha，孔，no_multigeometry，输出）

Esri还有一个工具“最小边界几何（数据管理）”

您可以选择哪种几何类型，其中包括凸包

#12 楼

有一个适用于GRASS GIS 7的新插件：v.concave.hull。另请参见
http://grasswiki.osgeo.org/wiki/Create_concave_hull

#13 楼

帮助您解决问题的“正确定义”部分；您可能已经看过
https://en.wikipedia.org/wiki/Convex_hull并得到了可以被认为是“适当”定义的内容，但发现它缺乏，因此也许更“有用”的定义是：

对于凸包内的每个点，到不在该壳内的任何点的直线只会与该壳相交一次。

这很有用，因为给定一个点，您可以通过它构造一条线，并测试与船体的线段相交的构造线。


没有交点，该点不在壳体内。
一个交点，该点在壳体上。
两个交点，该点在壳体内。
直线与凸包的相交不能超过两次