私はC#を初めて使用しており、凸包を計算するのに苦労しています。 C#にはこれのための何らかの種類の数学ライブラリがありますか?そうでなければ、私は自分自身を実装しなければならないと思う。凸包のライブラリ
凸包のライブラリ
答えて
MIConvexHull -https://designengrlab.github.io/MIConvexHull/ - は、C#の高性能凸包実装であり、高次元凸包もサポートしています。 LGPLライセンス。
ここでは、Monotone Chainアルゴリズム、a.k.a Andrew's Algorithmを使用して書いた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#への翻字ですが、非標準クラスには依存しません。
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();
}
}
私は提供されたすべてのコードで多くの凸包アルゴリズム/実装を比較しました。すべてはCodeProjectの記事に含まれています。
アルゴリズムを比較:
- モノトーンチェーン
- MiConvexHull(ドロネー三角形分割をし、ボロノイメッシュ)
- 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、どこの記事でバグがありましたか?私は最新の記事のコードでそれを再現できないのですか?どのように自分自身でバグを見ることができるかについてのヒントはありますか?すべてのOuelletアルゴリズムで、エラー/例外なしで4点(1分に1点ずつ)を1 000 000テストしますか? –
@ephraim、バグが見つかりました!どうもありがとうございます!それは最初の記事にすぎませんでした。訂正の記事はすぐに利用可能になるはずです(15分でパイプラインに入り、CodeProjectによって承認されたときに利用可能になります〜今日) –
- 1. 凸包とSciPy
- 2. コンピュータビジョン - OpenCVによる凸包および凸欠陥のフィルタリング
- 3. 凸包のアスペクト比の推定
- 4. アンドロイドJavaのOpenCVの2.4凸包convexdefect
- 5. 球の表面上の(経度、緯度)点の凸包
- 6. scipy.spatialの凸包ルーチンは、元の点集合を返します
- 7. 凸包 - 点の順番を決定する
- 8. Java線形代数/凸最適化ライブラリ
- 9. JavascriptでGPSポイントの凸包を見つける/作成する方法
- 10. eclipse CDT glibライブラリの包含エラー
- 11. openCV関数を使って凸包領域を計算するには?
- 12. 凸最適化のためのdotnetライブラリは何ですか?
- 13. 凸3Dポリゴンオブジェクト
- 14. 回転キャリパーを使用したXNAの凸包の向き付き境界ボックスの検索
- 15. 単純凸と単純非凸多角形の差
- 16. 2d凸包の面から点が見えるかどうかを確認する
- 17. 静的ライブラリのヘッダーファイルの包含と可視性iOS
- 18. 緯度と経度を指定して地球凸包ポリゴン領域を計算する
- 19. 凸多面体の重心
- 20. 簡単で包括的なAjaxウィジェットを設定したjavascriptライブラリ
- 21. 主成分凸多角形
- 22. 凸ボーダートップとボーダーボトムとCSS?
- 23. 2つの凸多角形の交点
- 24. OpenGLの非凸多角形の概要
- 25. Cudaの凸多角形アルゴリズムですか?
- 26. ボロノイ図からの凸面船体
- 27. 凸多角形の生成方法
- 28. Pythonのリスト内包1つの宣言と2つの内包
- 29. Pythonのリスト内包
- 30. Pythonのリスト内包
'C#の凸包のためのGoogleでの非常に最初のヒットを' - http://www.codeproject.com/Articles/29275/Convex-Hull。あなたはどんな研究をしましたか? –
はい、私はそれを見ました。私の質問は、C#にそれのためのライブラリが組み込まれている場合でした... – Owen