我有许多元素需要使用 javascript 添加到页面，其中包含从服务器提取的数据及其位置信息。我想安排它们，以免重叠。例如，element 5将移动到细绿色框所在的位置，使其不重叠element 3。
我已经成功创建了一个决定两个框是否重叠的函数。例如，如果我运行overlaps($('#element5')[0],$('#element3')[0])它会返回true.
但是，使用此函数，我将不得不遍历每个元素并将其与其他所有元素进行比较。因此，对于 50 个元素，我需要运行该overlays函数 1275 次，这需要很长时间才能加载。
我决定最好先创建一个 rtree 来组织元素，这样我就可以轻松计算出运行覆盖函数所需的 2 个元素，从而显着减少覆盖函数的运行次数。但是，我对这将如何工作感到非常困惑。我将如何组织它们，以便我只需要运行少量的函数？rtree 的 2 个边界框不会重叠并使这种技术变得多余吗？最好的方法是什么？
在 R-tree 中，矩形页面确实可以重叠。
搜索重叠时，您必须同时探索这两个组。
但是 r-tree 中重叠页面的数量不应该太大（除非树的构建非常糟糕），所以这仍然会产生很好的加速。假设您在 5 个页面中有 50 个元素，每个页面有 10 个元素，您首先必须测试 5 个顶级页面，然后可能会在这些页面的 0-2 个中测试 10 个元素，因此可能只有 15 个重叠测试而不是 50 个。确切的数字当然会有很大差异。
但是，对于 HTML 解决方案，我会考虑使用基于网格的近似值。将您的表面划分为 10x10 个单元格。每个单元格都包含与此网格单元格重叠的矩形的引用。
在测试重叠时，您查看查询矩形所接触的网格单元，收集所有引用的现有矩形，然后仅对这些矩形进行重叠测试。如果您在每个单元格中存储两个列表 - “部分重叠”和“完全重叠”，您甚至可以跳过许多重叠测试：如果一个网格单元格被另一个单元格完全重叠，它们将在某处重叠。
另一种方法是按 X 轴对矩形进行排序，以快速缩小实际上可以与二分搜索重叠的矩形的数量。这也应该大大减少交叉路口呼叫的数量。
哦，最后但同样重要的是：1275 重叠测试无论如何都不应该花费很多时间。无论如何，这是您正在谈论的一个很小的数据集。R-trees 和类似方法适用于具有数百万个项目的数据集。