12

下午好。

我的情况：

  • 在二维空间中。
  • 输入：一组矩形（也有重叠的矩形）。
    • 矩形坐标是整数类型。
    • 矩形大小和矩形位置没有任何限制（仅整数范围）。
    • 没有矩形的宽度=0 或高度=0。
  • 我需要找到：所有包含输入点的矩形（带有整数坐标）。

查找包含输入点的矩形。

问题：

  • 保持矩形的有效结构是什么？
  • 在这种情况下什么算法是有效的？
    • 什么算法只对添加矩形而不删除有效？

谢谢 ：-）。

4

5 回答 5

21

R-Tree 是最适合这个用例的数据结构。R-树是用于空间访问方法的树数据结构，即用于索引多维信息，例如地理坐标、矩形或多边形。所有矩形的信息都可以以树的形式存储，因此搜索会很容易

维基百科页面、简短的 ppt和研究论文将帮助您理解这个概念。

在此处输入图像描述

于 2012-04-22T16:18:59.810 回答
3

在 java 中你可以使用 shape.contains

但一般来说，假设一个矩形是由 (x,y,width,height) 定义的

如果 (pt.x >= x && pt.x <= x + 宽度 && pt.y >= y && pt.y <= y + 高度) ...

如果集合中有所有矩形，则可以遍历集合并找到包含该点的矩形

于 2012-04-22T15:25:31.063 回答
3

看起来您的矩形集可能是动态的（“...用于添加矩形...”）。在这种情况下 - 二维区间树可能是解决方案。

于 2012-04-22T16:21:49.343 回答
2

一个矩形(left, top, right, bottom)包含一个点(x, y)if left < x < right and top < y < bottom（假设坐标向下增加，这是我见过的大多数硬件的情况；如果你的坐标向上增加，更传统的数学情况，交换top和bottom）。你不会比测试更有效率。

如果您将矩形视为“包含”一个点（如果它也在边界上），则将所有<s替换为<=.

至于如何处理矩形集合...我不知道。我认为按角坐标排序的列表会做一些事情，但我并没有真正看到它有多大好处......最多，你会平均将要检查的东西列表减少一半（最坏的情况仍然需要检查所有内容）。一大堆该死的一半仍然可以是一大堆。:)

于 2012-04-22T15:29:02.297 回答
2

这是一个简单的解决方案。

  1. 在您的平面上定义一个网格。
  2. 每个单元格维护两个列表：完全覆盖该单元格的矩形和部分覆盖该单元格的矩形。
  3. 在每次插入时，将目标矩形的 ID 放入所有涉及的单元格列表中。
  4. 在每个查询中，找到包含目标点的单元格，输出完全覆盖列表并在部分覆盖列表上运行扫描。
于 2012-04-22T16:42:20.460 回答