Java - 在数组中搜索矩形(这样做的有效方法)

Question

我有一个数组，其中包含一个对象，其中有不同的变量(矩形、图像等...)

我正在寻找一种有效的方法来保存数组，并寻找一种有效的方法来搜索它。

我需要每次搜索所有对象的矩形在渲染范围内

有没有好的、高效的、快速的方法呢？

Answer 1

根据您修改“要呈现的事物”数组的频率与尝试在其中搜索事物的频率相比，您可能会从查看数据的不同方式中获益。假设您只是偶尔修改数组，所以您有一些 Renderable 对象数组，其中每个 Renderable 都有一个返回矩形的 getOutline():

Renderable[] arr = new Renderable[] { /* whatever */ };

加速频繁搜索的规范解决方案是根据您搜索的属性对数组进行排序，然后使用 O(log n) 而不是 O(n) 的二进制搜索，就像遍历数组一样。在这种情况下，您不能这样做，因为您基本上是在 2/4 属性/键上建立索引:每个矩形的 X 范围和 Y 范围。

你可以做的是 四个 数组由相同的对象组成(因为它们是引用，空间成本并不大)并且每个数组都按相应的四个属性之一排序矩形:“顶部”(最小 Y)、“底部”(最大 T)、“左侧”(最小 X)和“右侧”(最大 X)。例如，您可以像这样定义其中之一:

Comparator<Renderable> topComp = (r1, r2) -> r1.getOutline().top - r2.getOutline().top;
Renderable[] byTop = Arrays.stream(arr).sorted(topComp).toArray(Renderable[]::new);
// The same goes for byBottom, byLeft and byRight

中间的第一行使用 lambda 创建了一个 Comparator，该 lambda 对您的 Renderable 对象施加了一个与其顶部坐标的自然排序相同的排序。它可以替换为 Comparator.comparingInt(r -> r.getOutline().top);，因为 Comparator 接口(interface)具有静态方法来创建执行此操作的比较对象。

现在，当您有一个要绘制的区域时，您可以使用二进制搜索来快速找到哪些矩形与其重叠:

// We'll say that the variable "reg" contains a rectangle that needs to be redrawn
// We'll make it a fake Renderable so "it" can be searched in the arrays
Renderable rReg = new FakeRenderable(reg);
int topPos    = Arrays.binarySearch(byTop,    rReg, topComp);
int bottomPos = Arrays.binarySearch(byBottom, rReg, bottomComp);
// etc for leftPos and rightPos

执行 4 O(log n) 次查找后，每个 xPos 变量可能为正或负。

• 如果为正(或零)，则意味着返回的索引是数组中第一个与给定键等于的对象的索引。索引将数组划分为“小于键”和“大于或等于键”——如果您想将“等于”对象留在左侧，只需搜索一个比键大的键。
• 如果为负，则没有对象与您的键完全相等，值为 (-(insertion point) - 1)，其中插入点是第一个元素的索引大于 key 。因此，iFirstGreater = -(x + 1); 其中 x 是 binarySearch 返回的值。然后，iFirstGreater 将数组划分为“小于键”和“大于键”。

因此，在任何情况下，索引都会对四个数组进行分区。您在四个排序数组中有四个索引，告诉您哪些可渲染对象的“顶部”坐标高于/低于您所在区域的顶部，哪些可渲染对象的“底部”位于您所在区域的上方/下方，左右字段相同。使用该信息，您可以决定每个可渲染对象是否是

• 绘图区外(应忽略)
• 在绘图区内(且应完整绘制)
• 重叠绘图区域(应该部分绘制/裁剪)