Eu tenho um conjunto de 2d pontos distribuídos aleatoriamente. Preciso realizar uma operação com uso intensivo de tempo em um pequeno subconjunto desses pontos, mas primeiro preciso descobrir em que pontos preciso executar essa operação intensiva de tempo. Para determinar quais pontos eu preciso, eles devem passar uma série de critérios geométricos.

Os critérios mais básicos são eles estão dentro de uma certa distância de um ponto específico. O segundo critério mais básico é se eles estão contidos dentro de um setor circular (um cone 2-D) que se estende a partir desse ponto específico. (Edit: esta operação é chamada regularmente com um ponto específico diferente de cada vez, mas o mesmo conjunto de 2d pontos).

Meu pensamento inicial foi criar uma grade contendo os 2d pontos e, em seguida, iterar ao longo dos quadrados da grade de captura do cone que ela cruza. Dependendo do tamanho da grade, filtraria a grande maioria dos 2d pontos desnecessários. Infelizmente, o sistema embarcado em que estou executando está severamente restrito à memória, de modo que um array 2d grande (de acordo com os nossos padrões, nem todos os outros) seria muito intensivo em memória.

Eu tenho tentado investigar o uso de árvores KD para acelerar o cálculo, mas não consegui encontrar um algoritmo relacionado a setores de círculo e árvores-kd.

Existe um algoritmo eficiente para descobrir quais pontos 2d estão dentro de um setor circular?

Apenas uma nota que nosso sistema particular é lento tanto em matemática de ponto flutuante quanto em trigonometria, de modo que uma solução que envolva menos deles é superior a uma que exige muito disso.