Определить точки в пределах данного радиуса алгоритма

Question

Я не уверен, что это за математическая концепция, чтобы поддержать мой вопрос. ^^

Допустим, у нас есть PointA в качестве эталона. Задача состоит в том, чтобы найти точки вокруг PointA в заданном радиусе (используя координаты). Мой подход состоит в том, чтобы вычислить расстояние каждой точки (пифагорейской) и затем сравнить с данным радиусом Я уверен, что это будет отстой в плане сложности.

Какой алгоритм вы можете предложить? Пример кода, чтобы указать на вещи, будет высоко ценится. Спасибо.

Answer 1

Я бы начал с создания прямоугольника вокруг круга и сначала проверил, попадет ли в него что-нибудь.Тогда вы, вероятно, все время избегаете вычисления квадратов и квадратов.Выберите один край коробки (скажем, тот, что слева) и вычислите его значение x:

xMin = xOrigin - radius

Тогда все, что удовлетворяет

xTest < xMin

, можно игнорировать.Повторите что-то подобное для всех четырех сторон.В тот момент, когда тест не пройден, перестаньте работать над этим пунктом.Не делайте ненужных вычислений.

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

abs(sqr(xOrigin - xTest) - sqr(yOrigin - yTest))

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

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

Answer 2

Если ваши очки не проиндексированы, это на самом деле оптимальный алгоритм.Есть n точек, и для поиска всех из них потребуется O ( n ) времени при отсутствии какого-либо другого индекса.

Одна микрооптимизациячтобы пропустить операцию sqrt и сравнить сумму квадратов координатных дельт с квадратом желаемого радиуса.

Если вы собираетесь делать несколько запросов к одному и тому же набору данных, существуют различные индексациисхемы, которые вы можете использовать, которые требуют некоторого времени для вычисления (O (n log n)), но ускоряют поиск (O (m + log n), где m - количество найденных точек.)

kd-trees , вероятно, это то место, с которого можно начать там.

Answer 3

Ваша единственная сложность здесь - это расчет расстояния. Просто просейте и упростите этот расчет, и вы будете оптимальны.

Если вашим «центром» является A (x, y), то для любой точки B (x1, y1) рассмотрим:

1 / Если B находится в пределах требуемого расстояния d от точки B, из этого следует, что и x-x1 < d, и y-y1 < d. Сначала проверьте эти условия, чтобы отфильтровать все исключения «низко висящих фруктов».

2 / Вместо того, чтобы вычислять расстояние, рассчитайте квадрат расстояния и сравните его с квадратом максимально допустимого расстояния (которое вы, очевидно, должны пересчитывать и ссылаться, а не пересчитывать каждый раз). Это означает, что нет необходимости вычислять квадратный корень для каждой точки.

Это довольно незначительные оптимизации, но при условии, что точки не отсортированы и случайны, это лучшее, что вы получите.

Answer 4

Лучший ответ будет зависеть от количества измерений. Я предполагаю, что вы работаете в 2D или 3D пространстве.

Простой подход состоит в том, чтобы создать равномерную сетку размера ячейки, скажем, r. Затем поместите все точки в соответствующие ячейки.

Каждая точка запроса пересекает только горстку ячеек, скажем, 9. Вам нужно проверить только пересекающиеся ячейки.

Более эффективным подходом было бы создание дерева квадрантов или дерева KD (есть много других вариантов, но для 2D, дерева квадрантов или дерева KD)).

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

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