金辉 刘润涛

摘 要：针对连接平面上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]算法的连接线段总长度过长。连接不相交线段集成简单多边形应用在调整小区供暖系统的例子中，不仅可以节约管道材料，还可以减少温度流失，故该算法在实际生活中具有重要意义。……