問題タブ [non-convex]

2D 非凸図形の優れた衝突検出アルゴリズムに関する情報 (または記事の提案) を教えてください。

ありがとう！

単純な非凸多角形の一連の点があるという問題があります (用語が正しいことを願っています)。しかし、ポイントは必ずしも順番通りではありません (つまり、時計回りまたは反時計回り)。Flash の描画 API で塗りつぶし領域を正しく描画するには、これらのポイントを端に沿って順番に進行させる必要があります (最終的に始点に接続するため)。

デカルト座標のリストを時計回りまたは反時計回りに並べ替えて、「ペンを持ち上げる」ことなくポイントからポイントへとシェイプを描画できる方法はありますか?

多角形の 4 点をソートするという投稿を 1 つ見ましたが、4 点だけの特殊なケースだったと思います。私の図形には最低 6 つのポイントがあります。リストでは、各エントリが少なくとも 1 つの隣接エントリ (前のポイントまたは次のポイント) に (時計回りまたは反時計回りの順序で) 隣接していることが保証されます。例: A, B, D, C... または B, A, D, C... ですが、 A, C, B, D... ではありません (A, B, C のいずれかになるように並べ替える必要があります、D または D、C、B、A)。この投稿を見つけましたが、回答がないようです:ポイント リストをポリゴンに並べ替える

CPU のパフォーマンスが問題です。しかし、「遅い」解決策でさえ、実装と理解が簡単であれば (次のプログラマーにとって)、効果的なキャッシュメカニズムを考え出すことができれば問題ないかもしれません。

私がしなければならないことの例を示すために写真を添付し​​たいと思いますが、まだ評判ポイントが 10 ありません。とにかく、このポリゴンのリストで 3 番目の例の頂点を並べ替える手段があれば、それは完璧です: http://upload.wikimedia.org/wikipedia/commons/1/1f/Assorted_polygons.svg

私は本当にすべての助けに感謝します、ありがとう!

編集:確かに座標系の中心点を保証できます-それは画面の中心になります。すべてのポイントは 0 と画面の幅/高さの間になります (原点は明らかに幅/高さ / 2 です)。ポリゴンの内部に原点が含まれているとは限りません。まれな例外ですが、説明する必要があります。

ところで、私のセグメントが必ずしも順番どおりではない理由は、それらが Conrec: http://paulbourke.net/papers/conrec/を使用して生成されているためです(それらは等高線です)。以下を使用して、Conrec によって生成された等高線セグメントを注文します。 Conrec を使用して等高線の連続点の配列を組み立てる方法 問題のケースは、地図上の外側の等高線です。それらはマップの端と交差します (つまり、閉じた多角形を形成しません)。この場合、線の始点 (マップの端) に再接続するか、兄弟線がマップに入るまで (最終的に元の位置に戻るまで繰り返します)、マップの境界の端に沿って描画します。点）。次に、領域を描画して、塗りつぶし API を機能させることができます。この情報がお役に立てば幸いです。最善の方法は、ポリゴン頂点の順序付きリストを生成することだと思いましたが、おそらく別のアプローチが必要です。

私は COcos2d IOS を使用して Box2d を初めて使用し、さまざまな単純なボディを作成し始めましたが、凸状ではない不規則な形状のようないくつかの形状 (つまり mySprite.png) の頂点を取得する際に問題が発生しています。体の衝突が正確に機能するように、これらの形状を凸面に変換するにはどうすればよいですか??

これらの凹面形状を小さな凸面部分に分割する必要がありますか?これは、多忙な作業のようなもので、簡単な方法またはアルゴリズムです。

参考資料のリンクも提供してください

私はあなたの助けと心配にとても感謝しています.

よろしくアビ..

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

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

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

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

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

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

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

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

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

3 次元の三角形メッシュが与えられた場合、それが凸面か凹面かはどうすればわかりますか? それをチェックするアルゴリズムはありますか？その場合、小さな凹みを無視する許容範囲を定義すると便利です。

^{画像ソース: http://www.rustycode.com/tutorials/convex.html}

解決されたモデルがあり、単一の出力値を返し、それをプロットします。これらの値から、1 ～ 35 の範囲の x 値と 1 ～ 39 の範囲の y 値を使用してサーフェスをプロットし、返された値を z 軸の値として取得します。下記参照。

この図は、定義された関数に従って動作するのではなく、単に出力値のプロットです。

グローバル最大値を見つけるために作成したランダム最適化アルゴリズムを使用しようとしましたが、非常に長い時間がかかり、常に正しいとは限りません (私が使用するグリッド検索アルゴリズムと比較すると、比較）。作成されるサーフェスには微妙な変化があり、厄介な極小値と極大値を複数作成するのに十分です。この非凸面のグローバルな最大値を比較的迅速に見つける方法を探しています。

編集：

35 x 39 が検索領域であり、これは最大のサイズです。x 軸と y 軸の値はモデルの入力値であるため (おそらく言及する必要があります)、各 z 値は x および y 入力座標に関連付けられています。そして、私の最初の推測は、通常、検索エリアの真ん中に軽くたたくことです。

1365 個の Z 値のそれぞれの計算に約 3 秒かかるため、この図の作成には約 50 分かかりました。徹底的な列挙 (Z 値のすべてのポイントを評価する) を使用せずにこれを行いたいと思います。これを 50 分ではなく 5 分程度にしてほしい。

編集(2):

混乱させて申し訳ありません。次の図は、Z 値の 35 行 39 列のグリッドであり、参照目的でのみ使用されます。プログラムの実際の実行では、私が持っているのは x 座標と y 座標だけです。時間を節約するために、可能な限り少ない関数評価でグローバルな最大 z 値を見つけようとしています。horchler、あなたのコメントを参照して、後者です。

編集(3):

この図のものは、ほんの一例です。別のソースからのデータを使用すると、複数の異なる数値が形成されます (つまり、この例では左側は面白くないかもしれませんが、別のデータ セットの場合、グローバル最大値が含まれる場合と含まれない場合があります)。そして、これは複雑さを増します。グローバル最大値の位置がどこになるかをデータから判断することは不可能です。信じられないほど滑らかな表面もあれば、全体に大きなピークが頻繁にある表面もあります。

これは 2 次元計算幾何学の問題です。

穴のない平面にコンパクトな集合 X があるとします (つまり、単純に接続されています)。w をベクトルとし、X と X+w の交点 (つまり、X を w で変換したもの) を考えます。次のことが当てはまる場合、この交差点は複雑であると言います。

1. X は X+w と交差します
2. Y を (X 和 X+w) から有界の穴を埋めることによって得られる単結合領域とすると、Y の境界を歩き回ると、循環順序 a、b、c、d で 4 つの点を見つけることができます。 a と c は X 内にあるが X+w 内にはなく、b と d は X+w 内にあるが X 内にはないような境界上。

簡潔にするために、X と X+w の交差が複雑なwの集合を X の凹包と呼びましょう(注: これはアルファ集合とは関係ありません。単なる名前です)。

X が (たとえば) 多角形ディスクである X の凹包を計算するための高速で実用的なアルゴリズムを知りたいです。これを超えて、おそらく別の用語での凹型船体のエレガントな特徴付けに興味があります. 最後に、この問題について議論している文献へのポインタを教えていただければ幸いです。

以下にいくつかの注意事項を示します。

1. X の凹包は、X が凸の場合にのみ空になります (したがって名前が付けられています)。これは、X が凸で、X が X+w と交差する場合、Y の境界が正確に 2 つのコンポーネントに分類されるためです。1 つは X にあり、もう 1 つは X+w にあります (逆は、以下のポイント 3 から続きます)。
2. 多角形の凹包は、開いた多角形 (つまり、境界が取り除かれたもの) でなければならないため、(たとえば) (開いた) 三角形の有限結合として答えを与えることができます。
3. X が凸でない場合、次のように凹包の一部を見つけることができます。L を X のサポート ラインとし、2 つのセット P と Q でギャップ I を介して X と交差します。J が P と Q の間の X の境界のセグメントである場合、I と J の和集合は、X の補数で開いたディスク D を境界付け、p+ が Q に最も近い P の極値である場合、D-p+凹型船体にあります。すべてのサポート ライン上のこのような領域の結合を内側の凹包と呼びます。計算は比較的簡単に思えますが、一般的には凹包よりも小さくする必要があると思います。