3

オルタント型の領域が繰り返し切り出された整数格子上の大きな箱の重心を効率的に追跡することに興味があります。私は計算幾何学の文献を探し回っていましたが、関連する可能性のあるさまざまなデータ構造がありますが、ほとんどの議論は可視性の計算 (コンピューター グラフィックスの場合) または最近傍探索 (データ マイニングなどの場合) に関するものです。

論文 http://www.graphicsinterface.org/pre1996/92-NaylorSolidGeometry.pdf、つまり:

Naylor, Bruce F.  Interactive Solid Geometry via Partitioning Trees, 
        Proc. Graphics Interface '92, 1992, pp 11-18.

「バイナリ空間分割ツリー」によって幾何学的オブジェクトを表し、集合操作をサポートし、集合操作の後にオブジェクトの重心が再計算されるという興味深い言及 (詳細なし) があるシステムについて説明しています。おそらく私には盲点がありますが、ツリー マージ アルゴリズム中に質量の中心を効率的に更新する方法がすぐにはわかりません。また、Naylor のものを引用している論文で質量の中心の計算に関する議論を見つけられませんでした。ポインタはありますか？

4

1 に答える 1

1

kd ツリーは文字通り、ここで探しているものです。カットは本質的に軸に沿って配置されていますが、任意の位置にあります。この論文で言及されているように、バイナリ スペース パーティショニング スキームなどの一般化を処理することは、必要のない複雑な層のように聞こえ、パフォーマンスを低下させます。

kd ツリーを使用すると、大きな領域が消える交差点を計算して削除することができます。各 kd ツリー ノードの領域の重さと重心をノード自体に格納すると、子ノードを考慮する必要なく、重心全体への寄与を消去できるはずです。

これを行うことで、ポイント マスとして表されるボリュームのツリーを効果的に構築できます。各ノードは、必要に応じてその子から計算できます。

于 2011-08-02T06:36:31.577 に答える