格雷厄姆扫描问题点数很高

我的格雷厄姆扫描算法有一个问题，当我的列表有很多分数，但每次都很好，点数少。 我做了一些截图：

工作：（300分）

不工作（5000分）

角度计算：

public static double angle(MyVector3D vec1, MyVector3D vec2) { return Math.Atan2(vec2.Y - vec1.Y, vec2.X - vec1.X) * 180 / Math.PI; } 

极角分选点取决于最大Y点：

 //bubblesort private void sortList() { double temp = 0.0; MyVector3D tempVector = new MyVector3D(); for (int i = 1; i < points.Count; i++) { for (int j = 1; j < points.Count - 1; j++) { if (angles[j] < angles[j + 1]) { temp = angles[j + 1]; tempVector = points[j + 1]; angles[j + 1] = angles[j]; points[j + 1] = points[j]; angles[j] = temp; points[j] = tempVector; } } } 

ccw方法：

 private double ccw(MyVector3D vec1, MyVector3D vec2, MyVector3D vec3) { // ccwTest = ((vec2.X - vec1.X) * (vec3.Y - vec1.Y)) - ((vec2.Y - vec1.Y) * (vec3.X - vec1.X)); return ((vec2.X - vec1.X) * (vec3.Y - vec1.Y)) - ((vec2.Y - vec1.Y) * (vec3.X - vec1.X)); } 

格雷厄姆扫描算法：

 for (int i = 2; i  0) { if (M > 1) { points.RemoveAt(M); M -= 1; i--; } else if (i == points.Count - 1) { break; } else { i += 1; } } //goodPoints.Add(points[M]); //listBoxInfos.Items.Add("g" + (int)points[M].X + "," + (int)points[M].Y + "," + 0); //listBoxInfos.Items.Add("ccw" + ccwTest); M += 1; } 

我真的不知道为什么我的程序会在800多点上爆炸……这很难调试，因为算法在300,400,500点时非常有效。

Ty的信息。

Answer 1

维基百科上的算法被打破了。 它不处理多个点彼此共线并且具有最小点的情况 。 例如，以下测试用例将失败：

  Vector3[] points3 = new Vector3[] { new Vector3( 1, 1, 0), new Vector3( 5, 5, 0), new Vector3( 3, 3, 0), new Vector3( 2, 2, 0), new Vector3( 1, 1, 0), new Vector3( 1, 10, 0), }; 

问题在于，当沿着点行进时，如果该点位于船体的最后两个点之间，则可能需要丢弃当前点而不是延长船体或替换船体上的最后一个点。 （这只有在点与最小点共线时才会发生，否则前面的角度排序会阻止这种双后退。）在所示的伪代码中没有逻辑。

我还认为维基百科算法可能会严重处理浮点舍入错误。 特别是检查ccw <= 0看起来有问题。

这是尝试清理维基百科算法。 我不得不摆脱（模糊地说是kludgy）“sentinal point”，因为如果所有的点都是水平对齐的，那么它将基本上随机选择：

  public static IList GrahamScanCompute(IList initialPoints) { if (initialPoints.Count < 2) return initialPoints.ToList(); // Find point with minimum y; if more than one, minimize x also. int iMin = Enumerable.Range(0, initialPoints.Count).Aggregate((jMin, jCur) => { if (initialPoints[jCur].Y < initialPoints[jMin].Y) return jCur; if (initialPoints[jCur].Y > initialPoints[jMin].Y) return jMin; if (initialPoints[jCur].X < initialPoints[jMin].X) return jCur; return jMin; }); // Sort them by polar angle from iMin, var sortQuery = Enumerable.Range(0, initialPoints.Count) .Where((i) => (i != iMin)) // Skip the min point .Select((i) => new KeyValuePair(Math.Atan2(initialPoints[i].Y - initialPoints[iMin].Y, initialPoints[i].X - initialPoints[iMin].X), initialPoints[i])) .OrderBy((pair) => pair.Key) .Select((pair) => pair.Value); List points = new List(initialPoints.Count); points.Add(initialPoints[iMin]); // Add minimum point points.AddRange(sortQuery); // Add the sorted points. int M = 0; for (int i = 1, N = points.Count; i < N; i++) { bool keepNewPoint = true; if (M == 0) { // Find at least one point not coincident with points[0] keepNewPoint = !NearlyEqual(points[0], points[i]); } else { while (true) { var flag = WhichToRemoveFromBoundary(points[M - 1], points[M], points[i]); if (flag == RemovalFlag.None) break; else if (flag == RemovalFlag.MidPoint) { if (M > 0) M--; if (M == 0) break; } else if (flag == RemovalFlag.EndPoint) { keepNewPoint = false; break; } else throw new Exception("Unknown RemovalFlag"); } } if (keepNewPoint) { M++; Swap(points, M, i); } } // points[M] is now the last point in the boundary. Remove the remainder. points.RemoveRange(M + 1, points.Count - M - 1); return points; } static void Swap(IList list, int i, int j) { if (i != j) { T temp = list[i]; list[i] = list[j]; list[j] = temp; } } public static double RelativeTolerance { get { return 1e-10; } } public static bool NearlyEqual(Vector3 a, Vector3 b) { return NearlyEqual(aX, bX) && NearlyEqual(aY, bY); } public static bool NearlyEqual(double a, double b) { return NearlyEqual(a, b, RelativeTolerance); } public static bool NearlyEqual(double a, double b, double epsilon) { // See here: http://floating-point-gui.de/errors/comparison/ if (a == b) { // shortcut, handles infinities return true; } double absA = Math.Abs(a); double absB = Math.Abs(b); double diff = Math.Abs(a - b); double sum = absA + absB; if (diff < 4*double.Epsilon || sum < 4*double.Epsilon) // a or b is zero or both are extremely close to it // relative error is less meaningful here return true; // use relative error return diff / (absA + absB) < epsilon; } static double CCW(Vector3 p1, Vector3 p2, Vector3 p3) { // Compute (p2 - p1) X (p3 - p1) double cross1 = (p2.X - p1.X) * (p3.Y - p1.Y); double cross2 = (p2.Y - p1.Y) * (p3.X - p1.X); if (NearlyEqual(cross1, cross2)) return 0; return cross1 - cross2; } enum RemovalFlag { None, MidPoint, EndPoint }; static RemovalFlag WhichToRemoveFromBoundary(Vector3 p1, Vector3 p2, Vector3 p3) { var cross = CCW(p1, p2, p3); if (cross < 0) // Remove p2 return RemovalFlag.MidPoint; if (cross > 0) // Remove none. return RemovalFlag.None; // Check for being reversed using the dot product off the difference vectors. var dotp = (p3.X - p2.X) * (p2.X - p1.X) + (p3.Y - p2.Y) * (p2.Y - p1.Y); if (NearlyEqual(dotp, 0.0)) // Remove p2 return RemovalFlag.MidPoint; if (dotp < 0) // Remove p3 return RemovalFlag.EndPoint; else // Remove p2 return RemovalFlag.MidPoint; } 

顺便说一句，你的算法在几个地方的顺序为n平方：

1. bubblesort是O（N ^ 2）的阶数
2. 在找到船体时移除点而不是将它们交换到列表的前面可以是O（N ^ 2），因为所有后续点都必须向下移动。

让我知道如果它解决了你的问题，我已经测试了一下但不完全。

Answer 2

按照这个： http ： //en.wikipedia.org/wiki/Graham_scan和其他人，你的格雷厄姆扫描算法实现至少有2个问题，我认为你用较低的数字’变得幸运’：

1）你在你的外表中增加我和你的其他地方，即通常你正在跳过测试每一点。

2）我不相信你的移除失败点的方法，是的，这个点不在船体’这里’但是可能是船体上的一个点，你需要移动到交换这些点或使用堆栈基于方法。

Answer 3

我想这超出了评论部分的范围，所以我将从中得出答案：

设点[M-1]与点[i]处于相同的坐标。

然后知道：ccw =（（vec2.X – vec1.X）*（vec3.Y – vec1.Y）） – （（vec2.Y – vec1.Y）*（vec3.X – vec1.X））对应于vec1的[M-1]和对应于vec3的points [i]。

用vec1替换vec3得到：ccw =（（vec2.X – vec1.X）*（vec1.Y – vec1.Y）） – （（vec2.Y – vec1.Y）*（vec1.X – vec1.X ））我们可以清楚地看到这将是== 0.因为你肯定如果ccw == 0这些点将保留在凸包中，那么这将使你的船体的一部分成为两条完全重叠的线，除非我弄错了某处。

---

谢谢。 我检查了算法，你是对的kugans。 问题是当ccw == 0时，但主要问题是如何消除ccw == 0的点，这些点不是凸包的一部分并保留那些，因为同一矢量中的3个点可能是凸包的一部分。 知道怎么解决这个问题吗？

（你可能想看看dbc的代码，但这是我的答案）

我认为您不想在凸包中与ccw == 0保持任何联系。 当ccw == 0时，矢量之间的角度为180度或0度。

0deg的情况就像我在回答的开头所说的那样（这些点实际上不需要重叠，更容易以这种方式进行演示）。

至于180deg的情况，你需要做一些额外的代码。 我引用dbc：

如果该点位于船体的最后两个点之间，则可能需要丢弃当前点而不是延长船体或更换船体上的最后一个点。

如果你想让测试变得更容易，你也可以提取所有凸包点的位置并重放那些。