三維空間內(nèi)凹多面體的Minkowski和的算法研究.pdf

1、計(jì)算幾何是計(jì)算機(jī)理論科學(xué)的一個重要分支，該學(xué)科已經(jīng)有了巨大的發(fā)展，產(chǎn)生了一系列的理論成果。Minkowski和算法作為計(jì)算幾何研究領(lǐng)域中的一個分支，在理論和應(yīng)用上都有著重要的意義，其研究成果已在機(jī)器人學(xué)、動態(tài)仿真、計(jì)算機(jī)圖形學(xué)等許多領(lǐng)域中得到了廣泛的應(yīng)用，尤其在機(jī)器人學(xué)領(lǐng)域，它是計(jì)算無碰撞路徑的一個重要工具。因此，如何快速而準(zhǔn)確地計(jì)算避障路徑，一直是國內(nèi)外學(xué)者研究的重要課題。
　　首先，在對國內(nèi)外研究現(xiàn)狀進(jìn)行綜合分析的基礎(chǔ)上，進(jìn)一

2、步研究了計(jì)算兩個凸多面體Minkowski和的求和算法。以減少計(jì)算平面劃分疊置的次數(shù)、提高算法的執(zhí)行效率為目標(biāo)，本文提出了基于正四面體映射和點(diǎn)投影的凸多面體的精確Minkowski和的算法，通過計(jì)算凸多面體的正四面體映射和點(diǎn)投影，把三維空間的問題轉(zhuǎn)換到二維平面進(jìn)行解決。
　　其次，凸剖分是計(jì)算凹多面體的Minkowski和的一個重要步驟。為了有效地計(jì)算凹多面體的Minkowski和，在研究了國內(nèi)外許多凸剖分算法后，本文采用集合論和

3、圖論的方法，提出了基于成功回路的凹多面體的剖分算法，同時對剖分算法的時間復(fù)雜度進(jìn)行了分析。
　　再次，給出了計(jì)算凹多面體的Minkowski和算法。采用成功回路的算法對凹多面體進(jìn)行剖分，得到若干子凸多面體；利用正四面體映射和點(diǎn)投影的算法計(jì)算所有可能成對的子凸多面體的Minkowski和；通過已改進(jìn)的增強(qiáng)立方體網(wǎng)格算法合并子凸多面體的Minkowski和多面體的邊界。
　　最后，通過實(shí)驗(yàn)驗(yàn)證了上述的研究內(nèi)容，給出了實(shí)驗(yàn)結(jié)果，并