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

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

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

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

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