一种基于拓扑搜索的三角网求交算法  

Rapid Topological Searching-based Intersection Algorithm of Triangulated Networks

作　　者：尹长林[1] 喻定权[2] 

机构地区：[1]中南大学信息物理学院,长沙410083 [2]长沙市规划信息服务中心,长沙410013

出　　处：《计算机工程与应用》2006年第36期209-211,共3页Computer Engineering and Applications

摘　　要：在地质构模以及各种地下工程设计等三维表达、分析领域,大规模的复杂三角形网的求交计算是三维表面模型建模的一个关键算法。根据三角形网中相邻三角形之间的拓扑邻接关系以及交线的连续性,提出了一种基于拓扑搜索的三角网求交算法。该算法引入空间辅助网格对原始三角网中的三角形进行筛选,并在候选三角形集合中依次追踪、计算构成交线的交线线段,在获得每个交线线段的同时完成了线段之间的连接。实验表明,该算法不仅效率高而且可靠性好。Intersection of large-scale complex triangulated networks is a key algorithm for three dimensional surface modeling in the field of geological modeling and kinds of subsurface engineering design.An intersection algorithm of triangulated networks based on topological searching is proposed according to topological relationship between neighboring triangles and continuity of intersection line,which introduces spatial referenced grid to filter triangles of original triangulated networks,then traces and computes in turn the intersecting segments which compose the intersection line in the set of candidate triangles.Test result shows that the algorithm has good efficiency and reliability.

关 键 词：表面模型 三角网 空间辅助网格 拓扑搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]