¿Hay un algoritmo para encontrar puntos cercanos usando solo coordenadas polares? - algoritmo, geometría computacional

Supongamos que tengo un vector de puntos como coordenadas polares.

Supongamos que uno de esos puntos actúa como una sonda para la cual quiero encontrar todos los otros puntos dentro de una cierta distancia.

¿Hay un algoritmo para hacer esto sin convertirlos a la forma cartesiana?

Respuestas

Estás buscando la distancia para las coordenadas polares. Puedes encontrar la fórmula en este enlazar.

La distancia entre los puntos (r1, a1) y (r2, a2) es:

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

Tenga cuidado, si planea escalar su algoritmo a muchos puntos, es mejor hacer una prueba de los puntos cercanos utilizando un índice espacial. No estoy al tanto de la existencia de índices espaciales que usan coordenadas polares, y estoy seguro de que serían un poco complejos de implementar / usar. Así que si tienes:

• muchos puntos,
• sondeo más frecuentemente que los puntos en movimiento,

pregúntese si debe usar coordenadas cartesianas y un índice espacial.

Haga las cuentas usted mismo de acuerdo con su caso de uso típico:

1. Usando cartesiano junto con coordenadas polares:

   • La conversión de polar a cartesiano se realiza solo cuando un punto se mueve e involucra dos funciones trigonométricas;
   • Encontrar puntos más cercanos que una cierta distancia aotro punto se puede hacer en O (1) tiempo (dependiendo de la distancia promedio, el tamaño del índice espacial, el número de puntos ...), y no implica nada más que sumas / multiplicaciones (ni siquiera raíces cuadradas, comparas la distancia al cuadrado).

2. Usando solo coordenadas polares:

   • La exploración de todos los puntos sin índice espacial es O (n);
   • Esto implica una función trigonométrica por comparación (por lo tanto norte llamadas trigonométricas por sonda).

Tenga en cuenta que los trigon son más caros en el tiempo de cálculo.