作者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