При поиске количества точек внутри некоторой фигуры с помощью KD-Tree нужно ли нам проверять пересечение областей или просто сравнивать свойства, соответствующие глубине?

Допустим, нам нужно найти количество точек внутри некоторой фигуры в 2D-плоскости.

Для решения этой проблемы мы можем использовать KD-Tree. KD-дерево разделит 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, и возможно, этот вопрос не имеет никакого смысла. Простите за это