S01E15:多于三个点的最佳平面

S01E15:多于三个点的最佳平面

IOS小彩虹2021-08-26 1:27:55150A+A-

说明

在三维空间中,3 个点确定一个平面(3 个点不能共线)。但是有时,我们会得到多个点,进而反推出平面位置,比如知道了多边形的顶点,但是位置精确度不够高,需要根据所有点集找到最接近的平面时。

几何

最简单的算法就是,我们把这些点每三个当成一个三角形,逐个计算法线,最后把得到的法线加起来,平均一下,就得到了“最佳”法线。当然,这个计算还可以化简,化简过程我们不再推算,根据书本,化简后的公式如下:

代码

static func estimatePlane(from points:[simd_float3]) -> Plane? {
    if points.count < 3 {
        return nil
    }
    var normal = simd_float3.zero
    var position = simd_float3.zero
    // 从最后一个顶点开始,避免在循环中做 if 判断
    var second = points.last!
    for vector in points {
        // 边向量乘积相加
        normal.x += (second.z + vector.z) * (second.y - vector.y)
        normal.y += (second.x + vector.x) * (second.z - vector.z)
        normal.z += (second.y + vector.y) * (second.x - vector.x)
        // 下一个顶点
        second = vector
        
        // 顺便求中心点,做为平面位置
        position += (vector / Float(points.count))
    }
    if length_squared(normal) < 0.0001 {
        return nil
    }
    normal = normalize(normal)
    return Plane(position: position, normal: normal)
}

其他

这个方法好处是计算简单效率高,复杂度只需要 O(n)。缺点是对顶点的排列顺序有要求:顶点顺时针排列时,得到法线为正。当点集的排列呈下面这种交叉时,正负方向的法线会互相抵消,当完全对称时,法线为 0。 那么这种情况应该怎么处理呢?很难处理,一种是调整数组顺序再算一遍(但不保证一定管用),另一种只能是更换其他算法,比如最小二乘法等。

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1
本网站由 提供CDN/云存储服务

联系我们