ACM 很全的計(jì)算幾何模板 基礎(chǔ)部分 1.幾何公式 5 1.1三角形 5 1.2四邊形 5 1.3正n邊形 5 1.4圓 5 1.5棱柱 6 1.6棱錐 6 1.7棱臺 6 1.8圓柱 6 1.9圓錐 6 1.10圓臺 7 1.11球 7 1.12球臺 7 1.13球扇形 7 2.直線與線段 7 2.0預(yù)備函數(shù) 7 2.1判三點(diǎn)是否共線 8 2.2判點(diǎn)是否在線段上 9 2.3判斷兩點(diǎn)在線段的同一側(cè) 9 2.4判斷兩點(diǎn)是否在線段的異側(cè) 9 2.5求點(diǎn)關(guān)于直線的對稱點(diǎn) 10 2.7判斷兩線段是否相交 10 2.7.1常用版 10 2.7.2不常用版 11 2.8 求兩條直線的交點(diǎn) 11 2.9點(diǎn)到直線的最近距離 12 2.10點(diǎn)到線段的最近距離 12 3.多邊形 12 3.0 預(yù)備浮點(diǎn)函數(shù) 12 3.1判定是否是凸多邊形 13 3.2判定點(diǎn)是否在多邊形內(nèi) 14 3.3 判定一條線段是否在一個(gè)任意多邊形內(nèi) 15 4. 三角形 16 4.0預(yù)備函數(shù) 16 4.1求三角形的外心 17 4.2求三角形內(nèi)心 17 4.3求三角形垂心 17 5. 圓 18 5.0預(yù)備函數(shù) 18 5.1判定直線是否與圓相交 19 5.2判定線段與圓相交 19 5.3判圓和圓相交 19 5.4計(jì)算圓上到點(diǎn)p最近點(diǎn) 19 5.5計(jì)算直線與圓的交點(diǎn) 20 5.6計(jì)算兩個(gè)圓的交點(diǎn) 20 6. 球面 21 6.0給出地球經(jīng)度緯度，計(jì)算圓心角 21 6.1已知經(jīng)緯度，計(jì)算地球上兩點(diǎn)直線距離 21 6.2已知經(jīng)緯度，計(jì)算地球上兩點(diǎn)球面距離 21 7. 三維幾何的若干模板 22 7.0預(yù)備函數(shù) 22 7.1判定三點(diǎn)是否共線 23 7.2判定四點(diǎn)是否共面 23 7.1判定點(diǎn)是否在線段上 23 7.2判斷點(diǎn)是否在空間三角形上 24 7.3判斷兩點(diǎn)是否在線段同側(cè) 24 7.4判斷兩點(diǎn)是否在線段異側(cè) 25 7.5判斷兩點(diǎn)是否在平面同側(cè) 25 7.6判斷兩點(diǎn)是否在平面異側(cè) 25 7.7判斷兩空間直線是否平行 25 7.8判斷兩平面是否平行 26 7.9判斷直線是否與平面平行 26 7.10判斷兩直線是否垂直 26 7.11判斷兩平面是否垂直 26 7.12判斷兩條空間線段是否相交 27 7.13判斷線段是否與空間三角形相交 27 7.14計(jì)算兩條直線的交點(diǎn) 28 7.15計(jì)算直線與平面的交點(diǎn) 28 7.16計(jì)算兩平面的交線 29 7.17點(diǎn)到直線的距離 29 7.18 計(jì)算點(diǎn)到平面的距離 29 7.19計(jì)算直線到直線的距離 30 7.20空間兩直線夾角的cos值 30 7.21兩平面夾角的cos值 30 7.22直線與平面夾角sin值 31 1.最遠(yuǎn)曼哈頓距離 31 2. 最近點(diǎn)對 32 3. 最近點(diǎn)對 34 4. 最小包圍圓 36 5. 求兩個(gè)圓的交點(diǎn) 39 6. 求三角形外接圓圓心 40 7. 求凸包 42 8.凸包卡殼旋轉(zhuǎn)求出所有對踵點(diǎn)、最遠(yuǎn)點(diǎn)對 44 9. 凸包+旋轉(zhuǎn)卡殼求平面面積最大三角 47 10. Pick定理 50 11. 求多邊形面積和重心 51 12. 判斷一個(gè)簡單多邊形是否有核 52 13. 模擬退火 54 14. 六邊形坐標(biāo)系 56 15. 用一個(gè)給定半徑的圓覆蓋最多的點(diǎn) 60 16. 不等大的圓的圓弧表示 62 17. 矩形面積并 62 18. 矩形的周長并 66 19. 最近圓對 70 20. 求兩個(gè)圓的面積交 74