algorithm - 高效地将二维平面投影到一维线上

Question

我有一个 [width, height, x, y] 向量数组，如下所示:[[width_1, height_1, x_1, y_1],...,[width_n, height_n, x_n, y_n]] 表示 block 的二维平面。该向量可能很长 (n > 10k)。

一个例子:

必须像这样投影:

然而问题是积木并不是整齐地堆放，而是可以是任何形状和位置

哪个 block 应该是项目的标准并不重要。在示例中，我取了第一个(在 x 轴上)最大的；这似乎是合理的。

重要的是维护一个列表(向量)，其中其他 block 被投影 block 遮挡。这些 block 包含重要的元数据，所以我应该能够回答“这个 block 投影到哪条线段？”的问题。

那么具体来说，如何才能将 2D 平面有效地投影到一条直线上，在某种意义上“转换阴影”，从而保持一种查看哪些 block 参与线段(阴影)的方法？

编辑:虽然问题相当普遍，但具体问题是我有一个包含多列和 float 图像的文档，我想为其生成一个“迷你 map ”，指示去哪里找到某些注释(颜色)

Answer 1

假设矩形始终与轴对齐，如您的示例所示，我将使用 sweep line方法:

1. 根据 y 值对矩形顶部/底部进行排序。对于每个元素，保留对完整矩形数据的引用。

2. 按 y 递增顺序扫描列表，维护一组 S 个矩形，表示包含当前 y 值的矩形。对于矩形 r 的每个顶部，将 r 添加到 S。类似地，对于 r 的每个底部，从 S 中删除 r。每次执行此操作时，都会关闭一个段并开始一个新段。如果此时检查 S，您将拥有参与该段的所有矩形，因此这是应用选择段颜色的策略的地方。

如果你以后需要知道一个矩形属于哪些段，你可以在矩形和段列表之间建立一个映射，并在扫描过程中更新它。