我是C#的新手,並且很難計算凸包。 C#是否有這樣的數學庫?如果不是,那麼我想我只需要實現我自己的。凸面船體庫
凸面船體庫
回答
MIConvexHull - https://designengrlab.github.io/MIConvexHull/ - 是C#中的高性能凸包實現,支持更高維的凸包。 LGPL許可證。
下面是我用Monotone Chain算法a.k.a. Andrew的算法編寫的2D凸包算法。
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;
}
它依賴於一些假定存在的事情,詳見我的blog post。
下面是對Qwertie答案中使用的相同Java源代碼的C#的音譯,但沒有依賴於具有雙字段的Point類之外的非標準類。
class ConvexHull
{
public static double cross(Point O, Point A, Point B)
{
return (A.X - O.X) * (B.Y - O.Y) - (A.Y - O.Y) * (B.X - O.X);
}
public static List<Point> GetConvexHull(List<Point> points)
{
if (points == null)
return null;
if (points.Count() <= 1)
return points;
int n = points.Count(), k = 0;
List<Point> H = new List<Point>(new Point[2 * n]);
points.Sort((a, b) =>
a.X == b.X ? a.Y.CompareTo(b.Y) : a.X.CompareTo(b.X));
// Build lower hull
for (int i = 0; i < n; ++i)
{
while (k >= 2 && cross(H[k - 2], H[k - 1], points[i]) <= 0)
k--;
H[k++] = points[i];
}
// Build upper hull
for (int i = n - 2, t = k + 1; i >= 0; i--)
{
while (k >= t && cross(H[k - 2], H[k - 1], points[i]) <= 0)
k--;
H[k++] = points[i];
}
return H.Take(k - 1).ToList();
}
}
我比較了許多Convex Hull算法/實現與所有提供的代碼。一切都包含在CodeProject文章中。
算法相比:
- 單調鏈
- MiConvexHull(Delaunay三角和沃羅諾伊目)
- 格雷厄姆掃描
- 陳
- Ouellet的(礦)
文章:
- 2017年10月13日 - 試驗檯與5月份的算法/實現:Fast and improved 2D Convex Hull algorithm and its implementation in O(n log h)
- 2014年5月20日 - 解釋我自己的算法:A Convex Hull Algorithm and its implementation in O(n log h)
@ephraim,非常感謝您向我彙報。我目前正在看這種情況! –
@ephraim,你在哪裏有錯誤,在哪篇文章?我無法用我最新文章的代碼重現它?你有什麼暗示我可以自己看到錯誤嗎? 1 000 000個測試用4個點(這應該導致1個象限,偶爾有1個點),所有的Ouellet公司都沒有錯誤/異常? –
@ephraim,找到了Bug!十分感謝!這只是在第一篇文章。有更正的文章應該很快就可以使用(將在15分鐘內完成,並且在CodeProject批准的時候可以使用〜大概今天) –
- 1. 凸面船體誤解?
- 2. 什麼是凸面船體技巧?
- 3. Python - 具有一些允許的內部點的凸面船體
- 4. 在opencv中查找非凸(或convac)船體
- 5. pyipy.spatial.Delaunay的Python凸包,如何清理船體內的點?
- 6. 船體表面由點雲生成
- 7. 凸出的船體或給定的一組點與最低可能的周長
- 8. 我在解決方案中缺少什麼?凸的船體查找算法
- 9. CGAL:在3D中簡化凸多面體
- 10. 如何確定多面體是凸的?
- 11. 簡化凹船體
- 12. 船體着色器術語
- 13. 正交船體算法
- 14. 如何計算凸多面體和另一個多面體之間的交點?
- 15. 三維凸體內的體素
- 16. 凹面船體在邊界上取多邊形的所有點
- 17. wxNotebook活動頁面凸顯
- 18. 3D中的凸面Perl Perl
- 19. 找到一個點是否在一組凸點內部而不計算船體本身
- 20. 凸多面體區域中的隨機點
- 21. 球體表面上的(經度,緯度)點凸殼
- 22. 生成複雜(非凸)多面體UV映射
- 23. 對凸多面體進行形狀鑄造膠囊
- 24. D3力佈局與幾何船體
- 25. 合併船體代碼示例
- 26. 剪輯d3 voronoi與d3船體
- 27. 與船
- 28. 船體和箱體之間的最近距離
- 29. 凸顯CSS活動面板沒有JavaScript
- 30. 凹凸類別上的方面barplot
在谷歌的第一個命中'C#凸包' - http://www.codeproject.com/Articles/29275/Convex-Hull。你有做過什麼研究嗎? –
是的,我已經看到了。我的問題是,如果C#有一個現有的內置庫... – Owen