我有一个在2D情况下工作的算法给你。这是棘手的，但可以把它推广到3D空间。基本思想是从一个最小曲面（2D中的三角形或3D中的四面体）开始，并在遍历点阵列时分割每个边（面）。

2D算法（python.完整源代码/演示请点击此处：（第10页）
**编辑：**此演示看起来很有趣：http://pastebin.com/K0WpMyA3

def surface(pts):
center = pt_center(pts)
tx = -center[0]
ty = -center[1]
pts = translate_pts(pts, (tx, ty))

# tricky part: initialization

# initialize edges such that you have a triangle with the origin inside of it

# in 3D, this will be a tetrahedron.

ptA, ptB, ptC = get_center_triangle(pts)
print ptA, ptB, ptC

# tracking edges we've already included (triangles in 3D)

edges = [(ptA, ptB), (ptB, ptC), (ptC, ptA)]

# loop over all other points

pts.remove(ptA)
pts.remove(ptB)
pts.remove(ptC)
for pt in pts:
    ptA = (0,0)
    ptB = (0,0)
    # find the edge that this point will be splitting
    for (ptA, ptB) in edges:
        if crossz(ptA, pt) > 0 and crossz(pt, ptB) > 0:
            break
    edges.remove((ptA, ptB))
    edges.append((ptA, pt))
    edges.append((pt, ptB))

# translate everything back

edges = [((ptA[0] - tx, ptA[1] - ty), (ptB[0] - tx, ptB[1] - ty)) for (ptA, ptB) in edges]
return edges

结果：

概化为3D

• 而不是边，而是三角形。
• 初始化是围绕原点的四面体
• 查找分割面包括投影一个三角形，并检查pt是否在该三角形的内部
• 分割涉及添加3个新面，而2D是2个新边
• 我需要小心面对的方向（在我的二维代码，我很容易能够保证A-〉B将CCW方向）

根据点云的大小和速度要求，您可能需要更聪明地使用数据结构，以便更快地添加/删除。

3D船体（用于3D表面z = f（x，y）的凸包算法）。
然后，对于每个最大面上的点，搜索云上最近的点，并重新三角化该面以包括该点。
重复上述步骤，直到根据每个剩余面与最近云点的最大距离或最大剩余面的尺寸（长度/面积？）确定“足够接近”为止

我会考虑一个度量函数f（x，y，z），该函数返回三维空间中任意点的标量值。构造此函数时应考虑给定点是否（x，y，z）是云的“内部”或“外部”。例如，这可以是（x，y，z）到云中的每个点，或者它可以是（x，y，z）的某个邻域内的多个云点。函数的选择将影响最终结果。
有了这个f（x，y，z），你可以使用marching cubes algorithm来执行镶嵌，基本上是为某个值构造一个f（x，y，z）的等值面。

听起来你正在寻找“concave hull“。这提供了一个围绕一组点的“合理”边界，“合理”意味着将设置拟合到给定的容差。它不是像船体那样的几何属性，而是对许多“真实的世界”问题的很好的近似，比如在城市周围找到一个紧密拟合的边界。
您可以在Point Cloud Library中找到一个实现。