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 回答