二维物体相交检验的线性四叉树方法

在物体的平面布局问题中，判别两个物体是否相交是一个难点，以往的方法数据结构不统一，计算量大，算法复杂，本文首先讨论了二值图象的线性四叉树的表示及其有关术语和性质，然后在此基础上首次提出了二维物体相交检验的线性四叉树方法及其实现的算法，最后进行了算法的时空分析，与以往的方法相经，本文所提方法具有数据结构统一，算法简单，时空效率高等优点。

A Linear Quadtree Method for Intersection Detection between 2D Objects

In a plane layout of objects, it is difficult to detect intersections between objects. In former methods, the data structure is not uniform and the amount of calculation is large and the algorithm is complicated. Firstly, the linear quadtree representing a binary image, as well as the technical terms and features are described in this paper. Secondly, a new algorithm is presented that detects the intersection of an object with the other. Finally the algorithm is analyzed. Compared with former methods, the main features of the method presented in this paper are: (1) Its data structure is uniform and its algorithm is simple. (2) The algorithm is low computation consuming with small storage space.