如何用多个平面包围空间若干个点

sir_chen

现有3维空间中n个点, 如何用多个平面将这些点包围起来,并使得边界上的点到平面的距离不超过阈值d.要求所用的平面个数越少越好,允许部分点在包围平面的外面,但是与平面的距离不能超过阈值d. 我的想法是对于边界上的近似于平面分布的点确定一个区域,然后用最小二乘法确定一个平面.但问题是如何确定这个区域?用怎样的指标可以判定若干个点近似分布在一个平面上,以及如何准确的选取边界区域. 我这里有一些数据,谁能帮我把这些平面找出来. 数据第一个量表示点的总数,后面每一行表示一个点的三个坐标,其中第一个是z,第二个是x,第三个是y

sir_chen

对于这个问题我先提一下我的思路, 也算作为抛砖引玉吧 首先, 设定一个最小误差$varepsilon $, 比如上面的数据可以设$varepsilon =1$，然后按照这个最小误差将整个区间划分为一个个小的正方体区域, 然后逐层扫描, 这样就可以找到数据区域的边界点, 将所有的边界点保存起来, 记其集合为V. 现在设边界平面方程为z=Ax+By+C, 后面可以单独考虑平行于z轴的平面. 通过随机的取V的点, 得到A,B,C的大概范围, 然后将A,B,C各自的范围划分为n等分, 并将其映射到一个3维数组count[n][n][n], 此3维数组3个维度分别表示A,B,C可能的取值, 并将3维数组全部置0. 然后依此从V中取点, 记第i次取的点为$(x_i, y_i, z_i)$, 将其带入平面方程得到: $z_i=Ax_i+By_i+C$, 将其变形为$C=z_i-Ax_i-By_i$, 遍历A, B在区间上所有的取值, 一共$n^2$个, 并求出对应的C, 然后每次将count[A][B][C]加1. 遍历完V中所有的点后, 然后将count中所有的值进行排序, 其值的大小反应了以对应的A,B,C为参数的平面上包含V中的点的个数, 同时还要考虑夹角很小的平面对应的count值可能也很接近, 因此还要对夹角小于某个阈值的平面进行合并(可通过count值作为权重, 取加权平均), 最后剩下的平面就是整个区域的边界平面.

sir_chen

上面的算法时间复杂度为$O(n^2|V|)$, 空间复杂度为$O(n^3)$n为区间划分的大小, |V|为边界点的个数. 但可以采用分步精确的方法, 比如n=512, 可以在第一次取n=8, 这样得到A,B,C的一个初值, 第二次以第一次得到的A,B,C为初值再次进行细分, 再取n=8, 这样就可以得到对应于单独一次取8*8=64的精度, 第三次再取n=8, 这样就得到了8*8*8=512的精度, 而计算量和空间大幅度减小. 如果每次取n=a, 那么一共要取$log_an$次, 这样时间复杂度为$O(a^2log_an|V|)$, 空间复杂度为$O(a^3)$