平面內(nèi)可相交直線序列的遍歷算法研究

任　重

（河南檢察職業(yè)學(xué)院，河南　鄭州　451191）

?

平面內(nèi)可相交直線序列的遍歷算法研究

任重

（河南檢察職業(yè)學(xué)院，河南鄭州451191）

摘要：平面內(nèi)可享交直線的算法是幾何學(xué)中一個(gè)經(jīng)典課題，文章結(jié)合國(guó)內(nèi)外的研究現(xiàn)狀，提出了幾種切實(shí)可行的算法，及運(yùn)用平面內(nèi)兩點(diǎn)和直線的位置關(guān)系、兩條直線位置關(guān)系算法、對(duì)稱點(diǎn)算法、凸包算法等。同對(duì)上述計(jì)算方法進(jìn)行研究和推導(dǎo)，最終得出結(jié)論。

關(guān)鍵詞：對(duì)稱點(diǎn)；相交直線；科學(xué)算法

自20世紀(jì)70年代，由于空間區(qū)域研究的需要，幾何學(xué)誕生。幾何學(xué)最早是由歐洲數(shù)學(xué)家歐幾里得創(chuàng)造的，幾何最早是用來(lái)丈量土地。在現(xiàn)代，幾何學(xué)普遍應(yīng)用于交通路線圖的規(guī)劃、網(wǎng)絡(luò)大數(shù)據(jù)分析、旅行路線安排、GPS導(dǎo)航等領(lǐng)域。通過(guò)對(duì)大數(shù)據(jù)信息的分析，算出路程的最短距離，其核心是解ESP問(wèn)題。

在現(xiàn)實(shí)生活當(dāng)中最短路程問(wèn)題隨處可見(jiàn)，例如，一個(gè)學(xué)生上課、吃飯?jiān)俚綄嬍?，需要每天?lái)回重復(fù)走到這幾個(gè)地點(diǎn)，這個(gè)學(xué)生可以有很多路可選，那么，怎么走那條路路程最近呢？由于這個(gè)學(xué)生每天都會(huì)走，所以他必然懂得走那條路是最近的，然而如果將這三點(diǎn)換成3個(gè)國(guó)家呢？那恐怕就需要大數(shù)據(jù)的支持，采用平面內(nèi)可相交直線序列的算法進(jìn)行科學(xué)的計(jì)算，并找出相似的路程方可找到最短距離。

1　國(guó)內(nèi)外研究現(xiàn)狀

針對(duì)平面圖的算法而言，國(guó)際上Dijkstra 和Floyd是應(yīng)用最普遍的兩種算法。但是這兩種方法也有其自身局限性，就是只能解決點(diǎn)與點(diǎn)之間的最短路線問(wèn)題。而本文所介紹的ESP問(wèn)題的算法不局限于點(diǎn)，好包括直線和線段。傳統(tǒng)的算法已經(jīng)不能滿足現(xiàn)階段的計(jì)算。

針對(duì)簡(jiǎn)單多邊形算法問(wèn)題，1984年提出Funnel算法，其基本思路是：首先對(duì)給定的簡(jiǎn)單多邊形三角剖析，經(jīng)過(guò)計(jì)算分析，招到遠(yuǎn)點(diǎn)P到達(dá)Q的對(duì)角線，以此找到最短路徑。

論文的組織結(jié)構(gòu)

本文根據(jù)想要研究的內(nèi)容，將其分成了6章進(jìn)行討論。第一章：研究現(xiàn)狀。

這一章主要是對(duì)平面內(nèi)直線能夠相交的最近路徑進(jìn)行了討論，并對(duì)其意義和背景進(jìn)行了闡述，還分析了國(guó)內(nèi)和國(guó)外在這個(gè)問(wèn)題上的研究，從而將本文的組織結(jié)構(gòu)以及研究?jī)?nèi)容引導(dǎo)出來(lái)。

第二章：相關(guān)基本算法以及基礎(chǔ)知識(shí)。

這一章主要是在研究中需要通過(guò)什么樣的基礎(chǔ)知識(shí)進(jìn)行了闡述，并討論了相關(guān)的概念，還分析了一些比較經(jīng)典的算法，給予了可相交直線序列的問(wèn)題一些理論基礎(chǔ)。

第三章：可相交直線序列的遍歷以及算法。

這一章主要是對(duì)可相交直線序列的最近路線的思路做出了闡述，并對(duì)其提出凸多邊形的構(gòu)造，證明了其包含凸多邊形的構(gòu)造，這使得可相交直線的問(wèn)題有了解決方法。通過(guò)這些基礎(chǔ)，將幾種算法進(jìn)行對(duì)比分析，找出其最短路徑的算法。

第四章：算法的設(shè)計(jì)以及實(shí)現(xiàn)。

這一章主要按照實(shí)際的操作，給出一些比較詳細(xì)的算法，通過(guò)偽代碼描述這些算法，最終將其實(shí)現(xiàn)。

第五章：驗(yàn)證算法并分析其結(jié)果。

這一章重點(diǎn)對(duì)實(shí)際運(yùn)行的結(jié)果進(jìn)行了分析，通過(guò)隨機(jī)的一種序列當(dāng)做測(cè)試數(shù)據(jù)，利用分析法去驗(yàn)證其求解算法，并給出一定的曲線方程。

第六章：結(jié)論。

這一章主要是總結(jié)，將文章的結(jié)論表明，并描述一些應(yīng)該加以改進(jìn)的問(wèn)題。

2　相關(guān)基本算法以及基礎(chǔ)知識(shí)

2.1計(jì)算幾何學(xué)的概念

在20世紀(jì)70年代，就出現(xiàn)了計(jì)算幾何學(xué)，這在計(jì)算機(jī)科學(xué)當(dāng)中，是非常重要的一個(gè)分支，它的起源是根據(jù)對(duì)算法的分析和設(shè)計(jì)，在慢慢深入的研究中，其研究成果也慢慢的從最開(kāi)始的外形發(fā)展到了模式識(shí)別、統(tǒng)計(jì)分析以及地理數(shù)據(jù)等很多地方。在現(xiàn)如今的大規(guī)模集成電路、機(jī)器人技術(shù)、數(shù)學(xué)領(lǐng)域以及工程當(dāng)中，都已經(jīng)開(kāi)始廣泛使用。

2.2計(jì)算幾何學(xué)的算法簡(jiǎn)介

針對(duì)本文研究的平面可相交序列的遍歷算法，在計(jì)算幾何學(xué)中，rubber-band算法與貪婪算法較能針對(duì)性的提供計(jì)算依據(jù)。其他算法如在某些程度上也能為本文研究做出一些貢獻(xiàn)。

首先，圍繞平面上兩條直線的位置關(guān)系判定，采用直線斜率的求取，得出兩條直線平行或者相交狀態(tài)。

其次，對(duì)于平面點(diǎn)集的凸包的求解，主要有20世紀(jì)70年代出現(xiàn)的卷包裹法與graham算法。前者是出現(xiàn)較早的解決凸包問(wèn)題的基礎(chǔ)算法，后者是在平面點(diǎn)集凸包問(wèn)題上的最優(yōu)解決算法。在卷包裹的實(shí)際演算過(guò)程中，在一個(gè)點(diǎn)集中取坐標(biāo)最小的點(diǎn)，即凸包的某個(gè)頂點(diǎn)。之后做一條過(guò)該點(diǎn)的直線并讓直線繞頂點(diǎn)逆時(shí)針旋轉(zhuǎn)。

rubber-band算法是俗稱的橡皮筋算法，他可以被形象的描述為在起點(diǎn)，和終點(diǎn)相互連接的皮筋。皮筋在繃直狀態(tài)下就是最短路徑。euclidiean最短路徑問(wèn)題的求解的過(guò)程中該種算法的應(yīng)用非常形象直觀。Rubber-band算法的具體算法流程以程序判斷圖示意為：開(kāi)始→初始路徑的長(zhǎng)度計(jì)算→專門(mén)針對(duì)路徑點(diǎn)集合進(jìn)行處理→得出處理結(jié)果后，計(jì)算兩次路徑長(zhǎng)度之差并與精度標(biāo)準(zhǔn)對(duì)比→如果求差結(jié)果大于精度則重新開(kāi)始路徑點(diǎn)集合的處理步驟。反之基于整個(gè)路徑點(diǎn)得出最短路徑。

貪婪算法被稱為登山法，其進(jìn)行原理一般如同登山一樣的步步為營(yíng)。逐步的將全局的問(wèn)題轉(zhuǎn)化為小部分的問(wèn)題，并保證局部實(shí)現(xiàn)最優(yōu)化解決方案，當(dāng)一部分出現(xiàn)無(wú)解或者不能進(jìn)行時(shí)，全部算法過(guò)程就會(huì)停止。其特點(diǎn)就是簡(jiǎn)單。便捷。并能同時(shí)進(jìn)行。貪婪算法在求解某些問(wèn)題上具有自身的優(yōu)越性，諸如拓?fù)渑判騿?wèn)題，背包問(wèn)題以及本文中多次涉及到的路徑最短問(wèn)題。

3　可相交直線序列的遍歷以及算法

平面內(nèi)可相交直線序列的遍歷算法研究三、平面內(nèi)可相交直線序列的遍歷及求解算法平面內(nèi)可相交直線序列的遍歷已經(jīng)受到國(guó)內(nèi)外幾何領(lǐng)域?qū)W者的廣泛關(guān)注。目前，學(xué)者對(duì)于平面內(nèi)可相交直線序列的遍歷的算法的研究非常的少。筆者就在目前幾何領(lǐng)域的研究成果上，分析平面內(nèi)可相交直線序列的遍歷的幾何特征，將其轉(zhuǎn)換成可相交線段的問(wèn)題并通過(guò)其算法，來(lái)研究平面內(nèi)可相交直線序列的遍歷的求解算法。（1）總體思路對(duì)于平面內(nèi)可相交直線序列的遍歷問(wèn)題，首先，筆者根據(jù)直線的起點(diǎn)和終點(diǎn)的相交來(lái)獲得一個(gè)凸多邊形，其次，遍歷途徑必定包含在直線構(gòu)造的凸多邊形中，因此，筆者將平面內(nèi)可相交直線序列的遍歷的問(wèn)題轉(zhuǎn)換成多邊形內(nèi)可相交線段的遍歷的問(wèn)題。最后，筆者通過(guò)對(duì)Rubberband算法的研究來(lái)解決平面內(nèi)可相交直線序列的遍歷的問(wèn)題。（2）凸多邊形F的構(gòu)造。如圖1所示，如果圖中的虛線部分是一條遍歷途徑，虛線在凸包邊緣的內(nèi)部并且凸包的邊緣和所有的遍歷直線相交，那么這條虛線所代表的遍歷途徑將不是最短的直線。因此，如果直線的起點(diǎn)和終點(diǎn)相同，那么計(jì)算出的便是一個(gè)凸多邊形。反之，則不是。（3）多邊形內(nèi)相交線段的遍歷問(wèn)題在多邊形內(nèi)相交線段的遍歷的算法中，Rubber-band算法是其中最經(jīng)典的算法之一。Rubber-band算法是從局部最優(yōu)達(dá)到全局最優(yōu)。在Rubber-band算法的算法中，主要是通過(guò)最短路徑差來(lái)考慮下一步的進(jìn)行。當(dāng)線段存在相交時(shí)，Rubber-band算法則會(huì)出現(xiàn)退化的現(xiàn)象。如圖2所示。在Rubber-band算法的過(guò)程中，當(dāng)兩條線段相同時(shí)，下一步的進(jìn)行就會(huì)停止不動(dòng)，導(dǎo)致Rubber-band算法提前結(jié)束，這將使算法得不到正確的答案。

因此，交換線段順序的算法能夠更好的求解平面內(nèi)可相交直線序列的遍歷問(wèn)題。

4　算法設(shè)計(jì)與實(shí)現(xiàn)

4.1算法流程

在分析平面內(nèi)可相交直線序列的遍歷算法流程時(shí)，可以將其分為求凸包和求多邊形，以及用改進(jìn)Rubber-band算法求最短遍歷路徑這幾個(gè)步驟。其中在求凸包的步驟中，主要采用的是Graham算法來(lái)進(jìn)行相應(yīng)點(diǎn)集的計(jì)算。而在求多邊形的過(guò)程中，則需要現(xiàn)根據(jù)已經(jīng)計(jì)算出的凸包切線，通過(guò)對(duì)頂點(diǎn)處的切線進(jìn)行構(gòu)建，建立包含這些凸包的多邊形。構(gòu)建處的多邊形如圖3所示。

圖1　凸多邊形F的構(gòu)造

圖2　凸多邊形F的構(gòu)造

圖3　構(gòu)建處的多邊形

最后是用改進(jìn)Rubber-band算法求最短遍歷路徑，就是依靠算法的基本思想和理念，設(shè)計(jì)出更加高效科學(xué)的便利算法，以提高對(duì)平面內(nèi)可相交直線的算法。

4.2基本數(shù)據(jù)結(jié)構(gòu)

在進(jìn)行平面內(nèi)相交直線的算法中，基本的數(shù)據(jù)結(jié)構(gòu)其實(shí)就是點(diǎn)線面這三種類(lèi)型。其中點(diǎn)是最常見(jiàn)的基本類(lèi)型，也是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)組成部分。而直線則是關(guān)系算法研究的重要部分，既可以用ax+by+c=o的方式進(jìn)行表現(xiàn)，也可以通過(guò)y=k*（x-pt.x）+py.t的結(jié)構(gòu)來(lái)表示，除此之外在遍歷算法中還有依靠判斷直線是否屬于相等函數(shù)的算法。

4.3算法實(shí)現(xiàn)

算法實(shí)現(xiàn)指的就是對(duì)平面內(nèi)可相交直線序列算法的實(shí)現(xiàn)過(guò)程，最主要的就是主流算法的計(jì)算過(guò)程，如圖4所示。

圖4　主流算法的計(jì)算過(guò)程

5　算法驗(yàn)證及結(jié)果分析

算法驗(yàn)證和結(jié)果分析，主要針對(duì)的就是對(duì)分析驗(yàn)算的結(jié)果繼續(xù)測(cè)試和分析，通過(guò)使用事后分析法，對(duì)算法的有效性進(jìn)行科學(xué)的驗(yàn)證，其中可以分為測(cè)試數(shù)據(jù)生成和運(yùn)行結(jié)果分析兩部分。

測(cè)試數(shù)據(jù)生成就是為了驗(yàn)證算法的正確性，可以借助隨機(jī)生成的大量數(shù)據(jù)進(jìn)行驗(yàn)證，并對(duì)計(jì)算的結(jié)果進(jìn)行分析，通過(guò)對(duì)數(shù)據(jù)的VC++實(shí)現(xiàn)處理，對(duì)遍歷算法的各個(gè)步驟進(jìn)行詳細(xì)的結(jié)構(gòu)分析，通過(guò)將其同理論數(shù)據(jù)相比較，進(jìn)而驗(yàn)證算法的正確性和時(shí)間復(fù)雜度，進(jìn)一步加強(qiáng)對(duì)平面內(nèi)可相交直線序列的便利算法研究。

6　對(duì)未來(lái)遍歷算法的預(yù)測(cè)

上文已經(jīng)細(xì)致研究了平面內(nèi)相交直線序列存在的遍歷算法，同時(shí)也探索出了另一種改進(jìn)Rubber-band算法的思路，實(shí)現(xiàn)平面內(nèi)相交直線序列的遍歷算法，以及求解出其遍歷問(wèn)題，這也是該文研究成果精髓所在?？墒?，由于本文實(shí)際的內(nèi)容還不夠完善，致使在研究方面所涉及的相關(guān)內(nèi)容還存在一些小的缺陷，這些曲線對(duì)遍歷算法未來(lái)的發(fā)展還存在一定的影響，因此，對(duì)對(duì)未來(lái)遍歷算法的預(yù)測(cè)，可以從以下幾個(gè)方面問(wèn)題難點(diǎn)著手。

（1）本文雖提出的算法因其條件的限制，還只適用于對(duì)兩條直線相交于一點(diǎn)的情況進(jìn)行分析、求解及處理，而涉及3條或3條以上的直線相交同一點(diǎn)的情況，因?yàn)檫€沒(méi)有對(duì)其做針對(duì)性的研究，該算法是否適用將無(wú)從得知，這也使得該問(wèn)題成為遍歷算法未來(lái)要攻克的一個(gè)方面。

（2）本位只涉及了構(gòu)造多邊形算法中的部分方式進(jìn)行了運(yùn)用，而對(duì)更復(fù)雜、更優(yōu)化的時(shí)間算法還沒(méi)有涉及到，因此在未來(lái)遍歷算法的研究中，可以運(yùn)用此算法，從而減少算法的整體執(zhí)行時(shí)間，實(shí)現(xiàn)高效的遍歷算法。

7　結(jié)語(yǔ)

本文對(duì)平面內(nèi)可相交直線序列中存在的遍歷問(wèn)題進(jìn)行了較為深切的分析和研究，討論了最短路徑的求解方式在幾何學(xué)計(jì)算中的有關(guān)基礎(chǔ)理論知識(shí)，研究了直線之間存在的位置關(guān)系，并例舉出以構(gòu)造多邊形的方式，對(duì)直線的初始訪問(wèn)順序進(jìn)行確認(rèn)與肯定。同時(shí)將構(gòu)造多邊形的內(nèi)部添加進(jìn)最短遍歷路徑，實(shí)現(xiàn)了構(gòu)造多邊形內(nèi)部相交線段的遍歷算法，也對(duì)其進(jìn)行了相當(dāng)深入的對(duì)比與研究。而從遍歷算法的幾種不同性質(zhì)的線段中，對(duì)其思路的改進(jìn)也使得Rubber-band的運(yùn)用適應(yīng)了可相交直線序列，其共同作用使可相交直線序列的遍歷算法最終得以實(shí)現(xiàn)及證明。此外構(gòu)造測(cè)試數(shù)據(jù)，證明了在實(shí)際運(yùn)行中其設(shè)計(jì)的算法所得出運(yùn)行結(jié)果的準(zhǔn)確性。

［參考文獻(xiàn)］

［1］譚錦彪.遍歷平面內(nèi)Partial-Order線段集的ESP求解算法研究［D］.大連：大連海事大學(xué)，2013.

［2］鄭毅.訪問(wèn)平面內(nèi)線段序列的ESP問(wèn)題求解算法研究［D］.大連：大連海事大學(xué)，2012.

［3］孫立曉.訪問(wèn)平面內(nèi)不相交線段的ESP問(wèn)題求解算法研究［D］.大連：大連海事大學(xué)，2012.

［4］蘭明.平面內(nèi)經(jīng)過(guò)若干不相交線段的L1問(wèn)題求解研究［D］.大連：大連海事大學(xué)，2011.

［5］徐麗麗.基于flip的Delaunay三角剖分算法研究［D］.大連：大連海事大學(xué)，2010.

［6］任保營(yíng).基于Delaunay三角剖分的TSP問(wèn)題求解研究［D］.大連：大連海事大學(xué)，2010.

［7］侯斌.簡(jiǎn)單多邊形內(nèi)Euclidean最短路徑問(wèn)題算法研究［D］.大連：大連海事大學(xué)，2010.

［8］鄧禮禮.求圖中受限制的所有最短路徑算法的分析與研究［D］.上海：華東師范大學(xué)，2009.

Research on the Traversal Algorithm of Intersecting Lines in Plane

Ren Zhong
(Henan Procuratorial Vocational College, Zhengzhou451191, China)

Abstract：Plane eligible AC linear algorithm is a classical topic in geometry, this paper research status at home and abroad, and puts forward several feasible algorithm and using plane two points and a straight line position, two linear position relation algorithm, symmetric algorithm， convex hull algorithm. The calculation method is studied and deduced， and fnally the conclusion is drawn.

Key words：symmetry point； intersection line； scientifc algorithm

作者簡(jiǎn)介：任重（1981-），男，河南鄭州，本科；研究方向：算法設(shè)計(jì)和分析。