摘要： 八叉树编码方法是目前计算机图形学、图象处理和CAD/CAM技术中的一种新的方法。由于采用这种方法表示物体后,对物体进行相干性判别和消除隐藏线(面)操作变得容易而越来越引起人们的兴趣。但由于八叉树编码方法占用的内存太多,而且采用的数据结构是一个非线性结构(树状结构),因此不令人满意。而线性八叉树编码方法很好地解决了上面这两个问题。线性八叉树编码方法由Gar-gantini引入,但她没有给出线性八叉树的深入的性质,也没有详细给出算法。 本文引入了一些与线性八叉树有关的概念,给出并证明了线性八叉树的一些性质。最后,作为这些结果的应用,我们提出了由线性八叉树编码方法所表示的物体之间的集合运算的算法。并对这些算法进行了分析。这些算法都具有线性的时间复杂性。

Abstract: Linear Octtrees Encoding was proposed by Gargantini in[1]. It provides the potential of very effieient algorithms for Image Processing and Three Dimension Geometric Modelling. In this Paper, some new properties of Linear Octtrees are introduced. As an application of these properties, we present some algorithms to find the intersection and union of two objects represented by Linear Octtrees, which have Linear Complexity in time and are valuable in Image Processing and Geometric Modelling .