2

问题：

给定：与 3d k 边非凸多边形强相关的 n 个点，其中 n >> k

Find：与点的原始几何形状匹配的最佳拟合凹壳

尝试的解决方案：

警告：伪代码

segments = []
for each point in image:
    #segment points into planes via comparing approximate normals
    #actual implementation is more complicated
    findSegment(image,point)
for each segment in image:
    #transform coordinate system to be a 
    #2D-plane perpendicular to the normal of segment
    transform(segment, segment.normal)
    edges = findEdges(segment)
    polygonHull = reconstructPolygon(edges)
    #transform back to original coordinate system
    transform(segment, segment.normal)

例子：

 ___
|   |               |
|    \__    ==>     |   ___
|       |           |__/  /_____
|_______|          /  /   \_
                  /  /_____/
                 /

输入将只是一个高密度点云，它是多边形平面内近似均匀分布的随机点，带有一点噪音。

输出将是 3d 点中多边形的顶点。

我的问题是，有没有更好的方法来解决这个问题？上述解决方案的问题是这些点可能是嘈杂的。此外，将点光栅化为 2d 然后执行边缘查找非常昂贵。

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

4

3 回答 3

2

如果你的凹角不是太尖锐，我可能会尝试对点集进行 3d Delaunay 三角剖分。边界上点的 Voronoi 区域将趋向于无限大或比内部点长得多。类似地，与多面体的单个面相关联的边界上的单元将倾向于在几乎垂直于它们相关联的面的方向上对齐，因为它们都将是长而细的，并且它们的长轴将是几乎平行并指向多边形外。有点像准伪代码

Compute Delaunay triangulation
Collect long thin Voronoi regions
Partition the Voronoi regions into clusters that are nearby and nearly parallel.
Create faces normal to the axes of the Voronoi regions.

编辑 现在我看到你只想要一个多边形。上述方法有效，但最好分两步完成。首先找到多边形所在的平面，对小样本点进行最小二乘拟合可能就足够了。将这些点投影到平面上（这几乎就是您一直在做的事情）然后计算 2d Delaunay 三角剖分以找到边缘点并继续如上。

于 2010-08-10T21:57:06.540 回答
0

听起来您想计算投影到平面上的 3 空间中的一组点的凹壳。此处详细讨论了 2D 情况。

于 2010-08-10T01:39:01.023 回答
0

首先，您要为您的网格选择一个表示。在 2D 中，我使用以下表示实现了 Python 凹壳算法：半边数据结构。

然后，Edelbrunner 的 2D 算法（你应该适应 3D）可以接近alpha 形状算法。

于 2013-05-07T06:33:59.280 回答