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