У меня есть набор 2d точек, распределенных случайным образом. Мне нужно выполнить трудоемкую операцию с небольшим подмножеством этих точек, но мне нужно сначала выяснить, над какими точками мне нужно выполнить эту трудоемкую операцию. Чтобы определить, какие точки мне нужны, они должны пройти ряд геометрических критериев.

Самые основные критерии - они находятся на определенном расстоянии от определенной точки. Вторым наиболее основным критерием является то, содержатся ли они в круговом секторе (двумерный конус), выходящем из этой конкретной точки. (Редактировать: эта операция вызывается регулярно с разными точками каждый раз, но с одним и тем же набором 2d точек.)

Моей первоначальной мыслью было создать сетку, содержащую 2d точки, а затем выполнить итерацию вдоль квадратов сетки захвата конуса, которые она пересекает. В зависимости от размера сетки, она отфильтровывает подавляющее большинство ненужных 2d точек. К сожалению, встроенная система, на которой я работаю, сильно ограничена в памяти, поэтому большой (по нашим стандартам, никто не использует) массив 2d будет слишком интенсивным.

Я пытался исследовать использование KD-деревьев для ускорения вычислений, но мне не удалось найти алгоритм, относящийся к круговым секторам и kd-деревьям.

Существует ли эффективный алгоритм для определения того, какие 2d точки лежат в круговом секторе?

Просто обратите внимание, что наша конкретная система медленна как в математике с плавающей запятой, так и в тригонометрии, поэтому решение, в котором задействовано меньшее количество из них, превосходит решение, которое требует много.