¿Hay un algoritmo para encontrar puntos cercanos usando solo coordenadas polares?

Question

Supongamos que tengo un vector de puntos como coordenadas polares.

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

¿Existe un algoritmo para hacer esto sin convertirlos a formato cartesiano?

Answer 1

Está buscando las distancias para las coordenadas polares. Puede encontrar la fórmula en este link.

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

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

Answer 2

tener cuidado, si va a ampliar su algoritmo para muchos puntos, el sondeo de los puntos adyacentes es mejor hacerlo utilizando un índice espacial. No estoy al tanto de la existencia de índices espaciales usando coordenadas polares, y estoy seguro de que serían un poco complejos de implementar/usar. Así que si usted tiene:

• un montón de puntos, la sonda
• con más frecuencia que los puntos en movimiento,

hacerse la pregunta si debe usar coordenadas cartesianas y un índice espacial.

hacer sus propios cálculos de acuerdo con su caso de uso típico:

1. Usando cartesiano junto coordenadas polares:

   • conversión polar a cartesiano se realiza sólo cuando un punto se mueve, e involucrar a dos trigonométrica funciones;
   • Encontrar puntos más cercanos que una cierta distancia a otro 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 aparte de adds/multiplicalies (ni siquiera raíces cuadradas, se compara la distancia al cuadrado).

2. utilizando sólo coordenadas polares:

   • Scanning para todos los puntos w/o índice espacial es O (n);
   • Esto implica una función trigonométrica por comparación (por lo tanto n llamadas trigonométricas por sonda).

Sé consciente de que están llenas de sangre TRIGS costoso en tiempo de cálculo.