[發明專利]一種凸包的搜索方法

有效

• 申請號: 201110214998.1
• 申請日: 2011-07-29
• 公開（公告）號: CN102270233A
• 公開（公告）日: 2011-12-07
• 發明（設計）人: 安凱;辛明瑞
• 申請（專利權）人: 中國航天科技集團公司第五研究院第五一三研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 李愛英;付雷杰

技術領域

本發明涉及一種搜索方法，具體涉及一種針對分散目標點的凸包的搜索方法。

背景技術

在工程技術中，需要對電路板中的焊點實施焊接，對于焊點數量很大的情況，常需要對焊接工具的移動路徑做特殊設置，根據電路板中焊點的位置數據規劃出一條經過所有焊點的閉合路徑，使得該路徑的總長度最小，以減少焊接工具在移動過程中的能量消耗和器件磨損。尋找焊接工具移動路徑的過程就是要解決“焊點自動檢查的路徑優化問題”。

在車輛路由領域，也存在類似于“焊點自動檢查的路徑優化問題”的問題。當目的地數量較多且分散度較大時，對運輸工具的行駛路徑進行規劃是必要的，需要找出一條恰經過每個目的地一次且總行程最短的閉合路徑。按照該路徑行駛，運行的距離最短，運行的時間最短，可大幅降低運輸成本，提高運輸效率，節約能源消耗。

在實際中，路徑的優化問題在許多領域都具有重要的應用價值，如計算機配線，通信網絡頻率分配以及電網布線等等，常見的路徑優化方法有“最近鄰方法”和“插入法”等。“最近鄰方法”是以任意一個目標點作為路徑的起點，在路徑的末端后面總是選擇與其距離最近的一個目標點加入路徑中，重復這種搜索模式，直到將全部目標點都納入到路徑中，該路徑是一條優化路徑。“插入法”是在選擇下一個目的地時，選擇插入代價(d_ik+d_kj-d_ij)最小的目的地。

盡管“最近鄰方法”和“插入法”優化了路徑選擇，但是，它們在選擇下一個目的地時都未考慮與上一選擇步驟之間的關聯，因此具有一定的盲目性。為消除這種盲目性，應尋找一種能夠將所有目標點關聯起來的優化方法。針對由分散目標點形成的點集，存在一種凸包理論，其就是要將選擇各個目標點的步驟關聯起來，以確定點集的最外圍閉合環。因此，利用凸包理論能夠為解決路徑的優化問題提供新思路，消除現有方法中的盲目性。因此，為了解決路徑優化方法中的缺陷，需要利用凸包理論，確定目標點集的凸包。

凸包，是指包含了目標點集中的所有點的最小凸多邊形。關于如何確定一個目標點集的凸包，R.L?Graham提出了一種Graham掃描算法，該算法首先對有限點集排序，假設首先發現了一個內部點，以其為中心依據極角與極半徑依次對其余點進行排序，能夠確定該點集的凸包。Graham算法的優點在于在任何情況下，尤其在最壞情況下(所有的目標點都是凸包的頂點)，計算點集的凸包有一個最優的時間復雜度。此外，一種較為簡便的方法是“包裹法”(Gift-Wrapping)，其將縱坐標最小的點作為凸包的第一個頂點A，將與水平線的交叉積為正且夾角最小的點作為凸包的第二個頂點B，將與線段AB的交叉積為正且夾角最小的點作為凸包的第三個頂點C，依此類推，直至找到凸包的所有頂點。然而，盡管人們對凸包的搜索方法進行了大量研究，但運算過程都較為復雜，且耗時長，主要的問題在于對一些不可能屬于凸包的點反復搜索檢查，不僅浪費了大量的運算時間，還增加了運算成本。多年來，人們一直在尋找確定凸包的更優算法。

發明內容

所謂凸包，就是不考慮目標點集的中間部分，僅選擇目標點集邊緣處的點，令其形成凸包。根據凸包的含義，本發明提出一種簡單高效的凸包搜索方法，能夠將目標點集中不需要考慮的點自動移除。

具體地，本發明提供了一種用于確定由分散放置的目標點形成的目標點集的凸包的搜索方法，其特征在于所述方法包含確定位于目標點集的最左側、最下側、最右側和最上側的目標點，分別記為第一頂點、第二頂點、第三頂點和第四頂點；確定第一點集，其包含以第一頂點、第二頂點、第三頂點和第四頂點為頂點的四邊形的內部的目標點；確定第二點集，其包含從目標點集中除去第一點集后剩余的目標點；在第二點集中搜索凸包頂點，將搜索到的凸包頂點依次連接形成目標點集的凸包。

采用本發明所提出的方法搜索凸包，其效率是目前被公認為最好的Jarvis’smarch方法的n/n₀倍，可大幅縮短運算時間，提高搜索效率，降低運算成本。

附圖說明

圖1是目標點集的多層凸包。

圖2是確定新的凸包頂點后構建三角形的示意圖。

圖3是確定新的凸包頂點后形成向量的示意圖。

圖4是按照本發明的方法搜索到的凸包的示意圖。

具體實施方式

本發明提供一種確定由分散放置的目標點形成的點集的凸包的搜索方法，研究對象可以是任意元素，例如電路板上的焊點，多個目標旅游城市，計算機配線網絡中的多臺計算機等等，確定這些元素的凸包，就是要尋找由這些分散放置的目標點構成的點集中處在最邊緣的點。