Encontrar puntos de manera eficiente dentro de un sector de círculo.

Tengo un conjunto de 2d puntos distribuidos al azar. Necesito realizar una operación que requiera mucho tiempo en un pequeño subconjunto de estos puntos, pero primero tengo que averiguar en qué puntos necesito realizar esta operación que requiere mucho tiempo. Para determinar qué puntos necesito deben pasar una serie de criterios geométricos.

El criterio más básico es si están a cierta distancia de un punto específico. El segundo criterio más básico es si están contenidos dentro de un sector circular (un cono 2-D) que se extiende desde ese punto específico. (Editar: esta operación se llama regularmente con un punto específico diferente cada vez pero con el mismo conjunto de puntos 2d).

Mi idea inicial fue crear una cuadrícula que contenga los puntos 2d, luego iterar a lo largo de la cuadrícula de agarre del cono que intersecta. Dependiendo del tamaño de la cuadrícula, filtraría la gran mayoría de los 2d puntos innecesarios. Desafortunadamente, el sistema integrado en el que estoy ejecutando está severamente limitado por la memoria, por lo que una matriz 2D grande (según nuestros estándares no es la de nadie) requeriría demasiada memoria.

He estado tratando de investigar el uso de árboles KD para acelerar el cálculo, pero no he podido encontrar un algoritmo que relacione sectores circulares y árboles-kd.

¿Existe un algoritmo eficiente para encontrar qué puntos 2d se encuentran dentro de un sector de círculo?

Solo una nota de que nuestro sistema en particular es lento tanto en matemática de punto flotante como en trigonometría, por lo que una solución que implique menos de esos es superior y requiere mucho.

Respuestas a la pregunta(2)

Su respuesta a la pregunta