三維空間內凹多面體的Minkowski和的算法研究.pdf

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

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

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