Има ли алгоритъм за намиране на близки точки, използвайки само полярни координати? - алгоритъм, изчислителна геометрия

Да предположим, че имам вектор с точки като полярни координати.

Да предположим, че една от тези точки действа като сонда, за която искам да намеря всички други точки в рамките на определено разстояние.

Има ли алгоритъм за това, без да ги конвертирате в картезианска форма?

Отговори:

Търсите разстоянието за полярните координати. Можете да намерите формулата в това връзка.

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

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

Бъдете внимателни, ако имате намерение да увеличите своя алгоритъм до много точки, пробирането за точки в близост е по-добре да се направи с помощта на пространствен индекс, Не знам за съществуването на пространствени индекси, използващи полярни координати, и съм сигурен, че ще бъдат малко сложни за внедряване / използване. Така че, ако имате:

• много точки,
• сонда по-често от движещите се точки,

задайте въпроса дали трябва да използвате декартови координати и пространствен индекс.

Извършете сами математиката според типичния случай на използване:

1. Използване на картезиански заедно с полярните координати:

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

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

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

Имайте предвид, че trigs са кървави скъпо в изчислителното време.