我有一个图像,我想在鼠标移动到某些矩形区域时显示工具提示.矩形区域最多可以为1000.但是,只要检查每个矩形(如果该点在其中,即O(N)),则在移动鼠标时会使界面无响应.
有没有办法在低于O(N)的情况下做到这一点？我可以预先对矩形进行排序(我假设它是需要的).矩形可能(很少)重叠,但不超过4-5个矩形可以重叠在同一区域.在这种情况下,我可能需要获得所有矩形的列表,但即使只是其中任何一个仍然足够好.
但我假设这个问题已经由窗口管理员等解决了.
给定2D空间中的一组不同点,以及矩形(所有四个点的坐标,与xy轴平行的边),如何快速找到矩形内的哪些点？
我对通过所有点并看到哪个点位于矩形内的基本解决方案不感兴趣.我正在寻找的是一种算法,它可以为每个矩形提供快速的查询时间.
我不在乎我在预处理步骤中花了多少时间.我所关心的是,在处理完数据之后,我获得了一个有用的结构,它为每个矩形提供了快速的查询时间.
我知道例如我可以计算O(logN)中矩形内有多少个点.这是有效的,因为我在开始时做了很多繁重的处理,然后每次用新的矩形查询处理过的数据,并在logN时间内得到一个新的计数.我正在寻找一种类似的算法,用于找到实际的点,而不仅仅是它们的数量.