連接不相交線段集成簡單多邊形新算法

金輝 劉潤濤

摘?要：針對連接平面上n條線段構(gòu)成簡單多邊形問題，給出了線段集能連接成一個簡單多邊形的一個充分條件。證明了對線段集S的端點(diǎn)進(jìn)行Delaunay三角剖分可以找到端點(diǎn)的最近點(diǎn)或次最近點(diǎn)。以此為根據(jù)，給出了線段加入到簡單多邊形使得到的多邊形總長度最小的方法，進(jìn)而給出了連接給定線段集成一個簡單多邊形的算法。對新算法進(jìn)行了時間復(fù)雜度分析，并給出了算法的正確性證明。通過實例對算法進(jìn)行了對比，表明新算法可以得到更好的結(jié)果。

關(guān)鍵詞：線段集;簡單多邊形;Delaunay三角剖分;四邊形邊長增值

DOI：10.15938/j.jhust.2018.06.025

中圖分類號： TP391.41

文獻(xiàn)標(biāo)志碼： 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?引?言

近些年來，隨著地理信息系統(tǒng)、計算機(jī)輔助設(shè)計、醫(yī)學(xué)或衛(wèi)星圖像數(shù)據(jù)處理等領(lǐng)域的發(fā)展，計算幾何的發(fā)展越來越重要。連接線段構(gòu)成簡單多邊形作為計算幾何中重要問題之一，可用于解決某些實際問題如：居民區(qū)安裝煤氣管道、商業(yè)區(qū)安裝網(wǎng)絡(luò)通信

線路等方面。

研究這個問題的目的在于縮短連接線段總長度之和s′1+s′2+…+s′n，以及降低時間復(fù)雜度，并且可以將線段推廣成矩形、長方體等幾何對象，有針對性地解決一些空間物體無法抽象為點(diǎn)的情況。目前，其相關(guān)文獻(xiàn)較少，只有周培德于2002年提出的一篇，但是文[1]算法的連接線段總長度過長。連接不相交線段集成簡單多邊形應(yīng)用在調(diào)整小區(qū)供暖系統(tǒng)的例子中，不僅可以節(jié)約管道材料，還可以減少溫度流失，故該算法在實際生活中具有重要意義。

1?Delaunay三角剖分

定義1平面點(diǎn)集的三角剖分）平面上有n個點(diǎn)，用互不相交的線段來連接，并且使凸殼內(nèi)的每一個區(qū)域是一個三角形。

定義2Delaunay邊）假設(shè)V是二維實數(shù)域上的有限點(diǎn)集，邊e是由點(diǎn)集中的點(diǎn)作為端點(diǎn)構(gòu)成的封閉線段，E為e的集合。邊e（兩個端點(diǎn)為a，b）若滿足下列條件，則稱之為Delaunay邊：存在一個圓經(jīng)過a，b兩點(diǎn)，圓內(nèi)（圓上最多三個點(diǎn)）不含V中其他端點(diǎn)。

定義3Delaunay三角剖分）如果點(diǎn)集V的一個三角剖分只包含Delaunay邊，那么該三角剖分稱為Delaunay三角剖分。

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

按照文[1]的算法進(jìn)行連接的簡單多邊形如圖14所示，用本文的算法連接的簡單多邊形如圖13所示。

可以看出，根據(jù)周培德先生的算法得出的連接線段長度和為73.20，對比本文算法得到的連接線段長度和為53.04，比周培德先生的算法得到的連接長度少20.16，減少了27.54%。

6?結(jié)?論

本文通過添加Delaunay三角剖分，在連接過程中選取最近點(diǎn)或次最近點(diǎn)進(jìn)行連接，再將線段插入多邊形以及多邊形合并，通過比較計算四邊形邊長增值，根據(jù)增值最小值對連接線段進(jìn)行修改，達(dá)到了縮短多邊形連接總長度的目的。給出了相應(yīng)的算法，證明了本文算法可以正確的將si（i=1，n）的所有端點(diǎn)連接成簡單多邊形，并且連接線段總長度更低。

下一步將探討時間復(fù)雜度更低，連接線段的總長度和更短的算法。

參 考 文 獻(xiàn)：

[1]?周培德?王樹武?李斌.?連接不相交線段成簡單多邊形（鏈）的算法及其實現(xiàn)[J].?計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報?2002?14（6）： 522-525.

[2]?周培德.?平面線段集三角剖分的算法[J].?計算機(jī)工程與科學(xué)?2003?25（1）： 20-22.

[3]?袁小翠?吳祿慎?陳華偉.?Delaunay三角剖分算法改進(jìn)與對比分析[J].?計算機(jī)應(yīng)用與軟件?2016?33（9）：163-166.

[4]?高莉.?改進(jìn)的Delaunay三角剖分算法研究[D].?蘭州：蘭州交通大學(xué)?2015：126-188.

[5]?周培德.?連接兩個多邊形成一條回路的算法[J].?計算機(jī)研究與發(fā)展?1996（11）： 865-868.

[6]?周培德.計算幾何——算法設(shè)計與分析（第2版）[M].?北京： 清華大學(xué)出版社?2005.4： 166-176.

[7]?楊洋?劉學(xué)軍?肖斐.?復(fù)雜多邊形快速融合算法與實現(xiàn)[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ìn)算法[J].?測繪通報?2014（6）：51-54.

[10]范俊甫?馬廷?周成虎，等.?分治法在GIS多邊形快速合并算法中的應(yīng)用及效率提升評價模型[J].?地球信息科學(xué)學(xué)報?2014?16（2）：158-164.

[11]袁翰?李偉波?陳婷婷.?對構(gòu)建Delaunay三角網(wǎng)中凸殼算法的研究與改進(jìn)[J].?計算機(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].?計算機(jī)光盤軟件與應(yīng)用?2013（17）：311-312.

[14]王中輝?閆浩文.?帶約束折線的平面散點(diǎn)集Delaunay三角剖分[J].?測繪與空間地理信息?2011?34（1）：46-47.

[15]許文帥?龍毅?周侗，等.?面向復(fù)雜多邊形合并的視覺鄰近探測與縫合算法[J].?地理與地理信息科學(xué)?2014?30（1）：125-126.

[16]劉潤濤?王三?安曉華.?求平面點(diǎn)集凸殼的一種新算法[J].?計算機(jī)工程與應(yīng)用?2009?45（3）：58-59.

[17]陳正鳴?李春雷.?多邊形鏈求交的改進(jìn)算法[J].?計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報?2004?16（12）： 1713-1718.

（編輯：王?萍）