私は、非常に使いやすく強力な 2D クロスプラットフォーム CAD パッケージになることを願って取り組んでいます。すでにこれらのいくつかがあることは知っていますが、私は何よりも学習体験のためにこれを行っています.
レンダリングに OpenGL を使用しており、マウスが上に移動したときに各エンティティを強調表示できるようにしたいと考えています。エンティティなどの最も近い点を見つけるためのアルゴリズムがありますが、動きごとにエンティティのデータストア全体をスキャンしたくありません。
私は quadtrees、kd-trees などを見てきましたが、私が迷っているのは、それらを使用してエンティティ全体の焦点を絞り込む方法です。私が見た例のほとんどは、「ポイント」指向のようです。境界の四角形に基づいてインデックスを作成し、その四角形内のエンティティに対して最も近い点を検索したいと思います。
誰かが私を正しい方向に向けることができますか?
「Kd ツリー」を考えると、正しい方向に進みます。ここで、さらに一歩進んで、位置と追加のパラメーターを持つ多次元プリミティブにポイントを拡張する必要があります。Kdは「K次元」という意味でした。
したがって、円または円弧の場合、中心位置をツリーの最初の 2 次元に格納し、次に半径を 3 次元に格納します (2D プリミティブのセットの場合)。また、円形ではない他のすべてのプリミティブについては、円形の境界領域を想定してください。
リニア プリミティブの場合、BSP ツリーを調べることができます。もちろん、Kd の概念を BSP と組み合わせることができます。たとえば、曲線プリミティブには Kd のようなノードを使用し、線形凸セグメントによって境界付けられたプリミティブには BSP を使用します。
R-trees のようなものを探しているようです。これは、(Kd ツリーとは異なり) 兄弟サブツリーのボックスがオーバーラップできる軸指向のバウンディング ボックスに基づくツリーです。私の記憶が正しければ、さまざまな更新ヒューリスティックに基づいたさまざまなバリエーションがあります。
空間データ構造に関する決定的なリファレンスであり、R ツリーとその関連に関する多くの情報が含まれています。
空間分割の背後にある考え方は、より細かい方法を使用してテストできるプリミティブのサブセットを取得するために実行する必要があるテスト (およびそれらの計算の必要性) の数を減らすことです。
エンティティ全体のバウンディング ボックスを使用する必要があり、移動時にマウスの下にあるエンティティを最初に判断する必要があるのは正しいことです。
他にもいくつかのオプションがあります。
そして、私が行方不明であると確信している他の多くのもの - 私はもっと考えているのでそれらを追加します. ：） お役に立てれば！