計算幾何

《計算幾何:算法與應用》(第2版)的前4章對幾何算法進行了討論，包括幾何求交、三角剖分、線性規(guī)劃等，其中涉及的隨機算法也是《計算幾何:算法與應用》(第2版)的一個鮮明特點。第5章至第10章介紹了多種幾何結構，包括幾何查找、kd樹、區(qū)域樹、梯形圖、Voronoi圖、排列、Delaunay三角剖分、區(qū)間樹、優(yōu)先查找樹以及線段樹等。第11章至第16章結合實際問題，繼續(xù)討論了若干幾何算法及其數(shù)據結構，包括高維凸包、空間二分及BSP樹、運動規(guī)劃、網格生成及四叉樹、最短路徑查找及可見性圖、單純性區(qū)域查找及劃分樹和切分樹等，這些也是對前十章內容的進一步深化。