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

[Anonymous]

Предположим, нам нужно найти количество точек внутри некоторой фигуры в 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) = left && cx  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& p1, const vector& 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, int cx, int cy, int cr) {
if (node == nullptr)
return 0;

return 1 + traverse(node->left, cx, cy, cr) + traverse(node->right, cx, cy, cr);
}

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, cx, cy, cr);
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, cx, cy, cr);
else if (node->boundary.intersects_with_circle(cx, cy, cr))
count += count_points_inside_circle(node->right, cx, cy, cr);
}

return count;
}

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

vector 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, скорее всего, неправильный, поскольку он предполагает фиксированное относительное положение прямоугольника и круга. Я до сих пор не могу найти подходящую формулу для проверки пересечения круга и прямоугольника.
Но что мне пришло в голову: действительно ли нам нужно сравнивать всю площадь фигур?
p>
Я имею в виду, что если взять прямоугольник и любую форму, то что, если мы сравним только те свойства формы, которые подходят для данной глубины KD-дерева? Допустим, у нас есть 2D-плоскость и текущая глубина равна 6. Это четно, поэтому мы будем использовать свойство x. Можем ли мы просто получить среднюю точку фигуры, внутри которой мы хотим посчитать точки, проверить ориентацию x по этой средней точке с помощью векторного произведения, а затем получить самую левую или самую правую точку фигуры (зависит от ориентации) и проверьте, меньше или больше это свойство «самая точка» x (также зависит от ориентации), чем x нашего прямоугольника?
Может ли это сработать? Можем ли мы в данный момент выделить один объект вместо сравнения целых территорий? Я могу себе представить, что заданное свойство x "самая точка" фигуры может быть недопустимым без проверки также y, но тогда мы в конечном итоге проверим также свойство y и, при необходимости, отклоним некоторую конкретную область (один дополнительный шаг, от которого мы могли бы избавиться раньше), так как свойства чередуются в зависимости от глубины KD-дерева.
Я не уверен, что понимаю KD -Дерево правильное, и возможно, что этот вопрос не имеет никакого смысла. Извините за это[/i]

Подробнее здесь: https://stackoverflow.com/questions/786 ... eed-to-che