java - 如何返回 BoundingVolume 中的所有点

Question

我正在试验 jmonkeyengine，我发现需要返回落在边界体积内的所有点(来自预定义的大量点)。创建体积本身很容易，但我想获得所有包含点的 map 。

社区有什么想法吗？如果需要，我很乐意使用其他库，由于社区支持和 BoundingCapsule 形状，我被 jmonkey 所吸引。

编辑:我考虑过遍历我的所有点并使用 .contains，不幸的是空间包含数十万个点和相对较小的胶囊。当然，我一定缺少一些聪明的数学。

Answer 1

如果您只需要执行此操作一次，那么没有比根据边界体积检查每个点更好的方法了。

如果需要进行多次查询，可以通过设置空间查询结构来提高查询性能。请注意，您首先需要花费时间和内存来构建和维护您的查询结构，但如果您可以分摊大量查询的费用，那也没关系。

根据您的需要，您可能想要使用 grid , 一个 quadtree , 一个 K-d tree ，或 R-tree加速您的空间查询。以上并不是加速结构的详尽列表，但它包括一些最常用的选项。