有效地找出落在边界框下的图像块

Question

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

感谢您的帮助。

Answer 1

如果我没看错你的问题，四叉树就是为这种事情而生的。它们是一个 4 元空间分区树。

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

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

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

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

四叉树只是这个基本思想的 'adaptive grid' 扩展。