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

Question

Предположим, у меня есть вектор точек в качестве полярных координат.

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

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

Answer 1

Вы ищете расстояние для полярных координат. Вы можете найти формулу в этой ссылке .

Расстояние между точками (r1, a1) и (r2, a2) равно:

D = sqrt(r1*r1 + r2*r2 - 2*r1*r2*cos(a1-a2))

Answer 2

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

• много точек,
• проверяют чаще, чем движущиеся точки,

задайте себе вопрос, следует ли использовать декартовы координатыи пространственный индекс.

Выполните математику самостоятельно в соответствии с вашим типичным вариантом использования:

1. Использование декартовой системы наряду с полярными координатами:

   • Преобразованиеполярное на декартово выполняется только при перемещении точки и включает две тригонометрические функции:
   • Нахождение точек, ближайших к определенному расстоянию до другой точки, может быть выполнено за O (1) время (в зависимости от среднего расстояния,Размер пространственного индекса, количество точек ...), и не включает ничего, кроме сложения / умножения (даже квадратные корни, вы сравниваете расстояние в квадрате).

2. Использование только полярных координат:

   • Сканирование для всех точек без пространственного индекса равно O (n);
   • Это включает в себя одну тригонометрическую функцию на сравнение (таким образом N тригговых вызовов на один зонд).

Имейте в виду, что триггеры кроваво дороги во время вычислений.