我有一张图片，当鼠标移过某些矩形区域时，我想显示工具提示。矩形区域最多可以有 1000 个。但是，如果仅检查每个矩形是否有点在其中，即 O(N)，则会在移动鼠标时使界面无响应。
有没有办法在小于 O(N) 的时间内做到这一点？我可以事先对矩形进行排序（我假设它是需要的）。矩形可能（很少）重叠，但不超过 4-5 个矩形可以重叠同一区域。在这种情况下，我可能需要获取所有矩形的列表，但即使只是其中任何一个都足够好。
但我假设这个问题已经被窗口管理器等解决了。
问问题
348 次
4 回答
2
一种比图像树（以及可以渲染到相当小的图像上的网页）更快、更简单（尽管内存效率更低）的方法是使用模板。即，如果您有一个 x x y 像素的图像，请创建一个 x x y 大小的二维数组，并使用您的工具提示 ID 填充它。这具有从像素位置到 O(1) 的 ID 的搜索速度（我最喜欢的 O）
于 2013-05-16T10:08:38.087 回答
1
使用空间搜索数据结构，例如四叉树。
您需要事先将矩形添加到树中，但平均搜索速度会很快。在最坏的情况下，您可能仍然有 O(N)。
于 2013-05-16T09:57:18.407 回答
1
如果矩形是轴对齐的，则可以避免使用专门的数据结构。
首先将空间一维细分，例如将屏幕水平细分为垂直条带。每个矩形可以是多个条带。然后根据与该条重叠的矩形细分每个条。然后搜索涉及两个 O(log n) 二进制搜索或二叉树 - 一个用于识别条带，一个用于识别哪个矩形。
这是一种公认的空间数据结构，但对我来说它并不重要——它只是使用普通的二叉树。你甚至可以用std::map<int, std::map<int, int>>.
但实际上有一个支持 O(1) 搜索的选项，称为“像素选取”。基本上，在屏幕外的位图中绘制矩形，每个矩形使用不同的颜色，最前面的矩形最后是正常绘图（画家算法）。您可以通过简单地读取该像素来识别哪个矩形在任何点最前面。
额外的好处——你的显卡甚至可以加速绘制矩形，所以当矩形集发生变化时你不需要太担心重绘（这显然不包括在那个 O(1) 中）。它的内存有点贵，但在现代机器上，你可能不在乎。
于 2013-05-16T10:09:11.943 回答