一、點的基本運(yùn)算
1. 平面上兩點之間距離 1
2. 判斷兩點是否重合 1
3. 矢量叉乘 1
4. 矢量點乘 2
5. 判斷點是否在線段上 2
6. 求一點饒某點旋轉(zhuǎn)后的坐標(biāo) 2
7. 求矢量夾角 2

二、 線段及直線的基本運(yùn)算
1. 點與線段的關(guān)系 3
2. 求點到線段所在直線垂線的垂足 4
3. 點到線段的最近點 4
4. 點到線段所在直線的距離 4
5. 點到折線集的最近距離 4
6. 判斷圓是否在多邊形內(nèi) 5
7. 求矢量夾角余弦 5
8. 求線段之間的夾角 5
9. 判斷線段是否相交 6
10.判斷線段是否相交但不交在端點處（內(nèi)交） 6
11.求線段所在直線的方程 6
12.求直線的斜率 7
13.求直線的傾斜角 7
14.求點關(guān)于某直線的對稱點 7
15.判斷兩條直線是否相交及求直線交點 7
16.判斷線段是否相交，如果相交返回交點 7

三、多邊形常用算法模塊
1. 判斷多邊形是否簡單多邊形 8
2. 檢查多邊形頂點的凸凹性 9
3. 判斷多邊形是否凸多邊形 9
4. 求多邊形面積 9
5. 判斷多邊形頂點的排列方向，方法一 10
6. 判斷多邊形頂點的排列方向，方法二 10
7. 射線法判斷點是否在多邊形內(nèi) 10
8. 判斷點是否在凸多邊形內(nèi) 11
9. 尋找點集的graham算法 12
10.尋找點集凸包的卷包裹法 13
11.判斷線段是否在多邊形內(nèi) 14
12.求簡單多邊形的重心 （HDU1115）15
13.求凸多邊形的重心 17
14.求肯定在給定多邊形內(nèi)的一個點 17
15.求從多邊形外一點出發(fā)到該多邊形的切線 18
16.判斷多邊形的核是否存在 19 

四、 圓的基本運(yùn)算
1 .點是否在圓內(nèi) 20
2 .求不共線的三點所確定的圓 21

五、矩形的基本運(yùn)算
1.已知矩形三點坐標(biāo)，求第4點坐標(biāo) 22

六、常用算法的描述 22

七、補(bǔ)充
1．兩圓關(guān)系： 24
2．判斷圓是否在矩形內(nèi)： 24
3．點到平面的距離： 25
4．點是否在直線同側(cè)： 25
5．鏡面反射線： 25
6．矩形包含： 26
7．兩圓交點： 27
8．兩圓公共面積： 28
9. 圓和直線關(guān)系： 29
10. 內(nèi)切圓： 30
11. 求切點： 31
12. 線段的左右旋： 31
13．公式： 32

附上一篇博客：計算幾何算法概覽 

 

zoj上的計算幾何題
Vol I
1010 by pandahyx
1032 by javaman
1037 by Vegetable Bird
1041 by javaman
1081 by Vegetable Bird
1090 by Vegetable Bird

Vol II
1104 by javaman
1123 by javaman
1139 by Vegetable Bird
1165 by javaman
1199 by Vegetable Bird

Vol V
1426 by Vegetable Bird
1439 by Vegetable Bird
1460 by Vegetable Bird
1472 by Vegetable Bird

Vol VI
1597 by Vegetable Bird

Vol VII
1608 by Vegetable Bird
1648 by Vegetable Bird

Vol XII
2102 by pandahyx
2107 by pandahyx
2157 by pandahyx

Vol XIII
2234 by pandahyx

Vol XIV
2318 by ahyangyi
2394 by qherlyt

Vol XV
2403 by Vegetable Bird