問題タブ [geometry]

空のスペースに収まる最大の面積を持つ長方形を見つけるための最も効率的なアルゴリズムは何ですか？

画面が次のようになっているとしましょう（「＃」は塗りつぶされた領域を表します）：

考えられる解決策は次のとおりです。

通常、私は解決策を考え出すのを楽しんでいます。今回は自分で手探りで時間を無駄にしないようにしたいと思いますが、これは自分が取り組んでいるプロジェクトに実用的であるためです。よく知られている解決策はありますか？

Shog9は書いた：

入力は配列（他の応答によって暗示される）ですか、それとも任意のサイズの配置された長方形の形式のオクルージョンのリストですか（ウィンドウ位置を処理するときのウィンドウシステムの場合のように）？

はい、画面に配置された一連のウィンドウを追跡する構造があります。また、空か塗りつぶしかを問わず、各エッジ間のすべての領域と、左エッジまたは上端のピクセル位置を追跡するグリッドもあります。この特性を利用する修正された形式があると思います。何か知っていますか？

2 つの点 (線分) と四角形があります。線分が長方形と交差するかどうかを計算する方法を知りたいです。

画面空間に 4 つの 2D ポイントがあり、それらを逆投影して 3D 空間に戻す必要があります。4 つの点のそれぞれが 3D 回転した剛体の四角形の角であることはわかっており、四角形のサイズもわかっています。これから3D座標を取得するにはどうすればよいですか?

特定の API を使用しておらず、既存の射影行列もありません。これを行うための基本的な数学を探しています。もちろん、単一の 2D ポイントを他の参照なしで 3D に変換するのに十分なデータはありませんが、4 つのポイントがある場合、それらはすべて同じ平面上で互いに直角であることがわかっていると思います。それらの間の距離がわかれば、そこからそれを把握できるはずです。残念ながら、私はその方法を完全に理解することはできません。

これは写真測量の傘下にある可能性がありますが、Google で検索しても役立つ情報は得られませんでした。

私は GPU 機能を使用して現在の問題を解決しようとしています:「点群 P と、点と法線 (Pp、Np) で記述された有向平面が与えられた場合、EPSILON 以下の距離にある雲内の点を返します。飛行機から」。

私の同僚と話していると、次の解決策に収束しました。

1) すべてのポイントが異なる頂点座標を持つように、テクスチャ座標がアタッチされたポイントの頂点バッファを準備します。2) 投影ステータスを直交に設定します。3) 平面の​​法線が -z 軸と整列するようにメッシュを回転させますx,y,z=0 が Pp に対応するようにオフセットします 4) z:[-EPSILON;+EPSILON] のように z クリッピング プレーンを設定します 5) テクスチャにレンダリングします 6) グラフィック カードからテクスチャを取得します 7)グラフィック カードからテクスチャを読み取り、レンダリングされたポイントを (インデックスに関して) 確認します。これは、目的の距離範囲内のポイントです。

問題は次のとおりです。q1) そのような操作を行うには、ウィンドウ フレームを開く必要がありますか? 私は MATLAB 内で作業し、MEX-C++ を呼び出しています。経験上、新しいフレームを開くとすぐに、スーツ全体が惨めにクラッシュすることを知っています! q2) GLPoint にテクスチャ座標を与えるためのプリミティブは何ですか? q3) テクスチャへのレンダリングがどのように実装されるのかよくわかりません。任意の参照、チュートリアルは素晴らしいでしょう... q4) カードからこのテクスチャをどのように取得しますか? 繰り返しますが、参照、チュートリアルは素晴らしいでしょう...

スケジュールが厳しいので、GLSL 仕様書や OpenGL API を参考にするのではなく、私が学ぶべきテクニックの名前を教えていただければ幸いです。これらは、私の質問に対する少し漠然とした答えです。

コメントありがとうございます。

ps また、可能であれば CUDA のようなリソースを使用したくないことに注意してください。したがって、新しいシェーダーを作成する必要なく、できるだけ多くの OpenGL 要素を使用するものを取得します。

注: http://www.opengl.org/discussion_boards/ubbthreads.php?ubb=showflat&Number=245911#Post245911に相互投稿

作業中のプロジェクトの一環として、3D空間内の一連の点の重心を計算する必要があります。今のところ、私は単純に見えますが素朴な方法でそれを行っています-次のように、ポイントの各セットの平均を取ることによって。

ここxで、、yおよびzは浮動小数点数の配列です。より正確な重心を取得する方法があることを思い出しているようですが、そのための簡単なアルゴリズムは見つかりませんでした。誰かアイデアや提案がありますか？私はこれにPythonを使用していますが、他の言語の例を適応させることができます。

GISファイル（都市地図）からの（2D）ポイントのセットがあるので、そのマップ（その境界）の「等高線」を定義するポリゴンを生成する必要があります。その入力パラメータは、設定されたポイントと「最大エッジ長」になります。次に、対応する（おそらく非凸の）ポリゴンを出力します。

これまでに見つけた最善の解決策は、ドロネー三角形を生成してから、最大エッジ長よりも長い外部エッジを削除することでした。すべての外部エッジがそれよりも短くなった後、内部エッジを削除して、必要なポリゴンを取得します。問題は、これは非常に時間がかかることであり、もっと良い方法があるかどうか疑問に思っています。

私は州のランダム マップを作成するゲームに取り組んでいます (リスクまたは外交)。そのマップを作成するには、まず一連の半ランダムな点を生成し、次にそれらの点の Delaunay 三角形分割を計算します。

これが完了したら、州境の開始点として機能するポイントのボロノイ図を作成しようとしています。この時点での私のデータ (しゃれは意図していません) は、元の一連の点と Delaunay 三角形のコレクションで構成されています。

ウェブ上でこれを行う方法をいくつか見てきましたが、そのほとんどは Delaunay がどのように導出されたかに関係しています。Delaunay に統合する必要はなく、データだけに基づいて機能するものを見つけたいと思っています。それに失敗すると、最適な速度とは対照的に、相対幾何学​​の初心者にわかりやすいものを探しています。ありがとう！

楕円の長軸が垂直または水平の場合、バウンディング ボックスを計算するのは簡単ですが、楕円を回転させた場合はどうでしょうか。

これまでに考えられる唯一の方法は、周囲のすべてのポイントを計算し、最大/最小の x および y 値を見つけることです。もっと簡単な方法があるはずです。

任意の角度で楕円を記述する関数 (数学的な意味で) がある場合、その導関数を使用して、勾配がゼロまたは未定義の点を見つけることができますが、見つけることができないようです。

編集：明確にするために、軸に沿ったバウンディングボックスが必要です。つまり、楕円で回転するのではなく、x軸に合わせたままにする必要があるため、バウンディングボックスの変換は機能しません。

囲んでいる長方形をカバーする重複しない長方形のコレクションがあります。マウスクリックで含まれている長方形を見つける最良の方法は何ですか？

明白な答えは、長方形の配列を持ち、それらを順番に検索して、検索をO（n）にすることです。アルゴリズムがO（n）よりも小さくなるように位置別に並べ替える方法はありますか？たとえば、O（log n）またはO（sqrt（n））ですか？

線分が2Dで軸に沿った長方形と交差するかどうかをテストする方法は? セグメントは、その 2 つの端点 p1、p2 で定義されます。四角形は、左上と右下の点で定義されます。