問題タブ [computational-geometry]

ユーザーがジオフェンスとして使用されるポリゴンを地図上に描画できるGoogleEarthを利用したWindowsフォームアプリを入手しました。

私がやりたいのは、ボタンをクリックするだけで画面にうまく収まるようにポリゴンにズームできるようにすることです。機能に合うズームの一種。

ポリゴンの中心を見つけて、GoogleEarthカメラをその緯度/経度に設定するのは簡単です。

私が必要としているのは、広背筋\長さ、画面の高さ\幅のバウンディングボックスを取得し、カメラを設定するための高度を決定するアルゴリズムです。

誰かがこのアルゴリズムを持っているか、どこで見つけることができるか知っていますか？

ありがとう！！

私は秋に計算幾何学のコースを受講しています。そこでは、CまたはC ++でいくつかのアルゴリズムを実装し、それらのベンチマークを行います。ほとんどの学生は、いくつかのデータセットを生成し、timeコマンドを使用してプログラムを測定しますが、もう少し徹底的にしたいと思います。

さまざまなデータセットを自動的に生成し、それらを使用してプログラムを実行し、Rを使用して仮説をテストし、パラメーターを推定するプログラムを作成することを考えています。

では...プログラムの実行時間をより正確に測定するにはどうすればよいですか？

測定に関連するものは何ですか？

テストするのに興味深いと思われる仮説は何ですか（分散、キャッシングによって引き起こされる影響など）？

コードを複数のマシンでテストする必要がありますか？これらのマシンはどのように異なりますか？

私の全体的な目標は、これらのアルゴリズムが実際にどのように機能するか、どの実装手法が優れているか、ハードウェアが実際にどのように機能するかを学ぶことです。

問題: 2D 平面に点の集合があるとします。この点のセットが通常のグリッド上にあるかどうか (それらが 2D ラティスのサブセットである場合) を知りたいです。これを行う方法についていくつかのアイデアが欲しいです。

今のところ、これらの点が軸に沿った長方形のグリッドを形成しているかどうか (下にある格子が x 軸と y 軸に沿った長方形である) と、それが完全な長方形 (格子には穴のない長方形の境界があります)。N は数十万または数百万になる可能性があるため、すべてのソリューションは非常に効率的でなければなりません (O(N^2) よりも優れている)。

コンテキスト:任意にサンプリングされたベクトル フィールドに対して機能する 2D ベクトル フィールド プロット ジェネレーターを作成しました。サンプリングが通常のグリッド上にある場合、プロットを生成するためのより単純で効率的な補間スキームがあります。この特殊なケースをいつ使用できるか知りたいです。特別なケースは、実行する価値があるほど十分に優れています。プログラムはCで書かれています。

不規則な多角形を長方形と直角三角形に縮小するパッキング アルゴリズムを探しています。アルゴリズムは、そのような形状をできるだけ少なく使用しようとする必要があり、比較的簡単に実装できる必要があります (課題の難しさを考えると)。また、可能であれば、三角形よりも長方形を優先する必要があります。

可能であれば、この質問への回答は、提案されたアルゴリズムで使用される一般的なヒューリスティックを説明する必要があります。

これは、頂点が 100 未満の不規則なポリゴンの場合、確定的な時間で実行されるはずです。

目標は、素人向けの不規則な多角形の「賢明な」内訳を作成することです。

ソリューションに適用される最初のヒューリスティックは、多角形が規則的か不規則的かを決定します。正多角形の場合、正多角形に関する私の同様の投稿で概説されているアプローチを使用します:正多角形の効率的なパッキング アルゴリズム

代替テキスト http://img401.imageshack.us/img401/6551/samplebj.jpg

問題グリッド (2D 配列) をランダムな形状の部分 (地球の構造プレート
と考えてください) に分割したいと考えています。

基準は次のとおりです。

• ユーザー入力グリッド サイズ (これは非常に大きくなる可能性があるため、プログラムはスケーリングする必要があります)。
• ユーザーがグリッドの分割係数 (パーツの数) を入力します。
• Grid は長方形の 16 進グリッドで、上下にキャップがあり、左右に回り込みます。
• パーツの分解はありません。
• 他のパーツの中にパーツはありません。
• 極小部品や超大型部品はありません。
• 真円でないランダムな形状のパーツ、または伸びた蛇行形状。

私の解決策：

• 隣接するセルにアクセス/操作できるメソッドを作成します。
• 各パーツのサイズをランダムに決定します (すべてのパーツの合計が 2D 配列全体のサイズに等しくなります)。
• 2D 配列全体を最後の部分の ID 番号で埋めます。
• 最後の部分を除く各部分について:
• 2D 配列のランダムなセルに現在のパーツ ID 番号をシードします。
• 配列全体を反復処理し、現在のパーツ ID 番号で既にシードされているセルに隣接する各セルのアドレスを格納します。
• 保存されているアドレスの 1 つを抽出し、そのセルに現在のプレート ID 番号を入力します (したがって、パーツが形成され始めます)。
• 部品サイズに達するまで繰り返します。

長く伸びた「腕」や内部に大きな穴があるパーツを避けるために、2 つのストレージ アレイを作成したことに注意してください。それから私は前者の前に後者を使い果たします。

私のソリューションを実行すると、次のようになります:
グリッド サイズ: 200
幅: 20
高さ: 10
パーツ: 7

66633333111114444466
00033331111114444466
00003331111114444466
00003331111144444660
00000333111164444660
00000336111664422600
00000336615522222200
00006655555522222200
00006655555552222220
00066655555552222220

品番：0
品番：47

パーツ数：1
パーツサイズ：30

パーツ数：2
パーツサイズ：26

パーツ数：3
パーツサイズ：22

パーツ数：4
パーツサイズ：26

パーツ数：5
パーツサイズ：22

パーツ数：6
パーツサイズ：27

私の解決策の問題：

• 最後の部分は常に断片化されています。上記の場合、6 の 3 つの別々のグループがあります。
• パーツが袋小路で形成され、フルサイズに成長する余地がない場合、アルゴリズムは停止します (アルゴリズムは、他のパーツの上にパーツを形成することを許可しません。開始時の 2D 配列)。
• 2D 配列を形成する前にパーツ サイズを指定せず、パーツの数を指定してその場でパーツ サイズをランダムに生成するだけで間に合わせると、小さなパーツが形成される可能性が残ります。特に 2D 配列が非常に大きい場合は特にそうです。現在のパーツ サイズの方法では、パーツ サイズを 2D 配列の合計サイズの 10% から 40% に制限しています。これを行うための非常にエレガントな方法があれば、パーツのサイズを指定しなくても大丈夫かもしれません - ユーザーが持つ唯一の制御は、2次元配列のサイズとパーツの数です。

その他のアイデア:

• パーツを完全に整列した正方形に形成し、2D アレイを実行して、各パーツが他のパーツにランダムに侵入し、ランダムな形状に変形させます。
• グリッドを横切る蛇行を描き、作成されたスペースを埋めます。おそらく次のような数学を使用します: http://mathworld.wolfram.com/PlaneDivisionbyLines.html

結論:
ここに問題があります: 私は初心者プログラマーで、この問題に正しい方法で取り組んでいるかどうか確信が持てません。断片化されたパーツを一緒に移動し、成形パーツが袋小路に詰まった場合に袋小路から「飛び出す」ことを可能にする「パッチアップ」メソッドをさらに作成できますが、面倒です。

この問題にどのように取り組みますか? おそらく物事を単純化するために使用できるセクシーな数学はありますか?

どうも

画像解析アプリを開発しており、セグメント化された粒子のアスペクト比を計算する必要があります。

http://www.sympatec.com/Science/Characterisation/05_ParticleShape.htmlによると 、AR は (図 1) Xfmin/Xfmax によって与えられます。

この値 (Xf) を取得するためのアルゴリズムの提案はありますか?

問題：

与えられた : n >> k の場合、3 次元の k 辺非凸多角形に強く相関する n 個のポイント

Find : ポイントの元のジオメトリに一致する最適な凹包

試みられた解決策:

警告: 疑似コード

例：

入力は、ポリゴン プレーン内にほぼ均一に分散されたランダムなポイントである高密度のポイント クラウドであり、少しノイズがあります。

出力は、3D ポイントのポリゴンの頂点になります。

私の質問は、この問題にアプローチするより良い方法はありますか? 上記の解決策の問題点は、ポイントがノイズになる可能性があることです。また、ポイントを 2D にラスタライズしてからエッジ検索を実行するのはかなりコストがかかります。

どんな指針も素晴らしいでしょう。前もって感謝します

StackOverflow への最初の質問ですが、お手柔らかにお願いします。

• 特定の大きさまたは「信号強度」が与えられた場合、2Dデカルト平面上の3つの異なる点の中心点の方程式（およびそのアルゴリズム）を見つけようとしています。これらの信号強度はすべて、互いに相対的な尺度ですが、必ずしも円の「半径」と混同されるべきではありません。

三辺測量に関するウィキペディアのエントリ: http://en.wikipedia.org/wiki/Trilateration

このスレッドもチェックしましたが、必要なものとは少し異なります 3つの 緯度と経度のポイント、および3つの距離を使用した三辺測量

一般的な方程式は素晴らしいですが、テスト用にいくつかのサンプル データ ポイントをここに示します。

P1: X,Y = 4153, 4550 // 大きさまたは信号強度 = 143
P2: X,Y = 4357, 4261 // 大きさまたは信号強度 = 140
P3: X,Y = 4223, 4365 // 大きさまたは信号強度 = 139

私の一般的な感覚は、これらのポイントが同じスケール (信号強度とポイント) になるように変換する必要があるということですが、間違っている可能性があります。

考え？ティア

これは非常に簡単な質問のように思えますが、今日、自分で合理的な答えを見つけられないようです。平面 PI に属する R^3 (3D) に A と B の 2 つの点があります。ベクトル v = A - B に垂直な PI のベクトル r を見つけたいと思います。平面 PI の法線であるベクトル n を知っています。数学的には、vr = 0 と vxr = n を解くことができますが、r に関するこのシステムの解には、いくつかの除算が含まれており、数値的な不安定性をもたらす可能性があると思われます。この問題に対する数値的/計算的に優れた解決策を教えてもらえますか?

前もって感謝します、

フェデリコ

XZ平面の点a（0.0、0.0、10.0）を中心に回転させたい点、たとえばp（0.0、0.0、20.0）があります。それを行う最も簡単な方法は何ですか？QtとQVector3DおよびQMatrix4x4を使用して変換を実行しています。私が考えることができるすべてはそのようなものです：

しかし、それは私には非常に複雑に思えます。もっと単純な、またはよりエレガントな解決策があるのではないかと思います。