問題タブ [convex-hull]

こんにちは、また、私には 4 つのポイントがあり、4 つの三角形があると考えてください。これらの 4 つの三角形を、各ポイントが三角形内のポイントであるかどうかを確認するにはどうすればよいですか。ありがとう

O(n) のポイントのボロノイ図からポイント セットの凸包を計算するためのアルゴリズムが必要です。ボロノイ図はバウンディング ボックスに含まれ、二重接続エッジ リストとして格納されます。入力は、境界ボックス上に原点があるハーフ エッジです。

無限に長いボロノイ エッジを共有する場合、2 つの点が凸包上で隣接していることはわかっています。

Python コードで使用するために swig を使用して ac 関数をラップすると、属性エラーが発生します。私はチャップと一緒にうまく動作する他の機能を持っていますが、これが機能しない奇妙な理由があります:/

CGAL を使用して、すべての粒子の凸包を決定しようとしています (chap)。以下は chap 関数とトレースバックです。

点群のレンダリングに頭を悩ませようとしています。現在、私は Processing/Java を使用しており、QuickHull 3D を使用して疑似作業を行っていますが、効果に関しては、私が探していたものではありません。

これは私が持っているもののサンプルです: http://vimeo.com/17509829 Quickhull3D の Javadoc は次のとおりです: http://www.cs.ubc.ca/~lloyd/java/doc/quickhull3d/index.html

凸包法はメッシュのバウンディング タイプを識別するのに効果的ですが、私が探しているものは「シュリンク ラップ」効果に近いものではありません。2 つの頂点が QuickHull3D によって結合される距離を制限できるのではないかと期待していましたが、うまくいきませんでした。簡単に言えば、起こっていることはこれです：http://www.cs.sunysb.edu/~algorith/files/convex-hull.shtml

そして、G が G であることを大雑把に識別できるようにしたいと考えています。

これに取り組むための別のアプローチ、私が見逃している/認識していない2番目のステップ、またはそれらの頂点を結合するための距離を実際に制限する方法を誰かが推奨できますか? それは凸包アプローチの要点ではないことを知っているので、それを尋ねるのは恥ずかしがり屋ですが、どんな助けもいただければ幸いです。

ありがとう！

私は、2Dの任意のポイントのセットのモーショントラッキングなど、いくつかのコンピュータビジョン技術を研究して実装しようとしています。私は、知っているポイントのセットに対して凸包を作成し、マップできる可能性のあるポイントのセットに対して凸包を作成しています。2つの船体がどれほど似ているかを比較するのに役立つリソースを探しています。十分に似ている場合は、実際に互いにどのようにマッピングされますか？このスタイルのアルゴリズムと、この分野で潜在的により複雑なアルゴリズムについて説明している優れたリソース/書籍をどこで見つけるかについての情報をいただければ幸いです。

私は2つの凸包を持っていますが、誰かが良いアルゴリズムやリソースを知っているかどうか疑問に思っていました.1つの凸包の位置を別の凸包と比較する方法についてのアイデアはありますか?

距離、方向、および類似性は素晴らしい出発点です。

GPS クラスター (互いに接近している多くの GPS ポイントを含む) があり、その外側のポイントの周りにポリゴンを作成することで、それを場所として識別したいと考えています。1 つの方法は Convex Hull で、Javascript での実装を探しています。

何か案が？

関連：ポリゴンの分解-凸多角形を形成するための凹点の削除

私は次のことを行うためのアルゴリズムを探しています：

入力は2Dポイントの配列です（P0 _… PN _-1）。配列の長さNは変化します（3≤N<∞）任意のM≤Nに対して、頂点が_P0 …PM _-1
の順序 である凸多角形が存在する場合と存在しない場合があります。

エッジは必ずしもアレイ内の隣接するペアではないことに注意してください。

この凸多角形が存在するような最大Mを見つけるための最も効率的なアルゴリズムは何ですか？

私の現在のアルゴリズムは非常に非効率的です。M = 3、M = 4、M = 5などでテストし、船体を計算してから、すべてのP0 _… P _​​M-1が船体の頂点であることをテストします。そうでない場合は、ループから抜けてM-を返します。 1.1。

例1：[(-2,2), (2,2), (-2,-2), (-1,1)]

結果：3（最初の3つのポイントは三角形を形成しますが、P ₃ =(-1,1)を追加するとポリゴンが非凸になるため）

例2：[(-2,2), (2,2), (-2,-2), (1,-1)]

結果：4（配列内の4つのポイントすべてから凸四角形を作成できるため）

例3の更新[(-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1)]
： 結果：4。

この例は、提供されたすべての点の凸包を取得して、そのサブセットである接頭辞を見つけるだけでは不十分である理由を示しています。(3,-3)最初の5つのポイントで構成される凸多角形の一部にすることはできません。これは、前のポイント(2,-1)が船体上に存在しなくなるためです。しかし、それは(3,-3)6つのポイントすべての船体にあり、そうではないにもかかわらず、拒否されなければならないということ(2,-1)です。

無効な入力の例：

• [(-1,-1), (0,0)]（ポイントが少なすぎる）
• [(-1,-1), (0,0), (1,1), (1, -1)]（最初の3つのポイントは同一線上にあります。アルゴリズムがこれを処理できるとは思いません。）

一連の 2D ポイントの凸包を作成したいと思います (Python で)。役に立ったいくつかの例を見つけましたが、実装できなかった追加機能があります。私がやりたいことは、凸包を作成することですが、境界に十分に「近い」場合は内部の点を取得できるようにします。下の図を参照してください -> シータ < x 度の場合、その内点が船体に追加されます。

私の考えやテストからわかったように、明らかにこれは物事をもう少し複雑にする可能性があります。たとえば、内部ポイントが追加された場合、別の内部ポイントを追加できる可能性があります。

ここで作業するポイントの数は比較的少ないので、速度はあまり問題になりません。迅速なアルゴリズムよりも堅牢なアルゴリズムが必要です。

誰かがそのような例を知っているか、どこから始めるべきか正しい方向に私を向けることができるかどうか疑問に思っています. ありがとう。

いくつかの 2D ポイントが指定されており、それらのポイントを使用してポリゴンを描画したいと考えています。このポリゴンは指定されたすべてのポイントを通過する必要があります。これは、ポリゴンの内側または外側にそのようなポイントがないことを意味します。

例: (0,0)、(1,1)、(-1,-1)、(-1,1)、(1,-1) のような点があり、多角形を描きたい場合それらを使用すると、ポイント配列は次の方法でソートする必要があります。

(1,1) -> (1,-1) -> (-1,-1) -> (-1,1) -> (0,0) -> (1,1) または

(1,1) -> (0,0) -> (-1,1) -> (-1,-1) -> (1,-1) -> (1,1)

しかし、それはできません：

(1,1) -> (0,0) -> (-1,-1) -> (-1,1) -> (-1,1) -> (1,-1) -> (1, 1)

ポリゴンを描画するために、drawLine関数を使用して、あるポイントから別のポイントまで、最後に最後のポイントから最初のポイントまで線を描画しています。

これに利用できるアルゴリズムまたはコードはありますか?

ありがとう！！