一種凸多邊形的爆破網(wǎng)絡(luò)等時(shí)線算法研究

鄭 武，王 磊，呂仁輝

(武漢科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北武漢430081)

1 問題的提出

在爆破工程中，為了精確控制爆破過程，通常需要借助等時(shí)線來分析爆破的趨勢(shì)［1］，通過將起爆時(shí)刻相同或相近的炮孔用等時(shí)線連接起來，就可以更加直觀地看到爆破的進(jìn)度，而且可以根據(jù)等時(shí)線進(jìn)一步確定整個(gè)爆破的延伸方向。在實(shí)際中，通常是先計(jì)算出每個(gè)炮孔的起爆時(shí)刻，然后統(tǒng)計(jì)出起爆時(shí)刻相同或相近的炮孔，最后分析爆破的趨勢(shì)。某爆破項(xiàng)目的示意圖如圖1，其中數(shù)字代表起爆時(shí)刻，有箭頭的線段代表孔外延時(shí)，沒有箭頭的曲線代表等時(shí)線，紅色實(shí)心小三角形指明了爆破的巖石移動(dòng)方向。CHI Bao-ming［2］，ZHANG Wei［3］等學(xué)者對(duì)針對(duì)爆破網(wǎng)絡(luò)設(shè)計(jì)中的等時(shí)線進(jìn)行了相關(guān)研究和探討。研究者們提出的等時(shí)線算法，針對(duì)布孔比較規(guī)律的情況下比較有效，但卻有不同延時(shí)時(shí)間的等時(shí)線會(huì)存在交叉，獲取等時(shí)線時(shí)間過長(zhǎng)等問題［1-3］。

爆破網(wǎng)絡(luò)等時(shí)線的生成與優(yōu)化問題描述如下:在給定的爆破網(wǎng)絡(luò)中，所有炮孔的起爆時(shí)刻已知，炮孔的位置已知，需要將起爆時(shí)刻相同(或近似相同)的炮孔用等時(shí)線連起來。要求生成的等時(shí)線至少滿足4個(gè)條件:

(1)同一等時(shí)線不會(huì)自相交叉;

(2)等時(shí)線簡(jiǎn)明直觀，路徑較短;

(3)等時(shí)線能自動(dòng)適應(yīng)網(wǎng)絡(luò)變化;

(4)等時(shí)線生成效率較高。

圖1 某工程爆破網(wǎng)絡(luò)示意圖

為了更詳細(xì)地說明問題，將工程爆破中的相關(guān)術(shù)語及算法問題形式化描述如下:

定義1 起爆時(shí)刻，即爆破工程中炮孔實(shí)際起爆的時(shí)刻。爆破網(wǎng)絡(luò)給定之后，每個(gè)炮孔的起爆時(shí)刻是客觀存在的。起爆時(shí)刻可以根據(jù)爆破網(wǎng)絡(luò)中的炮孔布局計(jì)算得出。

定義2 等時(shí)線，即爆破工程中，為了準(zhǔn)確直觀地分析爆破過程，將起爆時(shí)刻相同(或近似相同)的炮孔連接起來的線。

本文通篇都涉及到等時(shí)線一詞，包括等時(shí)線的定義、計(jì)算、生成、優(yōu)化等，等時(shí)線的形式化定義如下:

定義 Xi、Xj為兩個(gè)不同的炮孔，t(Xi)、t(Xj)是炮孔的起爆時(shí)刻，Δt是允許的時(shí)間間隔。

若│t(Xi)-t(Xj)│≤Δt，則稱 Xi、Xj等時(shí)，采用等時(shí)線連接;

若│t(Xi)-t(Xj)│ ＞ Δt，則稱 Xi、Xj不等時(shí)，不用等時(shí)線連接;

其中 1≤i≤n，1≤j≤n。

嚴(yán)格按照前文所述的算法要求來完成算法的實(shí)現(xiàn)。為了避免同一等時(shí)線的交叉問題，采用凸多邊形算法進(jìn)行等時(shí)線的連接。為了使得生成的等時(shí)線路徑較短，采用自定義三角形算法進(jìn)行比較，并采用貪心算法進(jìn)行優(yōu)化。具體分為如下幾個(gè)過程:

(1)將爆破網(wǎng)絡(luò)中的炮孔按照起爆時(shí)刻進(jìn)行分類。

(2)將同一起爆時(shí)刻段的炮孔按層次劃分，主要采用凸多邊形生成算法進(jìn)行歸類。

(3)將同一起爆時(shí)刻段上的炮孔按照上一步劃分的層次，初步形成等時(shí)線。過程如下:已知最外層的凸多邊形，形成一個(gè)回路。首先將次外層的凸多邊形上的各個(gè)頂點(diǎn)插入到回路中去，插入時(shí)選取插入后使得路徑最短的動(dòng)作來做。然后按照從外到內(nèi)的順序依次將各個(gè)凸多邊形上的頂點(diǎn)插入到回路中去。文中采用一種三角形方法來快速選擇優(yōu)先插入的炮孔。

(4)判斷形成的等時(shí)線是否存在自相交叉情況，如果存在則進(jìn)行去交叉算法。

(5)使用貪心算法進(jìn)一步優(yōu)化等時(shí)線。

2 算法描述

在實(shí)際的爆破工程中，一般會(huì)用到大量的炮孔，炮孔的位置是根據(jù)爆破的需要而分配，炮孔的起爆時(shí)刻也不全相同。在統(tǒng)計(jì)完炮孔的起爆時(shí)刻后，會(huì)發(fā)現(xiàn)同一起爆時(shí)刻的炮孔位置很散亂的分布，這時(shí)如何將各個(gè)起爆時(shí)刻相同的炮孔連成一條等時(shí)線呢?使用相鄰連接的辦法經(jīng)常會(huì)造成連線的交叉、相鄰的距離很遠(yuǎn)等缺陷，為了避免這些問題，我們需要采用一種新的等時(shí)線生成算法——基于凸多邊形的插入算法。為了盡可能詳細(xì)的說明這一算法，本文只討論一條等時(shí)線的生成，基本模型如圖2。給定一些均勻分布的炮孔，這些炮孔的起爆時(shí)刻相同或近似相同，每個(gè)炮孔的位置已知，要求把這些炮孔連成一條等時(shí)線。圖2中所有炮孔的起爆時(shí)刻相同或近似相同，炮孔的位置是均勻隨機(jī)分布的。

圖2 均勻分布的100個(gè)炮孔

2.1 按層次劃分炮孔

第1步 在圖2所示的區(qū)域里搜索出以炮孔位置為頂點(diǎn)的最外層的凸多邊形，標(biāo)記這個(gè)凸多邊形上的炮孔，并標(biāo)記這個(gè)凸多邊形為0層(搜索凸多邊形可以參考 Graham＇s Scan 算法)［4］;

第2步 在剩余沒有被標(biāo)記的炮孔中搜索以炮孔位置為頂點(diǎn)的最外層的凸多邊形，標(biāo)記這個(gè)凸多邊形上的炮孔，并標(biāo)記這個(gè)凸多邊形為第1層。

……重復(fù)第2步的操作，直到剩余的沒有標(biāo)記的炮孔位置不足以構(gòu)成一個(gè)凸多邊形。

在執(zhí)行完所有的步驟之后，原來沒有規(guī)律的炮孔已經(jīng)被按層次分開了，如圖3。

圖3 搜索所有的凸多邊形

2.2 炮孔分層插入

在找到所有的凸多邊形后，對(duì)這些凸多邊形進(jìn)行編號(hào)，從最外層到最內(nèi)層依次為第0層，第1層，第2層，……，第n層(注意，如果最里面有不在凸多邊形上的炮孔，那么把這些炮孔記作最內(nèi)層上的，即第n層)。

插入過程如下:

第1步 將第1層上所有的炮孔依次插入到第0層，執(zhí)行完之后第1層為空，第0層上新增加了原來第1層所有的炮孔;

第2步 將第2層上所有的炮孔依次插入到第0層，執(zhí)行完之后第2層為空，第0層上新增加了原來第2層所有的炮孔;

……重復(fù)第2步的操作;

第n步 將第n層上所有的炮孔依次插入到第0層，執(zhí)行完之后第n層為空，所有的炮孔都被添加到第0層上，即當(dāng)前只有一層。

為了保證最終形成的等時(shí)線最短，沒有交叉，就需要確定最優(yōu)的插入算法。具體的過程是將待插入的炮孔在每個(gè)能夠插入的位置進(jìn)行一次插入操作，而最終選擇執(zhí)行完插入操作后總路徑最短的插入方法，具體的插入過程分成兩步。

2.2.1 插入位置選擇

算法如圖4。炮孔p0有兩個(gè)插入位置可以選擇(p1與p2之間，p2與p3之間)，采用算法1之后增加的長(zhǎng)度為Δs1=a1+b1-c1;采用算法2之后增加的長(zhǎng)度為Δs2=a2+b2-c2;比較Δs1和Δs2的大小，選擇其中較小的插入算法。

圖4 算法及效果示意圖

2.2.2 插入炮孔的順序選擇

選擇先插入點(diǎn)示意圖如圖5。有p01，p02兩個(gè)炮孔需要被插入到等時(shí)線上，那么如何確定哪個(gè)炮孔先插入進(jìn)去呢?做法是先按照步驟1對(duì)p01，p02分別選出最優(yōu)的插入位置，然后選出完成插入操作后路徑最短的炮孔，則這個(gè)炮孔就被選擇優(yōu)先插入。

2.2.3 優(yōu)化——去交叉

在完成上述操作后，基本上可以生成滿足要求的等時(shí)線。經(jīng)測(cè)試，上述方法在中等規(guī)模數(shù)量(150個(gè)炮孔左右)下沒有問題，但是在炮孔數(shù)量龐大(200個(gè)以上)的情況下，偶爾會(huì)出現(xiàn)一兩處交叉情況，如圖6(a)。經(jīng)過反復(fù)試驗(yàn)發(fā)現(xiàn)，出現(xiàn)交叉情況只會(huì)在少數(shù)情況而且在很小區(qū)域里，采用貪心算法矯正這部分的交叉即可(如圖6(b))。

圖5 選擇先插入點(diǎn)示意圖

圖6 交叉情況示意圖

矯正交叉過程如圖7。p1-p4與p2-p5出現(xiàn)交叉情況如圖7(a)，只要將p1連到p2，p4連到p5即可消除交叉，如圖7(b)。

圖7 矯正交叉過程圖

3 測(cè)試結(jié)果

本程序的運(yùn)行測(cè)試是在Windows7 32位操作系統(tǒng)上進(jìn)行的，處理器是Intel CORE2 2.20 GHz，安裝內(nèi)存為2.00 GB。

對(duì)本文的算法進(jìn)行了兩方面的檢測(cè)，首先用自動(dòng)生成的大量炮孔進(jìn)行檢測(cè)，然后用實(shí)際爆破工程圖進(jìn)行檢測(cè)。在采用自動(dòng)生成的炮孔檢測(cè)時(shí)，采用200個(gè)炮孔進(jìn)行10次檢測(cè)，發(fā)現(xiàn)生成的等時(shí)線符合要求，生成速度較快。在采用實(shí)際工程案例測(cè)試時(shí)，采用了10個(gè)規(guī)范布局圖進(jìn)行檢測(cè)，發(fā)現(xiàn)生成的等時(shí)線滿足工程要求。同時(shí)實(shí)際項(xiàng)目中等時(shí)線所花時(shí)間比均勻隨機(jī)布孔花的時(shí)間少得多，主要是因?yàn)閷?shí)際項(xiàng)目有多條等時(shí)線，每條等時(shí)線上的炮孔的數(shù)量較少造成的。具體測(cè)試數(shù)據(jù)見表1和表2。

表1 均勻隨機(jī)分布炮孔測(cè)試結(jié)果

續(xù)表

表2 實(shí)際工程案例測(cè)試結(jié)果

4 結(jié)語

本文主要探討了基于凸多邊形插入的爆破網(wǎng)絡(luò)等時(shí)線的生成及優(yōu)化算法，通過分層插入的方法使復(fù)雜的爆破網(wǎng)絡(luò)具有清晰的層次，并且有條理地將每一個(gè)炮孔插入到相應(yīng)的等時(shí)線上，最后說明了插入過程中的問題及解決方案。通過具體的實(shí)驗(yàn)證明，該算法可以適用于復(fù)雜網(wǎng)絡(luò)情況的等時(shí)線生成，并且可以達(dá)到較好的效果。

［1］張樂，顏景龍.起爆延期等時(shí)線的生成及其應(yīng)用研究［J］.工程爆破，2010，16(2):86-90.

［2］CHI Baoming，LI Zhijun，YE Yong.Study on the arithmetic of automatically drawing isoclines of groundwater level based on GIS［J］.Journal of Jilin University(Earth Science Edition)，2007，37(2):261-265.

［3］ZHANG Weiqin，QING Yan ，JIAN Xingxiang.Natural neighbor interpolation and its application to 2D grid of irregular data［J］.Computing Techniques for Geophysical and Geochemical Exploration，2011，6(3):291-295.

［4］RONALD L G.An efficient algorithm for determining the convex hull of a finite planer set［J］.Information Processing Letters，1972，1(1):132-133.