2-D不規(guī)則多邊形演化布局求解的干涉量計算研究.pdf

1、服裝裁剪中的畫印布局,造船業(yè)板材切割中的部件拼裝和機械行業(yè)中的沖壓落料等二維不規(guī)則圖形布局問題都屬于NP-難問題,存在求解困難。為此,許多學者進行了大量的研究。其中,演化算法(例如,遺傳算法、模擬退火算法、粒子群算法)是有效的算法。大多數演化算法求解不規(guī)則圖形的布局問題時,其迭代過程中,都需要計算待布物之間、待布物與容器之間的干涉量,將它作為適應度函數的一部分,用以評估種群個體的優(yōu)劣。由于其干涉量計算的時間是其它耗時的總和的50-500

2、倍。因此,它成為演化布局算法求解效率和精度提高的瓶頸問題。為此,本文主要研究2-D不規(guī)則多邊形的布局演化求解中的干涉量計算問題,提出基于凸多邊形分解和裁剪的高效不規(guī)則多邊形交疊面積計算方法,進而提高不規(guī)則多邊形演化布局求解的效率和精度。希望所提出的方法能用于其它相關的問題。
　　本文主要工作如下:
　　1.本文提出了一種使用輔助點的不規(guī)則多邊形凸剖分算法(IPSPCD)。它是提高不規(guī)則多邊形交疊面積計算效率的前提。文中剖分算

3、法是按順時針方向依次將不規(guī)則多邊形中相鄰凹頂點分成4種情形,然后根據不同情形分解出一個凸多邊形,直至所有凹頂點全部被剖分。算法復雜度分析與數值實驗表明:與已存在的算法相比,本文算法剖分的凸多邊形個數較少,計算效率較高。
　　2.本文提出一種快速不規(guī)則多邊形裁剪算法(FCPC)。它是提高不規(guī)則多邊形交疊面積計算效率的關鍵。文中裁剪方法是基于其內頂點的判斷和線段與凸折線段之間的快速相交判斷與求交得到交疊多邊形頂點。由算法復雜度分析可知

4、:本文裁剪算法較已有的裁剪算法具有較低的計算復雜度。
　　3.本文提出一種求解不規(guī)則多邊形干涉量算法(CIPOA)。它首先分解不規(guī)則多邊形為數目較少的凸多邊形集,然后分別在兩集合之間進行快速裁剪求交,并計算交疊多邊形面積。算法復雜度分析和數值實驗表明:與已存在的算法相比,CIPOA算法提高了不規(guī)則多邊形之間的交疊面積的計算效率。
　　本文以2-D不規(guī)則多邊形布局問題的演化求解為背景,研究了不規(guī)則多邊形交疊面積干涉計算,以及與