計(jì)算幾何課件

計(jì)算幾何ComputationalGeometry主講人：x2024年3月18日什么是計(jì)算幾何2024/3/11ComputationalGeometry2什么是計(jì)算幾何計(jì)算幾何：?數(shù)學(xué)?計(jì)算機(jī)起源于1971年，計(jì)算機(jī)圖形學(xué)(CG)與計(jì)算機(jī)輔助設(shè)計(jì)(CAD)的推動(dòng)主要關(guān)注解決幾何問題的算法三角剖分、凸包、掃描線、旋轉(zhuǎn)卡殼、半平面交、最小圓覆蓋……特點(diǎn)：需要處理實(shí)數(shù)而非整數(shù)、關(guān)心（低維）向量而非標(biāo)量為什么需要計(jì)算幾何降低在計(jì)算機(jī)中解決幾何問題的復(fù)雜度降低在計(jì)算機(jī)中解決幾何問題的數(shù)值誤差2024/3/11ComputationalGeometry3點(diǎn)、線、面的表示

2024/3/11ComputationalGeometry4點(diǎn)、線、面的表示

2024/3/11ComputationalGeometry5

點(diǎn)、線、面的表示

2024/3/11ComputationalGeometry6

點(diǎn)與線的距離

2024/3/11ComputationalGeometry7

線與線的位置關(guān)系(2D)

2024/3/11ComputationalGeometry8

線與線的位置關(guān)系(2D)

2024/3/11ComputationalGeometry9

線與線的位置關(guān)系(3D)

2024/3/11ComputationalGeometry10點(diǎn)與面的距離

2024/3/11ComputationalGeometry11

多邊形的周長(zhǎng)與面積(2D)

2024/3/11ComputationalGeometry12

點(diǎn)與多邊形的位置關(guān)系(2D)

2024/3/11ComputationalGeometry13

點(diǎn)與多邊形的位置關(guān)系(2D)

2024/3/11ComputationalGeometry14點(diǎn)與多邊形的位置關(guān)系(2D)

2024/3/11ComputationalGeometry15點(diǎn)到三角形的距離

2024/3/11ComputationalGeometry16三角形之間的距離二維情形（保證不相交）6組點(diǎn)—面/18組點(diǎn)—邊距離的最小值三維情形（保證不相交）6組點(diǎn)—面距離的最小值9組邊—邊距離的最小值三角形距離與碰撞檢測(cè)離散碰撞檢測(cè)(discretecollisiondetection,DCD)求兩個(gè)三角形網(wǎng)格(triangularmesh)之間的距離連續(xù)碰撞檢測(cè)(continuouscollisiondetection,CCD)三角形網(wǎng)格的每個(gè)頂點(diǎn)都有速度，求兩個(gè)網(wǎng)格經(jīng)過多長(zhǎng)時(shí)間發(fā)生接觸先考察“點(diǎn)—面”和“邊—邊”何時(shí)共面（均為一元三次方程組）再判斷共面時(shí)是否接觸2024/3/11ComputationalGeometry17德洛內(nèi)(Delaunay)三角剖分(2D)三角剖分將點(diǎn)集連接為三角網(wǎng)格，使得各三角形的邊不相交德洛內(nèi)三角剖分空?qǐng)A性：任意三角形的外接圓內(nèi)無其它點(diǎn)規(guī)則化：最大化最小角其它性質(zhì)所得結(jié)果唯一增刪改頂點(diǎn)只影響局部最外層邊界形成凸多邊形沃羅諾伊(Voronoi)圖：三角剖分的對(duì)偶圖將平面劃分為若干由最近控制點(diǎn)決定的區(qū)域2024/3/11ComputationalGeometry18凸包(2D)凸包的定義在平面上能包含給定點(diǎn)的最小的凸多邊形凸多邊形：所有內(nèi)角均小于180°的多邊形凸包與包圍盒軸對(duì)齊包圍盒(axisalignedboundingbox,AABB)包含給定點(diǎn)的與坐標(biāo)軸平行的矩形凸包一定在AABB內(nèi)；AABB是凸包最粗糙的近似方向包圍盒(orientedboundingbox,OBB)包含給定點(diǎn)的最小的矩形固定方向凸包(fixeddirectionshulls,FDH)“凸包”各邊（面）的法向只能在給定集合中選取2024/3/11ComputationalGeometry19凸包(2D)

2024/3/11ComputationalGeometry20凸包(3D)

2024/3/11ComputationalGeometry21平面最近點(diǎn)對(duì)(2D)

2024/3/11ComputationalGeometry22最小圓覆蓋(2D)

2024/3/11ComputationalGeometry23最小圓覆蓋(2D)

2024/3/11ComputationalGeometry24

反演變換

2024/3/11ComputationalGeometry25反演變換

2024/3/11ComputationalGeometry26總結(jié)參考資料MarkdeBergetal.鄧俊輝譯.計(jì)算幾何:算法與應(yīng)用(第3版).清華大學(xué)出版社.2009.周培德.計(jì)算幾何:算法設(shè)計(jì)與分析.清華大學(xué)出版社.2005.王華民.GAMES103:基于物理的計(jì)算機(jī)動(dòng)畫入門,Lecture09.課后練習(xí)(POJ)點(diǎn)、線、面2318,2398,3304,1269,2653,