sir_chen 发表于 2010-11-4 13:50:58

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

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

sir_chen 发表于 2011-2-17 10:50:51

对于这个问题我先提一下我的思路, 也算作为抛砖引玉吧
首先, 设定一个最小误差varepsilon , 比如上面的数据可以设varepsilon =1,然后按照这个最小误差将整个区间划分为一个个小的正方体区域, 然后逐层扫描, 这样就可以找到数据区域的边界点, 将所有的边界点保存起来, 记其集合为V.
现在设边界平面方程为z=Ax+By+C, 后面可以单独考虑平行于z轴的平面. 通过随机的取V的点, 得到A,B,C的大概范围, 然后将A,B,C各自的范围划分为n等分, 并将其映射到一个3维数组count, 此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加1.
遍历完V中所有的点后, 然后将count中所有的值进行排序, 其值的大小反应了以对应的A,B,C为参数的平面上包含V中的点的个数, 同时还要考虑夹角很小的平面对应的count值可能也很接近, 因此还要对夹角小于某个阈值的平面进行合并(可通过count值作为权重, 取加权平均), 最后剩下的平面就是整个区域的边界平面.

sir_chen 发表于 2011-2-17 11:04:54

上面的算法时间复杂度为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)
页: [1]
查看完整版本: 如何用多个平面包围空间若干个点