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

• 作 者: 张田文 李仲荣
• 机 构: 哈尔滨工业大学计算机科学系,哈尔滨工业大学计算机科学系哈尔滨150006,哈尔滨150006
• 出 处: 计算机学报
• 发表日期: 1991年3期
• 关键词: 八元树 连通分量 标号 客体群 计数 Linear octtrees adjacency graph incidence matrix topology-

本文提出二种算法分别标号和计数线性八元树表示的三维客体群的连通分量.这些操作典型地需要检查线性八元树中诸八分体在三个主方向上的面邻接对.根据这些邻接对,可以建造在计算机中用关联矩阵表示的邻接图.连通分量标号和计数是在关联矩阵上分别执行相应的操作而完成的.连通分量标号的执行时间是O(n+m·logm),而连通分量计数需要O(n)时间,其中m和n分别是线性八元树中八分体和邻接对的数目.