問題タブ [convex-hull]

私は頂点の大きな配列を持っています.それらのいくつかはエッジであり、いくつかは冗長であり(シェイプ内)、それらを削除したいと思います.

私が考えることができる最も単純なアルゴリズムは、それらが他のものによって形成された形状に当たるかどうかを1つずつチェックすることです. しかし、それは非常に遅いアルゴリズムでなければなりません。

エッジから 1 つ (例ごとに原点から最も遠いもの) を選択し、この開始点からの最長パスを計算することを考えました...エッジ パスを取得する必要がありますよね?

なにか提案を？

クラス割り当て用の 2D 凸包関数を作成する必要があり、割り当てが提供するよりも堅牢なテスト ケースが必要です。ソリューションを使用した大規模なテスト ケース (25 < n < 100) を知っている人はいますか?

平面上に約1000個の奇数点があるとします。

次に、円の半径にまったく影響を与えないポイント、つまり凸包が通過しないポイント（いくつかのアルゴリズムのいずれかを使用）を破棄することができると思います。これは私たちに重要なポイントを残します。

これから、その最小半径の円を見つけるために何ができるでしょうか？

円に対してどのように実行できるかを理解したら、これを楕円に対して一般化することを検討しています。

省略記号に変更できるように、「公開ソースコード」へのリンクがあれば役立ちます。

I have a set of points. I want to separate them into 2 distinct sets. To do this, I choose two points (a and b) and draw an imaginary line between them. Now I want to have all points that are left from this line in one set and those that are right from this line in the other set.

How can I tell for any given point z whether it is in the left or in the right set? I tried to calculate the angle between a-z-b – angles smaller than 180 are on the right hand side, greater than 180 on the left hand side – but because of the definition of ArcCos, the calculated angles are always smaller than 180°. Is there a formula to calculate angles greater than 180° (or any other formula to chose right or left side)?

4 つの 2D ポイントの凸包を計算するアルゴリズムが欲しいです。一般化された問題のアルゴリズムを見てきましたが、4 点の簡単な解決策があるのだろうかと思います。

ユーザーが好きな形の輪郭を描くことができる地図を作ろうとしています。しかし、ユーザーがポリゴンの線を交差させるポイントを選択し、含めたい領域を除外できるという問題が発生しています。

私が話していることを確認するには、このページに移動して次の手順を実行してください。

1. 4点をクリックして、ボックスの4つの角を作成します
2. ボックスの境界をさらに定義するには、作成した4つのポイントのそれぞれの間をクリックします。
3. クリック完了

次のように表示されます。

この問題を解決する簡単な方法はありますか、それとも基本的にここで「巡回セールスマン」タイプの状況に対処していますか？すべてのロジックはjavascriptで行われるため、私がこれをどのように行っているかを確認したい場合は、「ソースを表示」してください。

ボリューム内のすべてのボクセルに1があり、ボリュームの外側にあるすべてのボクセルに0があるバイナリマスクを生成したいと思います。ボリュームは、3D座標のセットの周りの凸包によって定義されます（<100;一部の座標はボリューム内にあります）。

CONVHULLNを使用して凸包を取得できますが、それをバイナリマスクに変換するにはどうすればよいですか？

凸包を通過する良い方法がない場合、バイナリマスクを作成する方法について他に何か考えがありますか？

平面上の n 点を指定します。いいえ 3 は同一線上にあります。

数 k が与えられます。

k ポイントの凸包が、k ポイントのサブセットの任意の凸包の中で最小の周囲長を持つように、k ポイントのサブセットを見つけます。

O(n^kk log k) で実行される単純なメソッドを考えることができます。(サイズ k のすべてのサブセットの凸包を見つけ、最小値を出力します)。

これはNPの問題だと思いますが、還元に適したものが見つかりません。

誰でもこの問題についてアイデアを持っていますか?

例、

結果：

このセットには 3 つのポイントが含まれているため、結果の凸包と周囲は、他の 3 つのポイントのセットよりも小さくなります。

複雑な多角形の凸包を見つけるための最悪の O(n log n) アルゴリズムと、単純な多角形の凸包を見つけるための最悪の O(n) アルゴリズムがあることは知っています。複雑な多角形の凸包を見つけるための最悪の O(n) アルゴリズムはありますか?

複雑な多角形は、線分が交差する可能性がある多角形です。複雑な多角形の凸包を見つけることは、点の順序付けられていないリストの凸包を見つけることと同じです。

こんにちは、ブラインド凸包には o(n^4) があることは知っていますが、そのコードを見たことがありません! コードがあるサイトはありますか？ありがとう