快速计算圆圈内的点数

Question

给定平面上的一组n个点,我想以某种方式比O(n ^ 2)(O(nlog(n))更快地预处理这些点,然后能够回答以下类型的查询"多少个n个点位于一个给定中心和半径的圆圈内？" 比O(n)更快(O(优选log(n)).

你能建议一些我可以用来解决这个问题的数据结构或算法吗？

我知道这些类型的问题通常使用Voronoi图来解决,但我不知道如何在这里应用它.

Answer 1

构建空间细分结构,例如点的四叉树或KD树.在每个节点存储该节点所覆盖的点数.然后,当您需要计算查找圆覆盖的点时,遍历树,并在节点中的每个细分检查它是否完全在圆外,然后忽略它,如果它完全在圆内,则将其计数添加到如果它与圆相交,则递归,当你到达叶子时,检查叶子内的点以便收容.

这仍然是O(n)最坏的情况(例如,如果所有点都位于圆周上),但是平均情况是O(log(n)).

Answer 2

构建点的KD树,这应该给你比O(n)更好的复杂性,平均O(log(n))我认为.

您可以使用2D树,因为这些点被约束到平面.

假设我们已经将问题转换为2D,我们将为这些点提供类似的东西:

 struct Node {
     Pos2 point;
     enum {
        X,
        Y
     } splitaxis;
     Node* greater;
     Node* less;
 };

greater并且less包含沿splitaxis分别具有更大和更小坐标的点.

 void
 findPoints(Node* node, std::vector<Pos2>& result, const Pos2& origin, float radius) {
     if (squareDist(origin - node->point) < radius * radius) {
         result.push_back(node->point);
     }
     if (!node->greater) { //No children
          return;
     }
     if (node->splitaxis == X) {
         if (node->point.x - origin.x > radius) {
             findPoints(node->greater, result, origin radius);
             return;
         }
         if (node->point.x - origin.x < -radius) {
             findPoints(node->less, result, origin radius);
             return;
         }
         findPoints(node->greater, result, origin radius);
         findPoints(node->less, result, origin radius);
     } else {
         //Same for Y
     }
 }

然后使用KD树的根调用此函数