平面內可相交直線序列的遍歷算法研究

任　重

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

?

平面內可相交直線序列的遍歷算法研究

任重

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

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

關鍵詞：對稱點；相交直線；科學算法

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

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

1　國內外研究現(xiàn)狀

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

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

論文的組織結構

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

這一章主要是對平面內直線能夠相交的最近路徑進行了討論，并對其意義和背景進行了闡述，還分析了國內和國外在這個問題上的研究，從而將本文的組織結構以及研究內容引導出來。

第二章：相關基本算法以及基礎知識。

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

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

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

第四章：算法的設計以及實現(xiàn)。

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

第五章：驗證算法并分析其結果。

這一章重點對實際運行的結果進行了分析，通過隨機的一種序列當做測試數(shù)據(jù)，利用分析法去驗證其求解算法，并給出一定的曲線方程。

第六章：結論。

這一章主要是總結，將文章的結論表明，并描述一些應該加以改進的問題。

2　相關基本算法以及基礎知識

2.1計算幾何學的概念

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

2.2計算幾何學的算法簡介

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

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

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

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

貪婪算法被稱為登山法，其進行原理一般如同登山一樣的步步為營。逐步的將全局的問題轉化為小部分的問題，并保證局部實現(xiàn)最優(yōu)化解決方案，當一部分出現(xiàn)無解或者不能進行時，全部算法過程就會停止。其特點就是簡單。便捷。并能同時進行。貪婪算法在求解某些問題上具有自身的優(yōu)越性，諸如拓撲排序問題，背包問題以及本文中多次涉及到的路徑最短問題。

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

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

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

4　算法設計與實現(xiàn)

4.1算法流程

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

圖1　凸多邊形F的構造

圖2　凸多邊形F的構造

圖3　構建處的多邊形

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

4.2基本數(shù)據(jù)結構

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

4.3算法實現(xiàn)

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

圖4　主流算法的計算過程

5　算法驗證及結果分析

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

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

6　對未來遍歷算法的預測

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

（1）本文雖提出的算法因其條件的限制，還只適用于對兩條直線相交于一點的情況進行分析、求解及處理，而涉及3條或3條以上的直線相交同一點的情況，因為還沒有對其做針對性的研究，該算法是否適用將無從得知，這也使得該問題成為遍歷算法未來要攻克的一個方面。

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

7　結語

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

［參考文獻］

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

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

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

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

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

［6］任保營.基于Delaunay三角剖分的TSP問題求解研究［D］.大連：大連海事大學，2010.

［7］侯斌.簡單多邊形內Euclidean最短路徑問題算法研究［D］.大連：大連海事大學，2010.

［8］鄧禮禮.求圖中受限制的所有最短路徑算法的分析與研究［D］.上海：華東師范大學，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

作者簡介：任重（1981-），男，河南鄭州，本科；研究方向：算法設計和分析。