连接不相交线段集成简单多边形新算法

摘要：

针对连接平面上n条线段构成简单多边形问题,给出了线段集能连接成一个简单多边形的一个充分条件.证明了对线段集S的端点进行Delaunay三角剖分可以找到端点的最近点或次最近点.以此为根据,给出了线段加入到简单多边形使得到的多边形总长度最小的方法,进而给出了连接给定线段集成一个简单多边形的算法.对新算法进行了时间复杂度分析,并给出了算法的正确性证明.通过实例对算法进行了对比,表明新算法可以得到更好的结果.

关键词：线段集、简单多边形、Delaunay三角剖分、四边形边长增值

所属期刊栏目：23

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

资助基金：国家自然科学基金11871181

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

页数：共8页

页码：138-145