algorithm - 布置矩形以避免碰撞(算法帮助)

Question

我有一个(大)水平 ScrollView ，我想在上面放置一堆矩形。每个矩形都有一个所需的水平位置，但如果需要，它可以从该位置变化到一定量(常数 K)。矩形不得重叠。矩形的垂直位置是任意的(当然，受限于 View 的高度)。

理想情况下，我希望矩形的大小可变……我想如果这不可能的话，我可以让大小仅在一个维度上变化。

现在，这种布局将有一些不可能:因为只有一定量的垂直空间，而且它们只能水平移动 K 个像素远离理想状态，可能无法绘制所有矩形。为了解决这个问题，每个矩形都有一个优先级(P)，优先级较低的矩形应该首先被忽略。 (您可以假设这是明确的，并且您始终可以判断任意两个矩形中的哪一个具有更高的优先级。)

我追求的是概念性算法，但如果您需要具体细节，这将在 iPad 上运行，并且将有几千个(>1000 但 <10,000)个矩形需要考虑。理想情况下，我希望每次用户更改缩放级别时能够足够快地重新运行，但如果这不容易，那么我可以缓存这些位置。这些对象是时间轴上的照片，我想让它们大致接近事件发生的时间——我将进行近似以便在那里放置更多对象。

我见过像 this 这样的算法，它执行不相交的技巧，但对于每个项目只允许移动一定数量没有相同的想法。显然，如果没有后一个约束，您可以显示所有项目，因此我还需要一些方法来了解在什么时候不能显示更多的矩形。

如果按照描述解决问题太困难，我欢迎提出更实用的想法。如果一切都失败了，我总是可以按照优先顺序做一些事情，如果可以的话，将每个项目渲染到它想要的位置，如果不能，那么尝试垂直移动它，如果仍然不行，那么将它水平移动到允许的限制，在继续下一个之前。优先顺序意味着可能会找到一个次优的解决方案，但它会被加权到最重要的项目。

Answer 1

这是我认为可以做到的一种方式。

第 1 步是找出可以放置新黄色矩形的所有位置。不失一般性，我们可以将其存储为矩形左上角所有可能的 X-Y 位置的列表。自然地，对于如此庞大的起始区域，列表将包含数百万个条目，因此为了节省空间，让我们以一组矩形区域的形式存储此列表。

例如，如果我们的屏幕有从 X=0 到 X=2999(含)和从 Y=0 到 Y=999(含)的像素，并且我们的新矩形的宽度为 300 像素，高度为 150 像素，则左上角我们的新矩形可以出现在从 (X,Y) = (0, 0) 到 (2699, 849) 的任何位置。让我们将其存储为四元组 [0, 0, 2699, 849]。

现在，当我们将每个现有的(红色)矩形放到屏幕上时，其中一些可能性就被排除了，因为它们会导致新的(黄色)矩形与它们重叠。例如，如果有一个红色矩形 [1100, 200, 1199, 299]，那么我们的黄色矩形的左上角不能位于从 (X,Y) = (801, 51) 到 (1199, 299) 的任何位置包容性。

因此，将 [0, 0, 2699, 849] 替换为四个矩形区域，它们覆盖相同的区域但留下空隙。有很多方法可以做到这一点，但这里有一个:[0, 0, 1199, 50], [1200, 0, 299, 2699], [0, 51, 800, 849], [801, 300, 2699, 849 ].

继续向屏幕添加更多红色矩形。每次添加一个时，从列表中减去更多可能性(这通常会导致列表包含更多、更小的“安全区域”)。 (对于上面有 1000 多个矩形的全屏来说，这可能非常耗时；相反，如果您只从提到的 [X-K, 0, X+K, H] 空间开始，那么 1000 个矩形中的相对较少+ 将与此重叠并且计算将进行得更快。)这段代码应该非常小心地编写并进行大量单元测试，因为 fencepost 错误会比比皆是。

最终结果是屏幕上可以放置新黄色矩形左上角的可能位置的完整列表，以矩形区域列表的形式表示。

第 2 步:浏览此列表并选择最理想的位置。任何实际与理想垂直线相交的矩形区域都将优先。但也有可能没有。在这种情况下，您可以从落在理想线左侧的区域和落在理想线右侧的区域中选择最可取的选项。提示:在每种情况下只需要考虑每个区域的一个角(右侧区域的左上角，左侧区域的右上角)。