Быстро посчитать количество точек внутри круга

Question

Учитывая набор из n точек на плоскости, я хочу предварительно обработать эти точки как-то быстрее, чем O (n ^ 2) (предпочтительно O (nlog (n))), а затем иметь возможность отвечать на запросы следующего вида «Сколько из n точек лежит внутри круга с данным центром и радиусом?» быстрее, чем O (n) (O (log (n) предпочтительно).

Можете ли вы предложить какую-либо структуру данных или алгоритм, который я могу использовать для этой проблемы?

Я знаю, что подобные проблемы часто решаются с помощью диаграмм Вороного, но я не знаю, как их здесь применить.

Answer 1

Постройте структуру пространственного подразделения, такую ​​как дерево квадрантов или KD-дерево точек. В каждом узле хранится количество точек, покрываемых этим узлом. Затем, когда вам нужно подсчитать точки, охватываемые кругом поиска, пройтись по дереву и для каждого подразделения в узле проверить, находится ли он полностью за пределами круга, а затем проигнорировать его, если он полностью находится внутри круга, а затем добавить его счет к итого, если он пересекается с кругом, повторяйте, когда вы доберетесь до листа, проверьте точки (точки) внутри листа на предмет удержания.

Это все еще O (n) наихудший случай (например, если все точки лежат по периметру окружности), но средний случай - O (log (n)).

Answer 2

Постройте KD-дерево из точек, это должно дать вам гораздо большую сложность, чем O (n), в среднем O (log (n)), я думаю.

Вы можете использовать двухмерное дерево, поскольку точки ограничены плоскостью.

Предполагая, что мы преобразовали задачу в 2D, у нас будет что-то вроде этого для точек:

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

greater и less содержат точки с большими и меньшими координатами соответственно вдоль разделительной оси.

 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-дерева

Answer 3

Если бы моей целью была скорость, а количество точек не было бы огромным (миллионы), я бы сосредоточился не только на алгоритмической памяти, но и на алгоритме.

Несбалансированное дерево k-d лучше всего подходит на бумаге, но для него требуются указатели, которые могут увеличить объем памяти в 3 раза, поэтому его нет.

Сбалансированное дерево k-d не требует хранения, кроме как для массива с одним скаляром для каждой точки. Но у этого тоже есть недостаток: скаляры не могут быть квантованы - они должны быть такими же 32-битными числами с плавающей точкой, что и в исходных точках. Если они квантованы, больше невозможно гарантировать, что точка, которая появляется раньше в массиве, находится либо на плоскости расщепления, либо слева от нее, И что точка, которая появляется позже в массиве, находится либо на плоскости расщепления, либо направо.

Существует структура данных, которую я разработал для решения этой проблемы. Люди Synergetics говорят нам, что объем является эмпирически четырехнаправленным. Давайте скажем, что самолет также эмпирически направлен на три направления.

Мы привыкли пересекать плоскость по четырем направлениям -x, + x, -y и + y, но проще использовать три направления a, b и c, которые указывают на вершины равносторонний треугольник.

При построении сбалансированного дерева k-d спроецируйте каждую точку на оси a, b и c. Сортируйте точки, увеличивая. Для получения средней точки округлите вниз, квантовайте и сохраните a. Затем, для подмассивов слева и справа от медианы, сортируйте по возрастанию b, а для медианных точек округляйте вниз, квантовайте и сохраняйте b. Повторяйте и повторяйте, пока в каждой точке не сохранится значение.

Затем, при проверке окружности (или чего-либо еще) против конструкции, сначала вычислите максимум a, b и c координаты окружности. Это описывает треугольник. В структуре данных, которую мы сделали в последнем абзаце, сравните срединную точку координату с максимумом окружности координатой. Если точка a больше круга a, мы можем дисквалифицировать все точки после медианы. Затем для подмассивов слева и справа (если не дисквалифицирован) от медианы сравните окружность b с координатой медианной точки. Повторяйте и повторяйте, пока больше не останется очков для посещения.

По теме это похоже на структуру данных BIH , но не требует интервалов -x и + x и -y и + y, потому что a, b и c так же хороши при обходе самолет, и для этого требуется меньшее количество направлений.

Answer 4

Предполагая, что у вас есть набор точек S в декартовой плоскости с координатами (x _i , y _i ), заданный произвольный круг с центром (x _{c *) 1006 *, y c ) и радиус r вы хотите найти все точки, содержащиеся в этом круге.}

Я также предполагаю, что точки и окружность могут двигаться, поэтому определенные статические структуры, которые могут ускорить это, не обязательно будут подходящими.

На ум приходят три вещи, которые могут ускорить это:

Во-первых, вы можете проверить:

(xi-xc)^2 + (yi-yc)^2 <= r^2

вместо

sqrt((xi-xc)^2 + (yi-yc)^2) <= r

Во-вторых, вы можете несколько отбросить список точек, помня, что точка может быть только внутри круга, если:

• x _i находится в диапазоне [x _c -r, x _c + r]; и
• y _i находится в диапазоне [y _c -r, y _c + r]; и

Это известно как ограничивающая рамка . Вы можете использовать его в качестве приблизительного значения или сократить список точек до меньшего подмножества, чтобы точно проверить с первым уравнением.

Наконец, сортируйте свои точки в порядке x или y, а затем вы можете выполнить поиск пополам, чтобы найти набор точек, которые, возможно, находятся внутри вашей ограничительной рамки, дополнительно сокращая ненужные проверки.

Answer 5

Я использовал код Андреаса, но он содержит ошибку. Например, у меня было две точки на плоскости [13, 2], [13, -1], и моя исходная точка была [0, 0] с радиусом 100. Он находит только 1 точку. Это мое исправление:

void findPoints(Node * root, vector<Node*> & result, Node * origin, double radius, int currAxis = 0) {
if (root) {
    if (pow((root->coords[0] - origin->coords[0]), 2.0) + pow((root->coords[1] - origin->coords[1]), 2.0) < radius * radius) {
        result.push_back(root);
    }

    if (root->coords[currAxis] - origin->coords[currAxis] > radius) {
        findPoints(root->right, result, origin, radius, (currAxis + 1) % 2);
        return;
    }
    if (origin->coords[currAxis] - root->coords[currAxis] > radius) {
        findPoints(root->left, result, origin, radius, (currAxis + 1) % 2);
        return;
    }
    findPoints(root->right, result, origin, radius, (currAxis + 1) % 2);
    findPoints(root->left, result, origin, radius, (currAxis + 1) % 2);
}
}

Разница в том, что Андреас на данный момент проверяет детей с только если (! Root-> больше), что не является полным. Я, с другой стороны, не делаю эту проверку, я просто проверяю, действителен ли root. Дайте мне знать, если найдете ошибку.

Answer 6

в зависимости от того, сколько у вас времени на предварительные вычисления, вы можете построить дерево следующим образом:

ветви первого узла - это значения x, под ними - узлы значения y, а под ними - узлы значения радиуса. на каждом листе есть хэшсет точек.

когда вы хотите вычислить точки в x, y, r: пройдите по вашему дереву и спуститесь по ветви, которая соответствует вашим значениям x, y, ближайшим. когда вы спускаетесь к корневому уровню, вам нужно сделать небольшое совпадение (материал с постоянным временем), но вы можете найти радиус, чтобы все точки в этом круге (определяемые путем в дереве) находились внутри указанного круга x, y, r и другим кругом (то же самое x_tree, y_tree в дереве, как и раньше, но другим r_tree), так что все точки исходного круга (заданные x, y, r) находятся в этом круге.

Оттуда пройдитесь по всем точкам в большем из двух кругов дерева: если точка находится в меньшем круге, добавьте ее к результатам, если нет, запустите проверку расстояния.

Единственная проблема в том, что предварительное вычисление дерева занимает очень много времени. тем не менее, вы можете указать количество времени, которое вы хотите потратить, изменив количество веток x, y и r, которые вы хотите иметь в своем дереве.