查找一个点是否位于多个矩形之一中的最快方法是什么？

Question

所以基本上我是为我的 Minecraft spigot 插件（java）这样做的。我知道已经有一些土地所有权插件，但我想制作自己的。 对于这个声明插件，我想知道如何获取一个点（minecraft 块）是否在一个区域（矩形）内。我知道如何检查一个点是否在矩形内，主要问题是当有 10.000 个矩形时如何尽快检查。

检查 10.000 甚至 100.000 的最有效方法是什么，而无需手动循环所有这些并检查每个矩形？

Answer 1

如果您的矩形在一个大矩形中均匀地彼此相邻，那么找到哪个矩形包含点很容易：

width = (maxX-minX)/num_rectangles_x;
height = same but for y
idx = floor( (x - minX)/width );
idy = floor( (y - minY)/height );
id_square = idx + idy*num_rectangles_x;

如果您的矩形是随机放置的，那么您应该使用像八叉树这样的空间加速结构。然后检查点是否在根中，然后检查点是否在其节点之一中，重复直到找到包含该点的叶子。 CPU 上应该可以达到每 10 毫秒 10000 次测试。对于 GPU 来说，每 10 毫秒 100 万次测试应该没问题。但是您可能需要实现八叉树的稀疏版本和叶节点的空间填充曲线顺序，以获得更好的缓存，以达到这些性能水平。

Answer 2

当矩形以检查它们是否保留该点的方式生成时，有没有办法添加逻辑测试？在这种情况下，如果它们在生成时包含该点，则可以将布尔值设置为 true，然后在检查该 Minecraft 块时，区域（矩形）回复 true 或 false。

这样，您可以在生成矩形时运行循环或检查，但在运行游戏时，回复应该会非常快地发生，只需检查 bool ContainsPoint 的 true 或 false 即可。