logo标签列表

在小于O(N)的时间复杂度内，确定一个点是否在N个（可能重叠的）矩形中的其中一个内部。

c++algorithm
8
我有一张图片，希望在鼠标移动到某些矩形区域时显示工具提示。这些矩形区域最多可以达到1000个。但是，仅检查每个矩形的点是否在其中，即O（N），会使界面在移动鼠标时反应迟缓。
有没有办法以小于O（N）的复杂度来解决呢？我可以预先对矩形进行排序（我假设这是必要的）。矩形可能会（很少）重叠，但是不超过4-5个矩形可以重叠同一个区域。在这种情况下，我可能需要获取所有矩形的列表，但即使只是其中任何一个也足够好。
但我认为这个问题已经被窗口管理器等解决了。
1
虽然这是一个算法问题，但所涉及的接口/上下文可以提供更好的建议 - 例如，Web页面/JavaScript环境解决方案与C ++绘图应用程序解决方案不同。 - Déjà vu
@ring0 好的，我正在使用C ++和Qt，并可视化OCR的输出，该输出包括边界框+识别符号+其他数据。 - sashoalm
谢谢提供信息。我对Qt不是很熟悉，但正如你建议的那样，它可能根据“深度”和位置处理基于窗口（小部件）-因此至少应该可以立即获取鼠标“下”的“顶部”矩形（就像浏览器通过核心算法一样）。而且这似乎是一个提示；还需要更多研究才能获得所有矩形的列表（即来自所有深度）。 - Déjà vu
4个回答
7
2

对于图像（和可以渲染成相对较小的图像的网页），比使用树更快更简单（尽管内存效率稍差）的方法是使用模板。例如，如果您有一个 x 乘 y 像素的图像，请创建一个大小为 x 乘 y 的二维数组，并用工具提示 ID 填充它。在此情况下，从像素位置到 ID 的搜索速度为 O(1)（我最喜欢的 O）。

这是一个好的解决方案 :) 实际上，这就是我在遇到问题后立即采取的措施，但它更像是一种权宜之计而不是解决方案，这就是为什么我想知道是否有更优雅的解决方案。 - sashoalm
1

使用空间搜索数据结构，例如四叉树。

你需要事先将你的矩形添加到树中，但平均搜索速度会很快。在最坏情况下，搜索时间可能仍然是O(N)。

有没有任何链接提供关于四叉树的有趣且视觉化的信息，并解释它如何在这个问题/上下文中发挥作用？ - Déjà vu
@ring0：通常的嫌疑犯，维基百科。 - n. m.
谢谢。有些人在他们的解决方案中包含链接，让懒惰的其他人（比如我）可以直接点击而不是搜索。 - Déjà vu
@ring0：通常我都会包含链接，除非我在手机上打字（因为我也懒）。 - n. m.
1
如果矩形是轴对齐的，您可以避免使用专门的数据结构。
首先在一个维度上将空间进行细分，例如将屏幕水平划分为垂直条带。每个矩形可能在多个条带中。然后，根据重叠该条带的矩形来细分每个条带。搜索涉及两个O(log n)二进制搜索或二叉树——一个用于识别条带，一个用于识别哪个矩形。
这是一种公认的空间数据结构，但对我来说它并不真正算作——它只是使用普通的二叉树。您甚至可以使用std::map>来完成。
但实际上还有一种支持O(1)搜索的选项，称为“像素拾取”。基本上，在离屏位图中绘制矩形，每个矩形都以不同的颜色绘制，并按照正常绘图（画家算法）的方式最后绘制前面的矩形。您可以通过简单地读取该像素来确定任何点最前面的矩形。
额外的好处——您的显卡甚至可以加速绘制矩形，因此当矩形集合更改时，您不需要过多担心重绘（这显然不包括在O(1)中）。它在内存方面有点昂贵，但在现代计算机上，您可能并不关心。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接