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

金辉 刘润涛

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

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

DOI：10.15938/j.jhust.2018.06.025

中图分类号： TP391.41

文献标志码： A

文章编号： 1007-2683（2018）06-0138-08

Abstract：For the problem of how to link a set of segments to a simple polygon with the shortest whole length a sufficient condition that a given set of segments can be joined into a simple polygon is given. It is proved that the nearest point or second nearest point of the end point can be obtained in Delaunay triangulation for the end points of a set of segments S. Based on this result the method of joining a segment into a polygon is given for getting the polygon with the shortest length. Then a new algorithm for joining a set of segments into a simple polygon with shorter whole length is presented. The analysis is done on the time complexity for new algorithm. The correctness of new algorithm is proved. The comparison and analysis are done for the new algorithm to show that better result can be obtained with the new algorithm.

Keywords：set of segments; simple polygon; Delaunay triangulation; the enlargement of quadrilateral length

0 引 言

近些年來，随着地理信息系统、计算机辅助设计、医学或卫星图像数据处理等领域的发展，计算几何的发展越来越重要。连接线段构成简单多边形作为计算几何中重要问题之一，可用于解决某些实际问题如：居民区安装煤气管道、商业区安装网络通信

线路等方面。

研究这个问题的目的在于缩短连接线段总长度之和s′1+s′2+…+s′n，以及降低时间复杂度，并且可以将线段推广成矩形、长方体等几何对象，有针对性地解决一些空间物体无法抽象为点的情况。目前，其相关文献较少，只有周培德于2002年提出的一篇，但是文[1]算法的连接线段总长度过长。连接不相交线段集成简单多边形应用在调整小区供暖系统的例子中，不仅可以节约管道材料，还可以减少温度流失，故该算法在实际生活中具有重要意义。

1 Delaunay三角剖分

定义1平面点集的三角剖分）平面上有n个点，用互不相交的线段来连接，并且使凸壳内的每一个区域是一个三角形。

定义2Delaunay边）假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段，E为e的集合。边e（两个端点为a，b）若满足下列条件，则称之为Delaunay边：存在一个圆经过a，b两点，圆内（圆上最多三个点）不含V中其他端点。

定义3Delaunay三角剖分）如果点集V的一个三角剖分只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。

图1所示的是Delaunay三角剖分。

按照文[1]的算法进行连接的简单多边形如图14所示，用本文的算法连接的简单多边形如图13所示。

可以看出，根据周培德先生的算法得出的连接线段长度和为73.20，对比本文算法得到的连接线段长度和为53.04，比周培德先生的算法得到的连接长度少20.16，减少了27.54%。

6 结 论

本文通过添加Delaunay三角剖分，在连接过程中选取最近点或次最近点进行连接，再将线段插入多边形以及多边形合并，通过比较计算四边形边长增值，根据增值最小值对连接线段进行修改，达到了缩短多边形连接总长度的目的。给出了相应的算法，证明了本文算法可以正确的将si（i=1，n）的所有端点连接成简单多边形，并且连接线段总长度更低。

下一步将探讨时间复杂度更低，连接线段的总长度和更短的算法。

参 考 文 献：

[1] 周培德 王树武 李斌. 连接不相交线段成简单多边形（链）的算法及其实现[J]. 计算机辅助设计与图形学学报 2002 14（6）： 522-525.

[2] 周培德. 平面线段集三角剖分的算法[J]. 计算机工程与科学 2003 25（1）： 20-22.

[3] 袁小翠 吴禄慎 陈华伟. Delaunay三角剖分算法改进与对比分析[J]. 计算机应用与软件 2016 33（9）：163-166.

[4] 高莉. 改进的Delaunay三角剖分算法研究[D]. 兰州：兰州交通大学 2015：126-188.

[5] 周培德. 连接两个多边形成一条回路的算法[J]. 计算机研究与发展 1996（11）： 865-868.

[6] 周培德.计算几何——算法设计与分析（第2版）[M]. 北京： 清华大学出版社 2005.4： 166-176.

[7] 杨洋 刘学军 肖斐. 复杂多边形快速融合算法与实现[J]. 地理空间信息 2016 14（3）：52-55.

[8] SHEWCHUK J R. Delaunay Refinement Algorithms for Triangular Mesh Generation[J]. Computational Geometry Theory & Applications 2014 47（7）：741-778.

[9] 余代俊 蒲朝旭 朱逍賢. 一种Delaunay三角剖分的改进算法[J]. 测绘通报 2014（6）：51-54.

[10]范俊甫 马廷 周成虎，等. 分治法在GIS多边形快速合并算法中的应用及效率提升评价模型[J]. 地球信息科学学报 2014 16（2）：158-164.

[11]袁翰 李伟波 陈婷婷. 对构建Delaunay三角网中凸壳算法的研究与改进[J]. 计算机工程 2007 33（7）：70-72.

[12]FERNANDO de GOES MEMARI Pooran MULLEN Patrick. Weighted Triangulations for Geometry Processing[J]. ACM Transactions on Graphics 2014 33（3）：1-13.

[13]李源 李永钢. 基于扫描线的线段求交算法[J]. 计算机光盘软件与应用 2013（17）：311-312.

[14]王中辉 闫浩文. 带约束折线的平面散点集Delaunay三角剖分[J]. 测绘与空间地理信息 2011 34（1）：46-47.

[15]许文帅 龙毅 周侗，等. 面向复杂多边形合并的视觉邻近探测与缝合算法[J]. 地理与地理信息科学 2014 30（1）：125-126.

[16]刘润涛 王三 安晓华. 求平面点集凸壳的一种新算法[J]. 计算机工程与应用 2009 45（3）：58-59.

[17]陈正鸣 李春雷. 多边形链求交的改进算法[J]. 计算机辅助设计与图形学学报 2004 16（12）： 1713-1718.

（编辑：王 萍）