查找矩形内所有点的快速算法

亚历克斯

给定2D空间中的一组不同点和一个矩形(所有四个点的坐标,与xy轴平行的边),如何快速找到矩形内的点?

我对遍历所有点并查看矩形内的哪个点的基本解决方案不感兴趣。我正在寻找的是一种算法,它将为我提供每个矩形的快速查询时间。

我不在乎在预处理步骤中花费了多少时间。我关心的是,在处理完数据后,我得到了一个有用的结构,该结构为我提供了每个矩形的快速查询时间。

我知道例如我可以计算O(logN)中的矩形中有多少个点。之所以行得通,是因为我一开始做了很多繁重的处理,然后每次都用一个新的矩形查询处理过的数据,并在logN时间获得一个新的计数。我正在寻找一种类似的算法来查找实际点,而不仅仅是点数。

伊夫·达乌斯特(Yves Daoust)

一个经典的答案是kD树(在这种情况下为2D树)。

作为一种简单的替代方法,如果点的分布足够均匀,则可以通过网格进行尝试。

为方形网格选择像元大小(如果问题是各向异性的,则使用矩形网格)。将每个点分配给包含在链表中的网格单元。当您执行查询时,找到所有与矩形重叠的单元格并对其进行扫描以遍历其列表。对于部分覆盖的单元,您将需要执行矩形点测试。

大小的选择很重要:太大会导致太多点需要测试。太小会导致太多的空单元格。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

TOP 榜单

热门标签

归档