public static IListSource<Point> ComputeConvexHull(List<Point> points, bool sortInPlace = false)
{
if (!sortInPlace)
points = new List<Point>(points);
points.Sort((a, b) =>
a.X == b.X ? a.Y.CompareTo(b.Y) : a.X.CompareTo(b.X));
// Importantly, DList provides O(1) insertion at beginning and end
DList<Point> hull = new DList<Point>();
int L = 0, U = 0; // size of lower and upper hulls
// Builds a hull such that the output polygon starts at the leftmost point.
for (int i = points.Count - 1; i >= 0 ; i--)
{
Point p = points[i], p1;
// build lower hull (at end of output list)
while (L >= 2 && (p1 = hull.Last).Sub(hull[hull.Count-2]).Cross(p.Sub(p1)) >= 0) {
hull.RemoveAt(hull.Count-1);
L--;
}
hull.PushLast(p);
L++;
// build upper hull (at beginning of output list)
while (U >= 2 && (p1 = hull.First).Sub(hull[1]).Cross(p.Sub(p1)) <= 0)
{
hull.RemoveAt(0);
U--;
}
if (U != 0) // when U=0, share the point added above
hull.PushFirst(p);
U++;
Debug.Assert(U + L == hull.Count + 1);
}
hull.RemoveAt(hull.Count - 1);
return hull;
}
4 回答
这是我使用Monotone Chain算法编写的二维凸包算法,a.k.a . 安德鲁的算法 .
它依赖于假设存在的一些东西,详见我的blog post .
MIConvexHull - https://designengrlab.github.io/MIConvexHull/ - 是C#中的高性能凸包实现,也支持更高维的凸包 . LGPL许可证 .
我将许多Convex Hull算法/实现与所提供的所有代码进行了比较 . 一切都包含在CodeProject文章中 .
算法比较:
单调链
MiConvexHull(Delaunay三角剖分和Voronoi网格)
格雷厄姆扫描
陈
Ouellet(我的)
文章:
2017-10-13 - 具有may算法/实现的测试平台:Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)
2014-05-20 - 解释我自己的算法:A Convex Hull Algorithm and its implementation in O(n log h)
下面是对Qwertie的答案中使用的相同Java源代码的C#的音译,但没有依赖于具有双字段的Point类之外的非标准类 .