摘要
本文提出二种算法分别标号和计数线性八元树表示的三维客体群的连通分量.这些操作典型地需要检查线性八元树中诸八分体在三个主方向上的面邻接对.根据这些邻接对,可以建造在计算机中用关联矩阵表示的邻接图.连通分量标号和计数是在关联矩阵上分别执行相应的操作而完成的.连通分量标号的执行时间是O(n+m·logm),而连通分量计数需要O(n)时间,其中m和n分别是线性八元树中八分体和邻接对的数目.
Two algorithms are presented for labeling and counting the connected components of 3-D objects represented by a linear octtree. These operations typically require the inspection of surface adjacency pairs of octants in three principal directions. According to the adjacency pairs, the adjacency graph corresponding to the linear octtree can be constructed, which is expressed by the incidence matrix in computer. Connected component labeling and counting are carried out by the particular operations on the incidence matrix and their time complexities are O(n + m·logm) and O(n) respectively, where m is the number of octants and n that of the adjacency pairs in the linear octtree.
出处
《计算机学报》
EI
CSCD
北大核心
1991年第3期177-184,共8页
Chinese Journal of Computers
关键词
八元树
连通分量
标号
客体群
计数
Linear octtrees, adjacency graph, incidence matrix, topology-preserving shrinking.
