问题标签 [concave-hull]

我正在使用 PCL 1.10（安装 Ubuntu 20.04 和 ROS Noetic 的二进制版本）中的稀疏点云。我的云代表独立的对象，所以我在云中有许多独立的密集集群，我正在尝试使用凹壳按它们的接近程度对它们进行分组。但是，我得到的结果有时是无效的，并且结果可以从视觉上有效转变为无效，只需添加几个点。我将无效定义为其中一些自相交的多边形集，并将不包含所有点的多边形定义为一组。以下是一些在彼此相距几帧内拍摄的结果示例，其中连续帧的不同之处仅在于每帧增加了几个（2 或 3）个点。

我的云是 3D 的，但我将 ConcaveHull 对象明确设置为在 2 维中工作。将我的云投影到 2D 平面上以消除额外的尺寸没有效果，并且我确认多边形的顶点都在 XY 平面上。

上面的第一张图片显然是凹壳的一组无效多边形。上面的第二张图片是在大约 100 毫秒后拍摄的，只增加了几个点。由于黄色的小多边形，它也可能无效，但更接近正确。

我一直在梳理 PCL /surface/include/pcl/surface/impl/concave_hull.hpp 文件试图理解算法。显然，QHull 库被用于计算整个云的凸包，然后 PCL 拥有的代码处理凸包以确定凹多边形或一组多边形。我不知道那里正在实施什么算法，所以没有一些逆向工程就无法评论它。

我的猜测是，在真正的多边形又窄又长的区域中，有某种最近邻检查会在多边形的另一侧抓取一个顶点。您可以通过比较第一张和第二张图像来想象它们找到了相同的顶点，但是在第一帧中，一些不正确的逻辑正在抓取错误的顶点，这导致算法选择关闭多边形，从而导致很长的直线以及螺旋形的错误刻面。

我的计划是尝试更好地理解代码并导出我的数据以尝试其他一些凹壳算法，但为了每个人的利益而修复这个会很好。我的需求是无人值守的操作，所以它必须每次都能正常工作。

我正在寻找有关 PCL 算法的任何信息、其他从事此代码工作或遇到此问题的人的建议，或有关如何更好地满足我的需求的建议。感谢所有输入！

更新：我发现了另一个在幕后利用 QHull 的凹壳库 (concaveman-cpp)，当我自己调用 QHull 但使用 SciPy.spatial 的 QHull 实现时，它也会在我的系统上产生不正确的结果，而 concaveman-cpp 使用它演示应用程序。这导致我调查 QHull 的输出。

在直接执行 QHull 的 C++ 中，我发现当凹壳对我的数据集无效时，当以 PCL 的方式可视化时，来自 QHull 的凸包（即按其 qID 排序顶点）是无效的。我发现使用 Qhull 的 Geomview 输出每次都会产生正确的凸包。进一步的调查表明，QHull 并不总是将其顶点输出为有序集，它也没有声称如此。但是，询问 QHull 的有序输出是可能的，现在我 100% 的时间得到了正确的船体。这并不优雅，因为没有 C++ 接口可以这样做，但是您可以向 QHull 发送“Fx”标志以使其打印有序顶点并将标准输出重定向到字符串缓冲区，然后解析字符串以获取数据。该解决方案在使用也输出数据的其他标志方面不可扩展。有趣的是，

在几乎相同的数据集上运行的 PCL 凸包的两个示例图像，“ok”数据集与“bad”数据集具有相同的点，除了存在于云内部的 2 个点（即不影响包的点多边形）。

更新 2：Scipy 揭示了一种遍历和排序方面以确定有序点的方法。这个概念很简单，但由于 QHull 中疯狂的命名约定，实现有点难以理解。然而，它是针对凸包失效问题的通用解决方案，并导致 concaveman-cpp 产生 100% 良好的凹包。所以现在是时候弄清楚如何将这样的解决方案集成到 PCL 凹壳算法中了。

更新 3：我开始调试 PCL 凹壳代码，发现它发送到 qhull（特别是“d QJ”）的标志正在返回一个无效的凸壳。我发现添加“Fx”标志会导致返回一个有效的凸包，但我仍然必须使用从 SciPy 借来的重新排序代码来可视化它。无论是否对构面重新排序，来自 PCL 的 alpha 形状代码都会产生无意义的输出。我对用于在 PCL 中实现的 alpha 形状算法的 Delaunay 三角形和 Voronoi 中心没有任何了解，所以我认为这对我来说是一个死胡同。我希望这至少可以帮助某人。

更新 4：我得出结论，凹壳故障是与凸壳故障不同的错误。这是从完全相同的数据集（与上述不同的数据）生成的两个图像，其中两个图像之间的唯一区别是将 alpha 值从 0.56（有效）更改为 0.55（自相交船体失败）。在这种情况下，凸包是有效的。

我是编程的初学者，所以我很抱歉我的基本问题。

几周前我通过 vcpkg 管理器安装了 PCL 11.1，现在我意识到我缺少一些头文件。特别是 pcl/surface/concave_hull.h 和更多关于可视化的内容，但这些我现在不会错过太多。

我尝试以不同的方式安装 PCL（v11.1）（使用我在 git 上找到的 exe 文件），我可以在那里看到丢失的文件。然而，当我将此位置添加到 Visual Studio (v16.8.4) 中的其他包含目录时，我得到了 3 个链接器错误。

有谁知道这是为什么以及如何通过 vcpkg 安装完整版本的 PCL 或如何摆脱这些错误？谢谢你。

我有一个 3D 二进制掩码（来自 Dicom 图像），其中有一个对象。我想计算其中物体的总凹表面积和总凸表面积。对于total convex surface area，我使用了这个链接，它在 Matlab 中的代码如下：

对于total concave surface area，我已经看到了这个链接，但我不知道如何alphaShape在 3D 二进制掩码上使用它（ ）：

如果上面的代码是我的答案，如何为我的 3D 二进制掩码设置其输入参数？

否则，如何total concave surface area在 Matlab 中计算 3D 二进制掩码？

所以我有一个应该在多边形内的点（2d）列表，以及应该在多边形外的第二个点列表。我想找到包含“内部”点同时排除“外部”点的多边形。

生成的多边形几乎肯定是凹的。我想尽量减少它的边数，但任何其他合理的标准都可能会这样做。似乎某些从凸包开始，然后从中取出块的方法可能会奏效。

我想知道这是否可以使用 alpha 形状来实现，同时改变 alpha。已经有一个很好的python实现了；https://pypi.org/project/alphashape/ 但我还没有弄清楚我需要如何改变 alpha。

我在这里有一个问题，我真的无法以简单的方式解决。也许有人可以帮助我从不同的角度看待这一点。基本上，我有两个大小相同的x和y矩阵坐标。第一个（掩码）包含只有两个不同值的像素：-1 和 0。第二个（标签）可以包含具有整数值（从 1 到 1000）的像素。

这两个矩阵的表示如下：

• 掩码表示构成不同超像素轮廓的像素：如果 -1 我们在边界上，否则为 0。
• 在标签矩阵中，每个标签代表一个超像素，每个像素都分配给一个超像素标签。

我的目标是结合这两个矩阵，为每个超像素创建相关的凹多边形来提取他的顶点。

到目前为止，我的解决方案是：

1. 创建字典：键是表示超像素的标签，值是包含超像素轮廓像素的数组。
2. 运行 ConvexHull 以查找字典每个键的凸多边形。
3. 对于我找到的每个凸多边形，运行一个算法来检测与凹相关的多边形（https://github.com/sadaszewski/concaveman-cpp）。

不幸的是，我对这个解决方案不够精确，因为结果可能与原始超像素不同。

两个矩阵的简单示例：

标签：

面具：

非常感谢您的帮助！

问题

我正在尝试为 python 中的 3D 点云的 alpha 形状实现 Edelsbrunner 算法，如这篇 SO post中所述。但是，我无法绘制结果。我的球体有一半看起来不错，而另一半则乱码。

我怀疑这可能与我有负坐标的事实有关，但我不确定。

定义

我正在添加这些，以便程序员可以做出贡献而不会被数学所困。这些是简化的定义，并不意味着精确（请随意跳过这部分；有关更多信息，请参阅Alpha 形状和离散微分几何简介）：

• Delaunay 三角剖分： 对于 2D 点集，将点细分为三角形（即“三角剖分”），其中每个三角形的外接圆（即“外接圆”）不包含集合中的其他点。对于 3D 点，将“triangle”替换为“tetrahedron”，将“circumcircle”替换为“circumsphere”。

• 仿射独立： 点的集合，p0, ..., pk使得所有向量vi := pi-p0都是线性独立的（即在 2D 中不共线，在 3D 中不共面）；也称为“一般位置点”

• k-单纯形： k+1 个仿射独立点的凸包；我们称这些点为顶点。

0-单纯形 = 点（由 0+1 = 1 个点组成）
1-单纯形 = 线（由 1+1 = 2 个点组成）
2-单纯形 = 三角形（由 2+1 = 3 个点组成）
3-单纯形 = 四面体（由 3+1 = 4 分组成）

• 面： 任何单纯形，其顶点是另一个单纯形的顶点的子集；即“单纯形的一部分”

• （几何）单纯复形： 单纯形的集合，其中（1）两个单纯形的交点是单纯形，（2）单纯形的每个面都在复合形中；即“一堆单纯形”

• alpha-exposed： 点集中的单纯形，其中半径为 alpha 通过其顶点的圆 (2D) 或球 (3D) 不包含点集中的任何其他点

• alpha 形状： 点集的所有 alpha 暴露单纯形的边界

算法

Edelsbrunner 算法如下：

给定一个点云pts：

1. DT计算点云的 Delaunay 三角剖分
2. 查找 alpha 复形：搜索 Delaunay 三角剖分中的所有单纯形，并且 (a) 如果单纯形周围的任何球为空且半径小于alpha（称为“alpha 测试”），然后将其添加到 alpha 复形
3. 阿尔法复合体的边界是阿尔法形状

代码

输出

点云：

阿尔法形状：

2021 年 9 月 9 日更新

根据@akaszynski，问题确实似乎是独特点和负面点的结合。他通过以下方式解决了这个问题：

但是，如果有人可以进行更深入的调查以确定问题的原因，那将有所帮助。

2021 年 9 月 9 日更新 #2

根据@AndrasDeak，两者都pyvista支持VTK创建 2d 和 3d alpha 形状。该pyvista函数在底层delaunay_3d使用vtkDelaunay3D，它接受一个alpha参数。

（参见vtkDelaunay3D 文档）

我有一大组 2D 点，我已将其下采样为 44x2 numpy 数组（稍后定义的数组）。我试图找到那些实际上是凹壳的点的边界形状。在第二张图片中，我手动标记了我希望获得的近似边界形状。

我已经尝试从这里使用alphashape和 Delauney 三角测量方法，这两种方法都提供了相同的答案。

不幸的是，无论 alpha 参数如何，我似乎都无法实现我所需要的。我尝试了一些手动设置和 alphaoptimize，下面是其中的一些示例。

我对 alphashape 有什么重要的误解吗？文档看起来很清楚，但显然我遗漏了一些东西。

今天是个好日子，

我有一个多点作为几何图形的集群地理数据。我能够使用 geopanda 的方法创建凸包convex_hull。但不知何故，我找不到用于创建 alpha 形状的类似命令。或者一些东西会给我一个给定集群中所有点的紧密边界。

出于演示目的，我将在此处提供代码。该代码从 Open Street Map 下载样本数据，使用 HDBSCAN 方法对点进行聚类，然后为每个聚类创建凸包。

主要问题是关于最后一个命令。我想以类似的方式创建一个 alpha 形状（带有 predifend alpha 参数），我将拥有多边形，就像我在 convex_hull 的情况下一样。

有什么建议么？

我在ST_ConcaveHull函数调用中遇到了这个错误，我不知道如何解决它。

这是我的示例表的内容 ( inte1: text, geom_pol: geometry)

这是我用来获取集群的查询

查询成功完成（target_percent=1找到 2 个集群）。我想要一个更准确的结果，所以我尝试减少target_percent. 我试过用target_percent=0.9/0.8/0.7ecc。并且查询给了我以下错误：

我该如何解决这个错误？

地理信息系统版本："2.5 USE_GEOS=1 USE_PROJ=1 USE_STATS=1"

PostgreSQL 版本："PostgreSQL 11.11, compiled by Visual C++ build 1800, 64-bit"

我已经用 R 库alphahull工作了几天了。当我试图以sf多边形的形式获得结果时，我按照这里的建议使用ahull_track，因为它返回geom_path对象。

但是，当我尝试它时，我遇到了这个问题：

我确实在Github上查看了函数本身的代码，确实我看到它psp在第 8 行调用，但没有任何关于它应该从哪个库加载的参考。

有人知道我错过了什么吗？