代码之家 › 专栏 › 技术社区 › Xzhsh

简化凹壳

computational-geometry polygon 3d algorithm

2

Xzhsh · 技术社区 · 16 年前

问题:

鉴于 :n与三维k边非凸多边形强相关的点,其中n>>k

发现 :与点的原始几何图形匹配的最佳凹壳

尝试的解决方案:

警告:伪代码

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)

例子:

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

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

产量将是三维点中多边形的顶点。

我的问题是,有没有更好的方法来解决这个问题?上述解决方案的问题是这些点可能会有噪声。此外,将点光栅化为二维,然后执行边缘查找的成本相当高。

任何一个指针都是很好的。提前谢谢

3 回复 | 直到 13 年前

1

2

deinst 16 年前

如果你的凹角不是太尖锐,我可能会尝试做一个三维Delaunay三角点集。边界点的沃罗诺伊区域往往是无限的,或者比内部区域长得多。类似地,边界上与多面体的单个面相关联的单元将倾向于沿与它们相关联的面几乎垂直的方向对齐,因为它们都是长而薄的,它们的长轴将几乎平行并指向多边形之外。有点像伪代码

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.

编辑现在我看到你只想要一个多边形。上述方法是可行的,但最好分两步进行。首先找到多边形所在的平面,做一个点的小样本的最小二乘拟合就足够了。将这些点投影到平面上(这基本上就是您所做的),然后计算二维Delaunay三角剖分以找到边缘点,然后如上所述继续。

2

0

Community Mohan Dere 9 年前

听起来你想计算投影到平面上的3空间点集合的凹壳。对二维情况进行了详细的讨论。 here .

3

0

kiriloff 13 年前

首先,你要为你的网格选择一个表示。在2d中,我使用以下表示实现了一个python凹面外壳算法: half-edge data structure .

然后,算法在二维(你应该适应三维)可以接近 to alpha shape algorithm, by Edelbrunner.