問題タブ [convex-hull]

ランダムな順序でポイントの配列があり、すべてのポイントを通過する多角形を (隣接するすべてのペアが辺を表すようにソートすることによって) 見つける必要があり、その辺はもちろん交差していないとします。

ポイントを選択し、その下にあるすべてのポイントを最終的な配列に追加して、左から右に並べ替えることでそれを実行しようとしました。次に、その上にあるすべてのポイントを追加し、右から左に並べ替えます。

自己交差を避けるために、ポイントを追加して自然に並べ替えることができると言われました..しかし、それを理解することはできません。これを行う簡単な方法は何ですか？

コンテストで出題される問題があります。私はすでにこの問題を動的プログラミングとその複雑さで解決しましたが、O(n^2)より効率的な方法を探しています。動的プログラミングが凸包で最適化できることはすでに見ました。何か提案はありますか。アドバイスありがとう。

ここで点を楕円で囲むことについての議論を見てきましたが、一連の楕円を 1 つの楕円で囲むアルゴリズムはありますか? セットを閉じる楕円を近似するために焦点を使用できますか?

互いに設定された距離ですべてのポイントを見つけるアルゴリズムはありますか? または接触しているすべての長方形？

平面 (緯度/経度座標系、特定の制限) を nxn のサンプル四角形に分割し、各四角形は 0 から 7 の値を取得します。各値の島を表示できるようにする必要があります。n > 100 - 15000 になる可能性があります。

私は非常にブルートフォースなコードを書きましたが、非常に大雑把な長方形しか得られませんでした...

私の入力例:

上記は、長方形内のポイントを使用して定義されています (各 1 と 2 およびその他は、いくつかのサンプリングを通じて取得した長方形です...)それぞれの地域。

凸包アルゴリズムを使用して領域を取得できることを発見しました-長方形（またはそれらの中心点）を領域に適切に分離できれば。

関数への入力では、同じメトリックを持つ四角形のみを取得します。

例：

いくつかのアルゴリズムを見つけて、接触している長方形、または互いに特定の距離にある点を別々のセット (絶対座標を持っている) で取得できるようにしたいので、凸包アルゴリズムを結果セット。

長方形はサンプリングから作成されるため、幅と高さは同じです。

そんなことありますか？

私のコードは VB.NET ですが、C#、または任意の言語または疑似コードが役立ちます。

どうもありがとうございました。

編集：

私はあらゆる種類のテストを持っています

ここで、distance_lat と distance_lon はそれぞれ dim_lat/10、dim_lon/10 です。

ポイントのコレクションから凸包を計算する方法は?

C# での凸包アルゴリズムの実装を探しています

凸包を視覚化するための簡単なハックに scipy (0.10.1) を使用しようとしています。

次のコードを使用して、凸包を取得できます。

結果の配列は次のようになります。

数字は頂点のインデックスです。私の問題は、それらが注文されていないことです。KML で簡単に視覚化するには、CW または CCW の順序にする必要があります。

scipy.spatial に適切な時計回りの順序を計算させる簡単な方法はありますか?

各点の各座標がp/qの形式の有理数であり、pとqの値が制限されている場合、平面内のn点の凸包をO（n）時間で計算できることを示します。

注：これは宿題の問題です。どういうわけかすべてのポイントのスキャンを回避することで、JarvisMarchを使用することを考えることができます。たぶんこれは、次の点がどこにあるかを確認するために（合理的な条件を使用して）固定された方向に光線を投げることによって行うことができます。

BackgroundsubtractorMOG()基本的にマスクを抽出して前景を分離するためにを使用しています。次にconvexHull()、マスクを使用して移動オブジェクトの位置を特定します。

しかし、私は次のエラーが発生しています:

番号を確認しました。マスク行列を型キャストするだけでなく、要素の。しかし、エラーはまだ続きます。以前に同様の問題に遭遇した人はいますか。OpenCV 2.4.2 を使用しています

私は凸包アルゴリズムを使用して、不規則な形状の輪郭を見つけました。それは十分ではありませんが...

おそらく、私が持っている形状が凸状であるとは保証できないためです...

一連の長方形があり、輪郭の外側にあるすべての点を取得できるようにしたいのですが、輪郭の点を捨てないようにします。

凸包アルゴリズムはうまく機能しますが、右の例のように機能するため、輪郭に関する情報が失われます。

左のバージョンに近く、外側のコーナーを保持し、内側のポイントのみを削除するものが必要です...

そのようなアルゴリズムはありますか？

または、このような形状 (ポリゴン) を凸形状に分割して、凸包アルゴリズムが適切に処理できるようにする方法はありますか?

リンクからリンクへと、Hertel-Mehlhorn Algorithm のようなある種のアルゴリズムを設定する方法を見つけようとしてきましたが、この状況で交差する線がどのように使用されるかはわかりません...

ご提案ありがとうございます。

画像モーメントに基づいて伸びを計算するこの方法を見つけました

凸包の伸びを計算するにはどうすればよいですか？

ここで、「unicocnt」は​​、findcontoursで取得された輪郭です。