折线链节点标注技术

摘要：

针对传统多边形位置关系计算比较烦琐,以及简单多边形的理论难以拓展到一般多边形的问题,提出标注节点状态的方法.通过定义11种位置来描述折线链上每个节点的状态,再采用“线段端点与线段”和“线段端点与邻折线”的标注方法来实现任意折线链的标注,同时利用两线段分割预处理使相交仅发生在端点处,从而使算法更高效；然后给出折线链基本位置关系的节点特征,并且探讨了三维顶点的标注方法.该方法的标注原理简单、方法实用,算法空间和时间复杂度分别为O(n)和O(n2).实验结果表明,该方法对任意形状的折线链都能实现稳定标注；通过搜索节点状态特征可以求解折线链间的相互关系,还可以实现一般折线链的碰撞检测、相交区域计算以及多边形简单化分解等.

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

所属期刊栏目：24

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家自然科学基金61063030,51105310

在线出版日期：2012-10-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：605-611