找出点是否在小于O(N)的N个(可能重叠)矩形中的一个内
我有一个图像，我想在鼠标移动到某些矩形区域时显示工具提示。矩形区域可以达到1000。但是，只要检查每个矩形中的点是否在其中，即O（N），就会使界面在移动鼠标时没有响应。
有没有小于O(N)的方法？我可以预先对矩形进行排序(我假设这是必需的)。矩形可能会(很少)重叠，但同一区域重叠的矩形不能超过4-5个。在这种情况下，我可能需要获得所有矩形的列表，但即使只是其中的任何一个也足够了。
但是我假设这个问题已经由窗口管理器等解决了。
共有3个答案
如果矩形是轴对齐的，你可以避免特殊的数据结构。
首先将空间细分为一个维度，例如将屏幕水平细分为垂直条带。每个矩形可以位于多个条带中。然后，根据与该条带重叠的矩形细分每个条带。然后，搜索涉及两个O（log n）二进制搜索或二叉树 - 一个用于识别条带，一个用于识别哪个矩形。
这是一个公认的空间数据结构，但对我来说，它并不重要-它只是使用普通的二叉树。您甚至可以使用＜code＞std:：map来实现
但实际上有一个选项支持O（1）搜索，称为“像素拾取”。基本上，在屏幕外的位图中绘制矩形，每个矩形具有不同的颜色，最前面的矩形最后，就像普通绘制（painters算法）一样。您只需读取该像素，即可在任何时候识别哪个矩形最靠前。
额外的好处-您的图形卡甚至可以加速绘制矩形，因此当矩形集发生变化时，您不必太担心重新绘制（这显然不包括在O（1）中）。它的内存有点贵，但在现代机器上，你可能不在乎。
对于图像（以及可以呈现到相当小的图像上的网页）的树，一种更快，更简单（尽管内存效率较低）的方法是使用模具。即，如果您有 x x x 像素的图像，请创建一个大小为 x x x y 的二维数组，并使用工具提示 ID 填充它。这具有从像素位置到O（1）ID的搜索速度（我最喜欢的O）
听起来您想将矩形存储在R-Tree中，然后查询它。有一些可用的实现：
- JTS拓扑套件（Java）
- Net拓扑套件（. net）
- GeoTools（. net）
查看他们的 STRtree 类。
-
面试问题: 给定数十亿个矩形，找到与给定点P（x，y）重叠的最小面积矩形 有一种简单的方法通过顺序地处理每个矩形来在O（n）时间内实现答案，但进一步优化它提供了大量的矩形阵列。 我最好的方法是检查每个矩形，看看点是否在里面，然后计算面积并与当前最小的面积进行比较。这可以一次完成。我想不出任何其他不需要检查所有矩形的方法
-
我试图找出两个矩形是否相互重叠。我将下面的矩形表示为< code>[x1，x2] x [y1，y2] 我只需要一个伪代码，我可以实现它来查找矩形是否彼此重叠。
-
我正在寻找一个算法来查找并打印给定圆的交点。每个圆由其中心和半径指定。 O(n2)算法包括检查中心之间的距离是否小于或等于（被比较的两个圆的）半径之和。然而，我正在寻找一个更快的！ 一个类似的问题是线段的相交。我想即使我的问题可以解决使用行扫描算法，但我无法弄清楚如何修改事件队列在情况下的圆。
-
问题内容： 是 是 是 是 当他们有相同的基础时，我可以为他们做；当他们的基础不一样时，我无法弄清楚-我知道这些都是对的。 问题答案： 记录双方的日志。这是允许的，因为log是单调递增的函数
-
本文向大家介绍找出Python中具有n个或更少点的可能性的程序，包括了找出Python中具有n个或更少点的可能性的程序的使用技巧和注意事项，需要的朋友参考一下 假设我们正在玩一个独特的游戏，并且我们有三个值n，k和h。我们从0点开始，然后我们可以从1到h（包括1和h）之间随机选择一个数字，然后得到那么多点。当我们获得至少k分时，我们将停止。我们必须找到n点或更少点的概率。在这里，可以随机选择任何数
-
我有一个问题，也许可以用计算机屏幕上的窗口来最好地说明：创建另一个尽可能大的窗口，不与任何现有窗口重叠。 换句话说：在有限表面（一张纸或一块屏幕）上给定一组N个矩形，找到可以安装在这些矩形之间的最大矩形。（坐标可以是任意的，因此位图在这里不是可行的解决方案。 下面的照片显示了三个矩形(黑色)和最大的矩形(红色)。 http://www.irstafoto.se/blogmtrl/rectangle