java - 有效地找出落在边界框下的图像 block

Question

我在 Java 工作。我有一个由随机大小的矩形瓷砖组成的大图像。我想在我的程序中以这种方式存储有关这些图 block 的信息，即给定一个矩形边界框，我可以快速找出哪些图 block 将落入该矩形内。目前我正在通过遍历每个图 block 边界框来检查它。但我正在寻找一种快速找到它的方法，因为图 block 的数量非常多。

感谢您的帮助。

Answer 1

如果我正确理解你的问题，四叉树就是为这种事情而制作的。它们是一个 4 元空间划分树。

一个基本的实现是这样的:

1. 从一个包含整个图像的大根节点开始包含它的边界矩形。它目前是一片叶子(没有 child )。
2. 现在开始向其中插入元素(您的矩形)。
3. 当插入到一个节点时，如果它是一个叶节点，如果它还没有太多元素(例如:少于 4 个)，则插入该元素。如果它也有许多元素，把那片叶子分成 4 个象限，把它变成分支，并将元素转移到适当的象限。如果是分支，则将该元素插入到适当的子象限。
4. 重复直到插入所有内容，在此过程中形成搜索层次结构。

现在，当您想找出搜索矩形内有哪些元素(矩形)时，从该结构的根部开始，递归地向下进入与该矩形相交的象限，直到到达叶节点，此时您可以只检查那些叶节点内的元素。

另一种更简单并且更适用于非常动态的数据(例如:如果您的矩形在每一帧周围移动)的方法是固定大小的 NxN 网格。只需将您的元素(矩形)插入它们相交的单元格中。搜索时，只需搜索与搜索矩形相交的网格单元格内的元素。

四叉树只是这一基本思想的“自适应网格”扩展。