作者kaze (就軌擠壘)
看板C_Sharp
標題[問題] ConvexHull Algorithm
時間Tue Mar 23 23:05:03 2010
在網路上有看到一個演算法
http://www.csie.ntnu.edu.tw/~u91029/ConvexHull.html
裡面的"Jarvis' March （ Gift Wrapping Algorithm ）"
附上原始檔在下面
標黃色的部份 應該有錯誤
我覺得應該是 if (cross(
CH[m-1], P[i], P[next]) < 0)
但是如果選到"0"這個點時
會變成 if (cross(CH[m-1], P[i], P[next]) < 0) 永遠都跑不進去
比如說我依序找到的邊緣點是 3 -> 2 -> 8 -> 0 -> 0 -> 0 -> 0
選到 0 以後在也沒有點會被選到
因為cross(P[0], P[i], P[0])都是0 不管P[i]為何
請問該怎麼改呢?
--
1. // P為平面上的那些點。這裡設定為剛好100點。
2. // CH為凸包上的點。這裡設定為照逆時針順序排列。
3. struct Point {int x, y;} P[100], CH[100];
4.
5. // 小於。用以找出最低最左邊的點。
6. bool compare(Point& a, Point& b)
7. {
8. return (a.y < b.y) || (a.y == b.y && a.x < b.x);
9. }
10.
11. // 向量OA corss 向量OB。大於零表示從OA到OB為順時針旋轉。
12. double cross(Point& o, Point& a, Point& b)
13. {
14. return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
15. }
16.
17. void findConvexHull()
18. {
19. /* 用最低最左邊的點當作是起點。起點可以用凸包上面任意一個點。 */
20.
21. int s = 0;
22. for (int i=0; i<100; ++i)
23. if (compare(P[i], P[s]))
24. s = i;
25.
26. /* 包禮物，逆時針方向。 */
27.
28. CH[0] = P[s]; // 紀錄起點
29.
30. for (int m=1; true; ++m) // m 為凸包頂點數目
31. {
32. /* 找下一個點，最外圍的點。*/
33.
34. int next = 0; // 窮舉所有點，找出位於最外圍的一點
35. for (int i=0; i<100; ++i)
36.
if (cross(CH[m], P[i], P[next]) < 0)
37. next = i;
38.
39. if (next == s) break; // 繞一圈後回到起點了
40. CH[m] = P[next]; // 紀錄方才所找到的點
41. }
42. }
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 163.22.18.83