我有一组随机分布的2d点.我需要在这些点的一小部分上执行时间密集型操作,但我需要首先弄清楚我需要执行这个时间密集型操作的点.为了确定我需要什么点,他们必须通过一系列几何标准.
最基本的标准是它们在特定点的特定距离内.第二个最基本的标准是它们是否包含在从该特定点延伸出的圆形扇区(2-D锥形)内.(编辑:此操作定期调用,每次使用不同的特定点,但是相同的2d点集.)
我最初的想法是创建一个包含2d点的网格,然后沿着它相交的锥形抓取网格方块进行迭代.根据网格的大小,它将过滤掉绝大多数不需要的2d点.不幸的是,我正在运行的嵌入式系统受到严重的内存限制,所以一个大的(根据我们的标准而不是任何人),2d阵列会占用大量内存.
我一直在尝试使用KD树来研究加速计算,但我还没能找到一个关于圆扇区和kd树的算法.
是否有一种有效的算法来查找圆圈扇区中的2d点？
只是注意我们的特定系统在浮点数学和三角学方面都很慢,所以一个涉及较少的解决方案是一个需要大量的解决方案.