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

1、計(jì)算幾何是計(jì)算機(jī)理論科學(xué)的一個(gè)較新的極有生命力的子領(lǐng)域，而Minkowski和算法作為計(jì)算幾何研究領(lǐng)域中的一個(gè)分支，在理論和應(yīng)用上都有著重要的意義，其研究成果已在圖形學(xué)、機(jī)器人技術(shù)、地理數(shù)據(jù)庫等領(lǐng)域中得到了廣泛的應(yīng)用。
　　首先，本文在對(duì)國內(nèi)外研究現(xiàn)狀進(jìn)行綜合分析的基礎(chǔ)上，進(jìn)一步研究了計(jì)算兩個(gè)凸多面體Minkowski和求和算法。為進(jìn)一步提高求和算法的執(zhí)行效率，本文優(yōu)化了基于正四面體中心投影的計(jì)算凸多面體精確Minkowski和求

2、和算法，提出基于正四面體高斯映射的凸多面體精確Minkowski和求和算法。同時(shí)對(duì)算法的時(shí)間復(fù)雜度進(jìn)行了對(duì)比分析。
　　其次，為有效的計(jì)算凹多面體Minkowski和，在研究了許多凸剖分算法后，提出按照三維幾何造型的不同，對(duì)凹多面體進(jìn)行四面體分解或者面分解的分而治之的剖分策略。同時(shí)對(duì)剖分算法的時(shí)間復(fù)雜度進(jìn)行了分析。
　　然后，為提高合并算法的計(jì)算效率，本文利用改進(jìn)的Enhanced Marching Cubes算法，提出了優(yōu)