问题标签 [concave-hull]

从 GIS 文件（城市地图）中获得一组（2D）点，我需要生成定义该地图（其边界）的“轮廓”的多边形。它的输入参数将是点集和“最大边长”。然后它将输出相应的（可能是非凸的）多边形。

到目前为止，我发现的最佳解决方案是生成 Delaunay 三角形，然后删除比最大边长更长的外部边。在所有外部边缘都比这短之后，我只需删除内部边缘并获得我想要的多边形。问题是，这非常耗时，我想知道是否有更好的方法。

所以我试图翻译这里找到的凹壳算法：http ://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf

（第 65 页）

我已经通读了整篇文章，但我不知道如何实现sortByAngle，而且angle我不确定我应该在其中执行什么方法。这是我到目前为止所拥有的：

我知道这里有很多代码。但我不确定我是否可以展示上下文以及没有它的情况。

其他类：

我想问一个我有但我还没有想出解决方案的想法，我的想法是：

有一组被矩形覆盖的 GPS 坐标点，如何根据其形状连接这些点，当我尝试使用 Quick Hull 连接这些点时，它形成了一个凸面，这不是我的预期结果，我的期望是例如，我们有一组遵循“L”字母形状的点，因此如果我们将它们连接起来，我们可以有一个“L”形状。

我尝试了 voronoi 和 delaunay，但仍然没有得到好的结果！

感谢您帮助我找到一个好的解决方案。

真是受宠若惊！

感谢大家

我有一个定义 3D 对象的表面列表。这些曲面具有以下约束：

• 每个表面都由定义其边界的顶点数组定义
• 表面内没有孔
• 表面不重叠或穿过其他表面
• 包含曲面每条边上的每个顶点
• 所有表面都与至少两个其他表面相邻
• 由这些表面创建的对象可能是凹的

我想获得由这些表面创建的 3D 对象的外壳 - 3D 对象内部没有空白空间
有人知道算法吗？

问题：

.) 我已经可以排除所有边缘仅接触该表面的表面

• 每个表面边是至少 2 个表面的一部分

然而，图像 4 个立方体仅在 1 个边缘相互接触，因此可以在它们之间创建一个不属于任何 3D 对象的表面

.) 获得仅部分船体表面的 3D 对象很容易。但是，如果 3D 对象内部有表面并连接到船体，我如何找到这些表面？

任何指针都会很棒。提前致谢

我有一个像这样的二维布尔数组

这个形状不会有任何洞——即使它有——我会忽略它们。现在我想找到包含我的形状的多边形：

有没有准备好用于这种情况的算法？我找不到任何内容，但我不确定我是否知道此任务的正确搜索词。

我正在寻找一个函数的 OpenCV 实现来找到一组点的凹壳（至于 convexHull 函数）。有人知道吗？

这是一个解释：http ://ubicomp.algoritmi.uminho.pt/local/concavehull.html

先感谢您。

我正在为 Waze（著名的免费 G​​PS 导航器）开发开源 JavaScript 插件，专门用于在线编辑器。这个用户脚本的想法是可以快速选择大型统一彩色地图区域以将它们转换为地标。

到目前为止，我已经成功地在 Photoshop 等图形编辑器中实现了您将称为“Magic Wand”的工具：用户单击地图上的某个位置（例如，在湖或森林上），脚本选择相同颜色覆盖的整个区域并创建一个多边形为地标。

一切都很好，除了我使用凸包算法来获得......好吧......凸包:)那是：连接找到的点云的最外点的多边形。

但众所周知，只有少数地标具有凸面形状，而现实世界中的大多数物体都具有带有凹面区域的折线形状。在上图中，您可以看到该区域几乎没有锋利的边缘，并且右下角的农田被凸包覆盖——这是错误的。

我在谷歌上搜索合适的算法并翻阅数学论文，但仍然没有找到合适的算法。Stackoverflow 上关于凹壳的最受欢迎的问题是指 Alpha 形状和 Delaunay 三角形。虽然我不明白如何使用它以防万一：所有点都相互连接形成一条连续的折线，因此我似乎找不到合适的 alpha-radius 作为半径等于 1 像素的偶数圆并进行 alpha 曝光。

任何关于如何归档构建凹形船体目标的想法将不胜感激！可能是我走错了方向，需要查看位图矢量化算法吗？

我是具有基本 C++ 经验的新 CGAL 用户，试图找到一组点的 3D Alpha 形状。我正在使用ex_alpha_shapes_3示例代码，然后使用保存 CGAL alpha 形状表面网格的说明来可视化结果。一切似乎都正常，但是当我尝试通过替换来更改 alpha 的值时

和

假设第三个变量是 alpha (= 1) 的值并且每​​次都改变这个值，得到的结果没有变化。

更具体地说，在我的一组粒子中，有些粒子与大多数粒子分离，我想使用凹壳或 alpha 形状用单独的体积（类似于图 41.1 ）来表示它们。目前我得到的（使用 Tecplot 进行可视化）是： 如您所见，分离的粒子与其他粒子相连。最后，我还附上了我的代码。对于此事，我将不胜感激。

我正在使用 CGAL 使用ex_alpha_shapes_3 示例创建一组 3D 点的凹壳。接下来，我想知道空间中的点查询是否位于由三角形凹壳面（ex_alpha_shapes_3 代码的输出）创建的曲面内。“多边形中的点”技术应该对此有用。如果有人可以帮助我解决这个问题，我将不胜感激。

我有 20 到 30 个随机生成的 3D 点作为定义多面体的顶点。我曾尝试使用DelaunayTri(points)枚举面并使用叉积的行列式来计算和求和四面体体积，但我不确定它是否适用于非凸面的多面体。

另一种可能的方法是将凹多面体划分为凸多面体（通过检测凸包内的点），但这种不相交划分的算法让我望而却步。

另外，如何绘制这样一个凹形船体？