算法帮助 - 小对象的 HitTest

Question

在处理草图中实现选择算法时，我循环遍历场景中的每个对象，并检查它是否在鼠标点击位置的几个像素范围内。有很多对象，而且它们非常小。

正如您可以想象的那样，一旦场景中充满了物体，这就会变得非常麻烦。有没有简单的方法可以加快搜索速度？我可以轻松地使此搜索二进制化吗？我场景中的对象是点，因此多边形 HitTest 算法似乎不是正确的解决方案。

Answer 1

将场景分成桶，分成 N 个 x 桶和 M 个 y 桶，或者分成 N*M 个 x*y 桶。在前一种情况下，桶存储在两个数组中(一个 x 数组和一个 y 数组)；在后一种情况下，桶存储在数组数组中(外部数组索引 x 坐标，内部数组索引 y 坐标)。在任何一种情况下，桶都会存储对桶索引区域内所有点的引用；例如，点 (8, 12) 将位于 x-bucket [5, 10] 和 y-bucket [10, 15] 中，否则它将位于 x*y bucket ([5, 10] , [10, 15]).

查找点时，要么查找合适的 x 和 y 桶，要么简单地查找合适的 x*y 桶。在前一种情况下，取 intersection(union(x-buckets), union(y-buckets))。您可能需要根据命中半径查找多个桶，例如，如果您正在查找半径为 2 的 x 坐标 9，那么您需要 [5, 10] 和 [10, 15] 桶。

使用单独的 x 和 y 桶占用更少的空间(N + M 桶而不是 N*M 桶)并使索引更容易(两个单独的数组与一个嵌套数组)，而 x*y 桶使速度更快查找，因为您不需要采取任何设置的交叉路口。

存储桶越小，数据结构占用的空间就越大，但检索到的误报就越少。理想情况下，如果您有足够的内存，那么桶将覆盖与命中半径相同的间隔。