折线链节点标注技术  

Node-Labeling Techniques of Poly-Line Chains

作　　者：张云辉[1] 高满屯[1] 吴建军[1] 张燕[2] 

机构地区：[1]西北工业大学机电学院,西安710072 [2]华为技术有限公司西安研究所,西安710075

出　　处：《计算机辅助设计与图形学学报》2012年第5期605-611,共7页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家自然科学基金(61063030;51105310)

摘　　要：针对传统多边形位置关系计算比较烦琐,以及简单多边形的理论难以拓展到一般多边形的问题,提出标注节点状态的方法.通过定义11种位置来描述折线链上每个节点的状态,再采用"线段端点与线段"和"线段端点与邻折线"的标注方法来实现任意折线链的标注,同时利用两线段分割预处理使相交仅发生在端点处,从而使算法更高效;然后给出折线链基本位置关系的节点特征,并且探讨了三维顶点的标注方法.该方法的标注原理简单、方法实用,算法空间和时间复杂度分别为O(n)和O(n2).实验结果表明,该方法对任意形状的折线链都能实现稳定标注;通过搜索节点状态特征可以求解折线链间的相互关系,还可以实现一般折线链的碰撞检测、相交区域计算以及多边形简单化分解等.In order to more easily calculate polygonal position relationships and expand the theories of simple polygon to general polygon,a method labeling node status is proposed.Firstly,11 positions are defined to describe each node status of poly-line chains.And both methods of ＂an endpoint of a line with another line＂ and ＂an endpoint of a line with an adjoining line＂ are used to label any poly-line chain.Meanwhile,after the division pretreatments of two lines,which make the intersections only occurring at endpoints,are implemented,the labeling method become more efficient.Finally,the node-labeling features of basic position relationships between two poly-line chains are given,and the labeling of three-dimensional vertex is also preliminarily studied.The labeling method is simple in principle,but practical in application,whose space and time complexities of algorithm are O（n） and O（n2） respectively.Experimental results show that this method can stably label poly-line chain with arbitrary shapes;and through searching the labeling feature of each node,the position relationships among poly-line chains can be solved,furthermore,some applications can be achieved for general poly-line chains,such as collision detection,intersection computing and polygonal simplification decomposition,etc.

关 键 词：计算几何 邻折线 一般多边形 相交 多边形简单化 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]