金輝 劉潤(rùn)濤

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

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

DOI：10.15938/j.jhust.2018.06.025

中圖分類號(hào)： TP391.41

文獻(xiàn)標(biāo)志碼： A

文章編號(hào)： 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?引?言

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

線路等方面。

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

1?Delaunay三角剖分

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

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

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

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

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

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

6?結(jié)?論

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

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

參 考 文 獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

（編輯：王?萍）