多くの移動オブジェクト (球体、三角形、ボックス、点など) を処理するのに最適なデータ構造は何だろうと考えていました。Nearest Neighbor と Collsion detection という 2 つの質問に答えようとしています。

伝統的に、R ツリーのようなデータ構造は最近傍クエリに使用され、Oct/Kd/BSP は静的オブジェクトまたは非常に少数の移動オブジェクトを扱う衝突検出問題に使用されることを認識しています。

他にもっと良いものがあることを願うばかりです。

私はすべての助けに感謝します。

ノイズの多い X、Y ポイントのソートされていないリストがあります。ただし、それらは世界を通る道を形成します。線分を使用してこのデータの近似値を描画するアルゴリズムが必要です。

これは、ライン フィッティング アルゴリズムを使用して線形データの近似値を選択する方法に似ています。私の問題は、道が曲がりくねって世界中を曲がりくねっているので、難しいだけです。 代替テキスト http://www.praeclarum.org/so/pathfinder.png

これを達成するための標準/堅牢/理解しやすいアルゴリズムを知っている人はいますか?

質疑応答：

うるさいってどういう意味ですか？パスを理想的に実現した場合、X 要素と Y 要素にガウス ノイズを追加して、その理想的なパスから点のセットをサンプリングします。そのノイズの平均または標準偏差はわかりません。std devで推測できるかもしれません...

ポイントは、近似しようとしている理想的だが複雑なパスの近くにありますが、そのパス上にはありませんか? はい。

パスの形状に関するアプリオリな情報はありますか? そのような情報を取得する他の方法はありますか？残念ながら違います。

配列内の 4 つの 2D ポイント。それらを時計回りに並べ替える必要があります。1回のスワップ操作でできると思いますが、これを正式に書き留めることはできませんでした。

編集: 私の場合、4 つの点は凸多角形です。

編集: 4 つの点は、凸多角形の頂点です。それらは順番である必要はありません。

キャンバスでシェイプを編集するために使用したいコントロールである WPF Shape (PolyLine) エディターを作成しようとしています。

エディタが行う必要があるのは、形状の点と線を表示し、それらを移動できるようにすることです。

どうすればこれを達成できるか、または出発点を教えてくれる人はいますか? これまでのところ、これを行う方法に関連するものは何も見つかりませんでした。

私の状況

• 入力: 長方形のセット
• 各 rect は、次のように 4 つの double で構成されます: (x0,y0,x1,y1)
• それらはどの角度でも「回転」していません。すべて、画面に対して「上下」および「左右」に移動する「通常の」長方形です。
• それらはランダムに配置されています - それらは端で接触している、重なり合っている、または接触していない可能性があります
• 数百の長方形があります
• これはC#で実装されています

私は見つける必要があります

• それらのオーバーラップによって形成される領域 - 複数の長方形が「カバー」するキャンバス内のすべての領域 (たとえば、2 つの長方形の場合、それは交点になります)
• オーバーラップのジオメトリは必要ありません。面積だけです (例: 4 平方インチ)
• オーバーラップは複数回カウントされるべきではありません。たとえば、同じサイズと位置を持つ 3 つの四角形が重なり合っているとします。この領域は (3 回ではなく) 1 回カウントする必要があります。

例

• 下の画像には、A、B、C の 3 つの長方形が含まれています。
• A と B が重なっている (破線で示されている)
• B と C の重なり (破線で示す)
• 私が探しているのは、ダッシュが表示されている領域です

-

2 つのポリゴンの類似性を比較する通常の方法は何ですか? 頂点は 2D です。

いくつかの Geometry データと Transform がある場合、どのように変換を Geometry に適用して、データが変換された新しい Geometry を取得できますか?

例: Path.Data が PathGeometry オブジェクトに設定されている Path オブジェクトがあり、変換を使用して PathGeometry オブジェクトのポイントを所定の位置に変換し、レンダリング時に使用される PathGeometry に変換を適用したくありません。 .

PS Transform クラスには Point を変換するために使用できるメソッドがあることは知ってPoint Transform.Transform(Point p)いますが、任意のジオメトリを一度に変換する方法はありますか?

編集：現在見つかった解決策については、返信を参照してください

私の Direct3D アプリケーションでは、マウスまたは矢印キーを使用してカメラを移動できます。しかし、上方向ベクトルとして (0,1,0) をハードコーディングするLookAtLHと、カメラの向きによってはフレームが空白になります。

Y軸に沿って見ると、(0,1,0)が上方向として機能しなくなるという難しい方法を学びました(明らかですか?)。これらの特殊なケースごとに、上方向を別のものに切り替えることを考えています。これを処理するより優雅な方法はありますか?

（x1、y1、z1）から（x2、y2、z2）に向かう線（実際には立方体）があります。（x3、y3、z3）から（x4、y4、z4）に向かう別の線に沿って整列するように回転させたいと思います。現在、とMath::Atan2一緒に使用していMatrix::RotateYawPitchRollます。これを行うためのより良い方法はありますか？

編集：私はこの投稿を非常にひどく言いました。私が実際に探しているのは、2つのベクトルからの回転行列です。

3 つの点 (A、B、X) と距離 (d) があります。点 X が距離 d より線分 AB 上の任意の点に近いかどうかをテストする関数を作成する必要があります。

問題は、まず、私の解決策が正しいかどうか、そしてより良い (より速い) 解決策を考え出すことです。

私の最初のパスは次のとおりです

このコードは、少なくとも 1 つの A/B/d に合格するすべての P を見つけることを目的として、P の大規模なセットと A/B/d トリプレットの大規模なセットに対して実行されることになるため、方法があると思われます。それに基づいて全体的なコストを削減しますが、まだ調べていません。

（ところで：いくつかの並べ替え、いくつかの一時的な値、およびいくつかの代数恒等式が上記のコストを削減できることを認識しています。明確にするためにそれらを省略しました。）

編集: これは 2D の問題です (ただし、3D に一般化するソリューションはクールです

編集: さらに考えてみると、ヒット率は約 50% になると予想しています。X ポイントはネストされた階層で形成できるため、大きなサブツリーをすべてパスおよびすべて失敗としてプルーニングできると期待しています。トリプレットを制限する A/B/d は、より多くのトリックになります。

編集：dはABと同じ大きさのオーダーです。

編集: Artelius がすばらしい解決策を投稿しました。私が完全に理解する前に接線を外れてしまったので、彼が何をしようとしているのか正確に理解しているかどうかはわかりません. とにかく、結果として別の考えが頭に浮かびました：

• 最初の Artelius のビットは、AB を原点の中心に配置し、X 軸に合わせて配置する行列を事前に計算します。(2回追加、4回追加、2回追加)
• すべてを第 1 象限 (2 つの腹筋) に折りたたむ
• ゾーンの中央部分を単位正方形 (2 mul) にするために X&Y でスケーリングします。
• ポイントがその正方形にあるかどうかをテストする (2 テスト)
• エンド キャップをテストします (スケーリングされていない値に戻ります
  • 端を原点に配置するために x に変換します (1 追加)
  • 2 乗して加算 (2 mul、1 加算)
  • d^2 (1 cmp) と比較

これが私のソリューションよりも優れていると確信しています。

（これ以上のものがなければ、アルテリウスが「賞」を獲得します:)