在使用 KD 树查找某个形状内的点数时，我们是否需要检查区域交集，或者只是比较适合深度的属性？

Question

假设我们必须找到 2D 平面中某个形状内的点数。

我们可以使用KD-Tree来解决这个问题。 KD-Tree 将 2D 平面划分为矩形，然后我们可以检查一些节点边界（看起来像矩形）和我们想要计算点数的形状之间的交集。

这似乎合乎逻辑。我已经编写了解决这样的问题的代码，其中我的形状是圆形。

static bool is_point_inside_circle(int x, int y, int cx, int cy, int cr) {
    return (x - cx) * (x - cx) + (y - cy) * (y - cy) <= cr * cr;
}

struct RectBoundary {
    int top;
    int right;
    int bottom;
    int left;

    RectBoundary() : top(500), right(500), bottom(-500), left(-500) { }
    RectBoundary(int t, int r, int b, int l) : top(t), right(r), bottom(b), left(l) { }

    bool is_inside_circle(int cx, int cy, int cr) const {
        return is_point_inside_circle(left, top, cx, cy, cr)
            && is_point_inside_circle(right, top, cx, cy, cr)
            && is_point_inside_circle(right, bottom, cx, cy, cr)
            && is_point_inside_circle(left, bottom, cx, cy, cr);
    }

    bool intersects_with_circle(int cx, int cy, int cr) const {
        return cx - cr <= left
            || cx + cr >= right
            || cy - cr <= bottom
            || cy + cr >= top
            || (cx >= left && cx <= right && cy <= top && cy >= bottom);
    }
};

struct KDNode {
    int x, y;
    int depth;
    RectBoundary boundary;

    KDNode* left = nullptr;
    KDNode* right = nullptr;

    bool is_leaf() {
        return left == nullptr && right == nullptr;
    }
};

KDNode* build(vector<vector<int>>& points, int l, int r, int depth) {
    if (l > r)
        return nullptr;

    if (depth % 2 == 0) {
        sort(points.begin() + l, points.begin() + r + 1);
    }
    else {
        sort(points.begin() + l, points.begin() + r + 1, [](const vector<int>& p1, const vector<int>& p2)
            {
                return p1[1] < p2[1];
            });
    }

    const int mid = (l + r) / 2;

    KDNode* node = new KDNode();
    node->depth = depth;
    node->x = points[mid][0];
    node->y = points[mid][1];

    node->left = build(points, l, mid - 1, depth + 1);
    node->right = build(points, mid + 1, r, depth + 1);

    return node;
}

void set_boundaries(KDNode* node, int depth) {
    if (node == nullptr)
        return;

    if (depth % 2 == 0) {
        if (node->left) {
            node->left->boundary = node->boundary;
            node->left->boundary.right = node->x;
        }

        if (node->right) {
            node->right->boundary = node->boundary;
            node->right->boundary.left = node->x;
        }
    }
    else {
        if (node->left) {
            node->left->boundary = node->boundary;
            node->left->boundary.top = node->y;
        }

        if (node->right) {
            node->right->boundary = node->boundary;
            node->right->boundary.bottom = node->y;
        }
    }

    set_boundaries(node->left, depth + 1);
    set_boundaries(node->right, depth + 1);
}

int traverse(KDNode* node) {
    if (node == nullptr)
        return 0;

    return 1 + traverse(node->left) + traverse(node->right);
}

int count_points_inside_circle(KDNode* node, int cx, int cy, int cr) {
    if (node->is_leaf()) {
        return is_point_inside_circle(node->x, node->y, cx, cy, cr);
    }

    int count = is_point_inside_circle(node->x, node->y, cx, cy, cr);

    if (node->left) {
        if (node->boundary.is_inside_circle(cx, cy, cr))
            count += traverse(node->left);
        else if (node->boundary.intersects_with_circle(cx, cy, cr))
            count += count_points_inside_circle(node->left, cx, cy, cr);
    }

    if (node->right) {
        if (node->boundary.is_inside_circle(cx, cy, cr))
            count += traverse(node->right);
        else if (node->boundary.intersects_with_circle(cx, cy, cr))
            count += count_points_inside_circle(node->right, cx, cy, cr);
    }

    return count;
}

vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
    KDNode* root = build(points, 0, points.size() - 1, 0);
    set_boundaries(root, 0);

    vector<int> result(queries.size());
    for (int i = 0; i < queries.size(); ++i)
        result[i] = count_points_inside_circle(root, queries[i][0], queries[i][1], queries[i][2]);

    delete root;
    return result;
}

写完这篇文章后，我意识到我的

intersects_with_circle

很可能是错误的，因为它假设矩形和圆形的相对位置是固定的。我仍然无法找出适当的公式来检查圆形和矩形之间的交点。

但是我想到的是：我们真的需要比较整个形状区域吗？

我的意思是，给定矩形和任何形状，如果我们只比较适合给定 KD 树深度的形状属性会怎么样？假设我们有 2D 平面，当前深度为

6

。它是偶数，所以我们将使用

x

属性。我们是否可以只获取要计算点数的形状的中点，使用叉积检查

x

相对于该中点的方向，然后获取形状的最左边或最右边的点（取决于方向），以及检查这个“最点”

x

属性是否小于或大于我们矩形的

x

（也取决于方向）？

可以吗？我们现在可以只关注一处房产，而不是比较整个区域吗？我可以想象给定的形状“最点”

x

属性在不检查

y

的情况下也可能无效，但是我们最终将检查

y

属性并可选择拒绝某些特定区域（一个额外的步骤，来自我们本来可以早点摆脱它），因为属性根据 KD 树深度交替。

我不确定我是否正确理解了 KD-Tree，这个问题可能没有任何意义。抱歉

Answer 1

你当然可以，而且一般来说你会。

查询给定形状内所有点的正常方法是使用 kD 树作为 AABB 测试的宽相，然后针对形状本身进行窄相测试。

因此，您要做的第一件事就是确定包含该形状的矩形的范围。对于圆形，显然是

cx-cr < x < cx+cr

和

cy-cr < y < cy+cr

。在偶数（x 比较）级别上，无需检查

y

范围，因此存在“适合深度的属性”。当然，节点本身需要充分比较；幸运的是，你只需要在两个分支都通过的情况下才需要这样做。所以就像这样

// even level
bool leftPasses = node.x > xmin;
bool rightPasses = node.x < xmax;

if(leftPasses && rightPasses && narrowPhase(node.x, node.y)) count++;
if(leftPasses) recurse(node.left);
if(rightPasses) recurse(node.right);

注意我没有对节点边界做任何事情。对于这样的事情，没有理由存储它们：如果您只是进行自上而下的遍历，则可以随时跟踪它们。另请注意，缺乏“检查包含并计算整个子树”策略，从渐近性能的角度来看，这没有用。