Как посчитать количество точек внутри окружности (7 видео)

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

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

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

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

Содержание

6 ответов
Запросы на подсчет очков лежат внутри круга
Как рассчитать, сколько точек с координатами (x; y) находится в / на / вне круга
Решение
Другие решения
🌟 Видео

Видео:Как искать точки на тригонометрической окружности.Скачать

6 ответов

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

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

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

вы можете использовать 2D-дерево, так как точки ограничены плоскостью.

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

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

затем вы вызываете эту функцию с корнем KD-дерево

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

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

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

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

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

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

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

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

предполагая, что у вас есть набор точек S в декартовой плоскости с координатами (x_Я, y_Я), учитывая произвольный круг с центром (x_c, y_c) и радиус r вы хотите найти все точки, содержащиеся в этом круге.

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

три вещи приходят на ум, что может скорость это:

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

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

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

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

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

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

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

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

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

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

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

Видео:10 класс, 11 урок, Числовая окружностьСкачать

Запросы на подсчет очков лежат внутри круга

Даны n координат (x, y) точек на 2D плоскости и Q запросов. Каждый запрос содержит целое число r , задача состоит в том, чтобы подсчитать количество точек, лежащих внутри или на окружности круга, имеющего радиус r и центрированного в начале координат.

Примеры :

Уравнение для окружности с центром в начале координат (0, 0) с радиусом r, x 2 + y 2 = r 2 . И условие для точки в (x ₁ , y ₁ ) лежать внутри или на окружности, x ₁ 2 + y ₁ 2 2 .

Наивный подход может быть для каждого запроса, пройти через все точки и проверить условие. Это займет O (n * Q) сложность времени.

Эффективный подход состоит в том, чтобы предварительно вычислить x 2 + y 2 для каждой координаты точки и сохранить их в массиве p []. Теперь сортируем массив p []. Затем примените двоичный поиск по массиву, чтобы найти последний индекс с условием p [i] 2 для каждого запроса.

Ниже приведена реализация этого подхода:

// C ++ программа для определения количества точек, лежащих внутри или
// об окружности круга для Q запросов.
#include

using namespace std;

// Вычисление x ^ 2 + y ^ 2 для каждой заданной точки
// и сортируем их.

void preprocess( int p[], int x[], int y[], int n)

for ( int i = 0; i

p[i] = x[i] * x[i] + y[i] * y[i];

// Возвращаем количество точек лежащих внутри или по окружности
// круга, использующего бинарный поиск по p [0..n-1]

int query( int p[], int n, int rad)

int start = 0, end = n — 1;

while ((end — start) > 1) <

int mid = (start + end) / 2;

double tp = sqrt (p[mid]);

double tp1 = sqrt (p[start]), tp2 = sqrt (p[end]);

if (tp1 > (rad * 1.0))

return start + 1;

int n = sizeof (x) / sizeof (x[0]);

// Вычисляем расстояния всех точек и сохраняем

// расстояния отсортированы так, что запрос может

// работа в O (logn) с использованием бинарного поиска.

preprocess(p, x, y, n);

// Вывести количество точек в окружности радиуса 3.

// Вывести количество точек в окружности радиусом 32.

// JAVA-код для запросов на счет
// точки лежат внутри круга

// Вычисление x ^ 2 + y ^ 2 для каждой заданной точки

public static void preprocess( int p[], int x[],

for ( int i = 0 ; i

p[i] = x[i] * x[i] + y[i] * y[i];

// Возвращаем количество точек лежащих внутри или на

// окружность круга с использованием двоичного

public static int query( int p[], int n, int rad)

int start = 0 , end = n — 1 ;

while ((end — start) > 1 ) <

int mid = (start + end) / 2 ;

double tp = Math.sqrt(p[mid]);

double tp1 = Math.sqrt(p[start]);

double tp2 = Math.sqrt(p[end]);

if (tp1 > (rad * 1.0 ))

return start + 1 ;

/ * Программа драйвера для проверки вышеуказанной функции * /

public static void main(String[] args)

// Вычисляем расстояния всех точек и сохраняем

// расстояния отсортированы так, что запрос может

// работа в O (logn) с использованием бинарного поиска.

int p[] = new int [n];

preprocess(p, x, y, n);

// Вывести количество точек по кругу

System.out.println(query(p, n, 3 ));

// Вывести количество точек по кругу

System.out.println(query(p, n, 32 ));

>
// Этот код предоставлен Арнавом Кр. Мандал.

# Python 3 программа для поиска номера
# точки лежат внутри или на окружности
# круга для Q запросов.

# Вычисление x ^ 2 + y ^ 2 для каждого
# заданные баллы и сортировка их.

def preprocess(p, x, y, n):

for i in range (n):

p[i] = x[i] * x[i] + y[i] * y[i]

# Возвращаемое количество очков лежит внутри
# или по окружности, используя
# бинарный поиск на p [0..n-1]

Видео:Всё про углы в окружности. Геометрия | МатематикаСкачать

Как рассчитать, сколько точек с координатами (x; y) находится в / на / вне круга

У меня есть программа, чтобы написать в моем курсе C ++. В координатной плоскости имеем окружность с радиусом R. Центр круга находится в точке (xc, yc). Также у меня есть n точек с координатами (например, n = 2 и координаты (1; 1) (-1; -1). Мне нужно вычислить, сколько точек есть в окружности, на ней и за ее пределами .. Пожалуйста помоги 🙂

Видео:Длина окружности. Площадь круга - математика 6 классСкачать

Решение

Вам необходимо рассчитать расстояние между центром круга и точкой. Формула расстояния между двумя точками:

где: (xc, yc) — координаты центра круга, (x, y) — координаты вашей точки.

если расстояние больше радиуса, то точка находится за пределами окружности (d> R)

Затем вам нужно повторить это для n точек и запомнить, сколько из них внутри и сколько снаружи. и это все.

Теперь у вас есть алгоритм, который вы можете попробовать закодировать!

Видео:Coordinates on Circle - Координаты точек окружностиСкачать

Другие решения

Поверхность квадрата рассчитывается по S = pi*r^2
заданный r в пикселях, S будет в пикселях …

Стоит отметить, что этот метод является приближенным, потому что он не над дискретной плоскостью

Чтобы быть более точным (хотя и значительно медленнее):
обратитесь к ответу @Sandro и проверьте расстояние до каждой точки на вашей плоскости.
с двумя оптимизациями, которые вы можете рассмотреть:

исключить внешнюю ограничивающую рамку
Вам нужно проверить только пиксели x in [xc — r, xc + r] U y in [yc — r, yc + r]

автоматически включать вписанный квадрат
Вы можете включить каждый пиксель в x in (xc — sqrt(2)r, xc + sqrt(2)r) U (yc — sqrt(2)r, yc + sqrt(2)r)

Уравнение круга: R^2 = (xc — x)^2 + (yc-y)^2 где (xc, yc) координаты центра круга. (x, y) — координаты точки, R — радиус. Так: