线性八元树表示的三维客体群的连通分量标号和计数  

CONNECTED COMPONENT LABELING AND COUNTING OF 3-D OBJECTS REPRESENTED BY LINEAR OCTTREES

作　　者：张田文[1] 李仲荣[1] 

机构地区：[1]哈尔滨工业大学计算机科学系,哈尔滨150006

出　　处：《计算机学报》1991年第3期177-184,共8页Chinese Journal of Computers

摘　　要：本文提出二种算法分别标号和计数线性八元树表示的三维客体群的连通分量.这些操作典型地需要检查线性八元树中诸八分体在三个主方向上的面邻接对.根据这些邻接对,可以建造在计算机中用关联矩阵表示的邻接图.连通分量标号和计数是在关联矩阵上分别执行相应的操作而完成的.连通分量标号的执行时间是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.

关 键 词：八元树 连通分量 标号 客体群 计数 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]