計(jì)算三維空間凸多面體的精確Minkowski和的算法研究.pdf

1、計(jì)算幾何是理論計(jì)算機(jī)科學(xué)領(lǐng)域中一個(gè)新的極有生命力的子領(lǐng)域，而Minkowski和算法作為計(jì)算幾何研究領(lǐng)域中的一個(gè)分支，在理論和應(yīng)用上都有著重要的意義，其研究成果已在機(jī)器人學(xué)、計(jì)算機(jī)圖形學(xué)、CAD等許多領(lǐng)域中發(fā)揮了重要的作用。如何為各種應(yīng)用提供有效的基礎(chǔ)算法以及理論依據(jù)，一直是國(guó)內(nèi)外學(xué)者研究的方向。 本文針對(duì)疊置算法是計(jì)算兩個(gè)凸多面體Minkowski的重要步驟的情況，為克服現(xiàn)有疊置算法的缺陷，從一個(gè)全新的角度對(duì)平面劃分的疊置算法

2、進(jìn)行了研究，提出了三角形內(nèi)簡(jiǎn)單平面凸劃分的疊置算法。整個(gè)算法分為計(jì)算交點(diǎn)、拓?fù)渲亟M和創(chuàng)建雙向鏈接邊表記錄三步，文章同時(shí)對(duì)算法的正確性和復(fù)雜度進(jìn)行了分析。 文中以減少計(jì)算平面劃分疊置的次數(shù)，提高算法的執(zhí)行效率為目標(biāo)，提出了正四面體中心投影的概念。通過(guò)計(jì)算凸多面體的正四面體中心投影，按照給定坐標(biāo)系下的坐標(biāo)轉(zhuǎn)換關(guān)系，把三維空間的問(wèn)題轉(zhuǎn)換到二維空間進(jìn)行解決。提出了基于正四面體中心投影的凸多面體的精確Minkowski和求和算法。采用三角