从一组矩形创建连续的矩形矩阵
Create continuous matrix of rectangles from set of rectangles
我有一组对象（每个对象包含一个矩形和一个分配给它的值）保存在一个向量容器中。
见下图：
我需要通过在每个 y/x 左下 (LL) / 右上 (UR) 坐标绘制水平线和垂直线来创建一个矩阵，如下所示：
我需要为每个新的空矩形分配 value = 0，对于初始矩形内的其他矩形，我需要分配它们的旧值。
我已经用一些天真的算法实现了这个但是当我有大量的矩形时它工作得太慢了。我的算法基本上执行以下操作：
- 将所有矩形存储在地图容器中。地图的每个元素都包含一组具有相同 LL Y 坐标的矩形，它们按 LL X 坐标排序，即键是 LL Y 坐标。
- 将所有 X/Y 坐标存储在集合容器中。
- 迭代 Y/X 个坐标容器，并为每个新矩形找出它是否存在于地图中，如果存在 - 为其分配现有值，否则 - 分配 0 值。即，对于每个新矩形，它在地图中查找其 LL Y 坐标，如果存在这样的 Y，则搜索相应的值（矩形集），否则 - 它在整个地图中搜索。
是否有有效的算法来获得所需的结果？
我怀疑查找和迭代不够快。 'otherwise it searches the whole map' 之类的东西指出您进行了非常繁重的计算。
我认为你需要的是使用二维数据结构。 k-d 树或 BSP 都可以，但最容易理解和实现的是四叉树。
在四叉树中，每个节点代表 space 中的一个矩形。通过选择沿 2 个维度的中点并让 children 代表 4 个结果矩形，可以将每个节点拆分为 4 children。每个节点还包含您要分配给该区域的值和一个额外的标志（如果该值是统一的）。
要用某个值标记一个矩形，您从根开始并递归：
- 如果输入矩形覆盖了您将值设置为该节点的节点矩形，则将其标记为统一并且return。
- 如果输入矩形和节点矩形不接触 return。
- 如果节点被标记为统一，将值复制到它的 children 并将节点标记为不统一。
- 递归调用 4 children（您可能必须创建它们）。
- 在返回的路上，检查 4 个 children 是否具有相同的值并且都标记为统一，如果是，则将节点标记为统一并设置与 children 相同的值。
这种方法的主要优点是您可以快速标记地图的大面积区域。您还可以证明标记一个区域是 O(logN)，其中 N 是您的地图的大小（具有比通常的树更大的常数）。
您可以在 wikipedia 上找到更详细的解释和一些有用的图片。
对于 n 个矩形，这可以在 O(n^3) 时间 内轻松解决（如果最多有有限数量的矩形相交，则只需 O(n^2) 时间) 以不同的方式看待问题。这应该足以在几秒钟内处理多达数千个矩形。
此外，除非向问题添加一些其他约束，否则后一个时间界限是最优的：即存在由 n 个不相交矩形组成的输入，需要 O(n^2) 个较小的网格矩形输出（这当然需要 O(n^2) 时间）。此类输入的一个示例是 n 个 width-1 矩形，它们都具有相等的最底部 y 坐标和高度 1, 2, ..., n.
网格大小范围
首先，注意最多可以有2n条垂直线，最多2n条水平线，因为每个输入矩形最多引入2条（如果一条或两条垂直线是还有一些已经考虑过的矩形的边缘，水平线也是如此）。因此，由这些线定义的网格中最多可以有 (2*n - 1)^2 = O(n^2) 个单元格。
网格单元坐标系
我们可以为网格单元发明一个坐标系，其中每个单元格由其左下角标识，两条网格线的交点坐标仅由水平网格的数量给出它下面的线和它左边的垂直网格线的数量（所以最底部，最左边的网格单元格有坐标（0, 0），它右边的单元格有坐标（1, 0），单元格二上面的单元格单元格有坐标（1、2）等）
算法
对于每个具有 LL 坐标 (x1, y1) 和 UR 坐标 (x2, y2) 的输入矩形，我们确定它在新网格坐标系中占据的水平和垂直间隔，以及然后简单地遍历属于该矩形区域的每个单元格 (i, j)（即每个网格单元格 (i, j) 使得 toGridX(x1) <= i < toGridX(x2) 和 toGridY(y1) <= j < toGridY(y2)) 嵌套 for 循环，在散列 table 中记录 (i, j) 处单元格的 ID（颜色？）应该是当前输入矩形的颜色。输入矩形应该以递减的 z 顺序处理（隐含地至少似乎有这样的顺序，从你的例子来看）这样对于被多个输入矩形覆盖的任何单元格，散列 table 将结束记录无论 "nearest" 矩形的颜色是什么。最后，遍历哈希 table，将每个网格坐标对 (i, j) 转换回对应于该网格单元的输入-space 矩形的 LL 和 UR 坐标，并使用此哈希键的值给出的 ID 输出此矩形。
预处理
为了完成上述任务，我们需要两件事：一种将输入-space坐标映射到网格坐标的方法（以确定给定输入矩形的水平和垂直网格间隔)，以及一种将网格坐标映射回输入-space 坐标的方法（以在最后一步生成输出矩形）。这两个操作都很容易通过那个老主力来完成，排序。
给定某个输入矩形的任意角 (x, y)，对应于 x 的网格 x 坐标，toGridX(x)，就是等级位置 of x 在所有 distinct x 个垂直边缘位置的排序列表中，这些位置存在于输入矩形中。 同样，toGridY(y) 只是排名在输入矩形中存在的水平边缘的所有不同 y 位置的排序列表中 y 的位置。在另一个方向上，对于任何网格坐标 (i, j)，相应的输入-space x 坐标，fromGridX(i)，只是第 i 个最小的 x 坐标（忽略重复项） ) 输入矩形之间的任何垂直边缘，对于 fromGridY(j) 也是如此。这些都可以按如下方式计算（所有数组索引都从 0 开始，我只展示如何对 x 坐标进行计算；y 坐标类似）：
- 对于输入中具有 LL 坐标 (x1, y1) 和 (x2, y2) 的每个矩形 i：
- 将二元素数组 [x1, i] 附加到数组列表 VERT。
- 将二元素数组 [x2, i] 附加到数组列表 VERT。
- 按第一项升序对列表 VERT 进行排序。
- 合并 VERT 中具有相同 x 坐标的元素。具体来说：
- 设置 j = 0。
- 对于 i 从 1 到 n-1:
- 如果 VERT[i][0] == VERT[j][0] 然后将 VERT[i][1] 附加到 VERT[j] （从而在位置 j 形成一个长度为 3 或更多的数组） , 否则设置 j = j + 1 并用二元素数组 VERT[i].
覆盖 VERT[j]
- 从 VERT 中删除 VERT[j+1] 和所有后续元素。
此时，对于任何 i，VERT[i] 是一个数组，其中包含（在其第二个和后续位置）使用的每个输入矩形的 ID，作为其左侧或右侧edge，任何输入矩形使用的第 i 个最左边的不同垂直线——或者换句话说，第 i 个垂直线。我们现在 "invert" 这个：
- 对于 i 从 0 到 n-1:
- 对于从 1 到长度 (VERT[i])-1 的 j：
- 设置为GridX[VERT[i][j]] = i.
- 对于从 0 到长度 (VERT)-1 的 i：
- 设置 fromGridX[i] = VERT[i][0].
运行 时间
如前所述，最多有 O(n^2) 个网格单元。 n 个输入矩形中的每一个最多可以占据所有这些单元，每个输入矩形访问一次，时间范围为 O(n^3)。请注意，这是一个非常悲观的时间限制，例如，如果 none（或 none 但有界数）的矩形重叠，则它会下降到 O(n^2)，因为没有网格单元将永远被访问不止一次。
假设您知道最顶部和最底部 y 以及最左侧和最右侧 x，将属于每个矩形的四个向量扩展到相应的最大值和最小值 x 和 y 点。保留一组扩展的垂直向量和一组扩展的水平向量。每当添加扩展向量时，它必然会与垂直列表中的每个向量相交 - 交点是矩阵的单元格坐标。
生成单元格坐标列表后，遍历它们并适当地分配值，查找它们是否在原始矩形之内或之外。我不太精通矩形的数据结构，但在我看来，两棵间隔树，一棵用于水平，另一棵用于垂直，可以在每个查询的 O(log n) 时间内找到答案，其中 n是树中的区间数。
总的来说，这个方法似乎是O(n * log m)次，其中n是结果矩阵中单元格坐标的数量，m是原始矩形的数量。
我有一组对象（每个对象包含一个矩形和一个分配给它的值）保存在一个向量容器中。
见下图：
我需要通过在每个 y/x 左下 (LL) / 右上 (UR) 坐标绘制水平线和垂直线来创建一个矩阵，如下所示：
我需要为每个新的空矩形分配 value = 0，对于初始矩形内的其他矩形，我需要分配它们的旧值。
我已经用一些天真的算法实现了这个但是当我有大量的矩形时它工作得太慢了。我的算法基本上执行以下操作：
- 将所有矩形存储在地图容器中。地图的每个元素都包含一组具有相同 LL Y 坐标的矩形，它们按 LL X 坐标排序，即键是 LL Y 坐标。
- 将所有 X/Y 坐标存储在集合容器中。
- 迭代 Y/X 个坐标容器，并为每个新矩形找出它是否存在于地图中，如果存在 - 为其分配现有值，否则 - 分配 0 值。即，对于每个新矩形，它在地图中查找其 LL Y 坐标，如果存在这样的 Y，则搜索相应的值（矩形集），否则 - 它在整个地图中搜索。
是否有有效的算法来获得所需的结果？
我怀疑查找和迭代不够快。 'otherwise it searches the whole map' 之类的东西指出您进行了非常繁重的计算。
我认为你需要的是使用二维数据结构。 k-d 树或 BSP 都可以，但最容易理解和实现的是四叉树。
在四叉树中，每个节点代表 space 中的一个矩形。通过选择沿 2 个维度的中点并让 children 代表 4 个结果矩形，可以将每个节点拆分为 4 children。每个节点还包含您要分配给该区域的值和一个额外的标志（如果该值是统一的）。
要用某个值标记一个矩形，您从根开始并递归：
- 如果输入矩形覆盖了您将值设置为该节点的节点矩形，则将其标记为统一并且return。
- 如果输入矩形和节点矩形不接触 return。
- 如果节点被标记为统一，将值复制到它的 children 并将节点标记为不统一。
- 递归调用 4 children（您可能必须创建它们）。
- 在返回的路上，检查 4 个 children 是否具有相同的值并且都标记为统一，如果是，则将节点标记为统一并设置与 children 相同的值。
这种方法的主要优点是您可以快速标记地图的大面积区域。您还可以证明标记一个区域是 O(logN)，其中 N 是您的地图的大小（具有比通常的树更大的常数）。
您可以在 wikipedia 上找到更详细的解释和一些有用的图片。
对于 n 个矩形，这可以在 O(n^3) 时间 内轻松解决（如果最多有有限数量的矩形相交，则只需 O(n^2) 时间) 以不同的方式看待问题。这应该足以在几秒钟内处理多达数千个矩形。
此外，除非向问题添加一些其他约束，否则后一个时间界限是最优的：即存在由 n 个不相交矩形组成的输入，需要 O(n^2) 个较小的网格矩形输出（这当然需要 O(n^2) 时间）。此类输入的一个示例是 n 个 width-1 矩形，它们都具有相等的最底部 y 坐标和高度 1, 2, ..., n.
网格大小范围
首先，注意最多可以有2n条垂直线，最多2n条水平线，因为每个输入矩形最多引入2条（如果一条或两条垂直线是还有一些已经考虑过的矩形的边缘，水平线也是如此）。因此，由这些线定义的网格中最多可以有 (2*n - 1)^2 = O(n^2) 个单元格。
网格单元坐标系
我们可以为网格单元发明一个坐标系，其中每个单元格由其左下角标识，两条网格线的交点坐标仅由水平网格的数量给出它下面的线和它左边的垂直网格线的数量（所以最底部，最左边的网格单元格有坐标（0, 0），它右边的单元格有坐标（1, 0），单元格二上面的单元格单元格有坐标（1、2）等）
算法
对于每个具有 LL 坐标 (x1, y1) 和 UR 坐标 (x2, y2) 的输入矩形，我们确定它在新网格坐标系中占据的水平和垂直间隔，以及然后简单地遍历属于该矩形区域的每个单元格 (i, j)（即每个网格单元格 (i, j) 使得 toGridX(x1) <= i < toGridX(x2) 和 toGridY(y1) <= j < toGridY(y2)) 嵌套 for 循环，在散列 table 中记录 (i, j) 处单元格的 ID（颜色？）应该是当前输入矩形的颜色。输入矩形应该以递减的 z 顺序处理（隐含地至少似乎有这样的顺序，从你的例子来看）这样对于被多个输入矩形覆盖的任何单元格，散列 table 将结束记录无论 "nearest" 矩形的颜色是什么。最后，遍历哈希 table，将每个网格坐标对 (i, j) 转换回对应于该网格单元的输入-space 矩形的 LL 和 UR 坐标，并使用此哈希键的值给出的 ID 输出此矩形。
预处理
为了完成上述任务，我们需要两件事：一种将输入-space坐标映射到网格坐标的方法（以确定给定输入矩形的水平和垂直网格间隔)，以及一种将网格坐标映射回输入-space 坐标的方法（以在最后一步生成输出矩形）。这两个操作都很容易通过那个老主力来完成，排序。
给定某个输入矩形的任意角 (x, y)，对应于 x 的网格 x 坐标，toGridX(x)，就是等级位置 of x 在所有 distinct x 个垂直边缘位置的排序列表中，这些位置存在于输入矩形中。 同样，toGridY(y) 只是排名在输入矩形中存在的水平边缘的所有不同 y 位置的排序列表中 y 的位置。在另一个方向上，对于任何网格坐标 (i, j)，相应的输入-space x 坐标，fromGridX(i)，只是第 i 个最小的 x 坐标（忽略重复项） ) 输入矩形之间的任何垂直边缘，对于 fromGridY(j) 也是如此。这些都可以按如下方式计算（所有数组索引都从 0 开始，我只展示如何对 x 坐标进行计算；y 坐标类似）：
- 对于输入中具有 LL 坐标 (x1, y1) 和 (x2, y2) 的每个矩形 i：
- 将二元素数组 [x1, i] 附加到数组列表 VERT。
- 将二元素数组 [x2, i] 附加到数组列表 VERT。
- 按第一项升序对列表 VERT 进行排序。
- 合并 VERT 中具有相同 x 坐标的元素。具体来说：
- 设置 j = 0。
- 对于 i 从 1 到 n-1:
- 如果 VERT[i][0] == VERT[j][0] 然后将 VERT[i][1] 附加到 VERT[j] （从而在位置 j 形成一个长度为 3 或更多的数组） , 否则设置 j = j + 1 并用二元素数组 VERT[i]. 覆盖 VERT[j]
- 从 VERT 中删除 VERT[j+1] 和所有后续元素。
此时，对于任何 i，VERT[i] 是一个数组，其中包含（在其第二个和后续位置）使用的每个输入矩形的 ID，作为其左侧或右侧edge，任何输入矩形使用的第 i 个最左边的不同垂直线——或者换句话说，第 i 个垂直线。我们现在 "invert" 这个：
- 对于 i 从 0 到 n-1:
- 对于从 1 到长度 (VERT[i])-1 的 j：
- 设置为GridX[VERT[i][j]] = i.
- 对于从 1 到长度 (VERT[i])-1 的 j：
- 对于 i 从 0 到 n-1:
- 对于从 0 到长度 (VERT)-1 的 i：
- 设置 fromGridX[i] = VERT[i][0].
运行 时间
如前所述，最多有 O(n^2) 个网格单元。 n 个输入矩形中的每一个最多可以占据所有这些单元，每个输入矩形访问一次，时间范围为 O(n^3)。请注意，这是一个非常悲观的时间限制，例如，如果 none（或 none 但有界数）的矩形重叠，则它会下降到 O(n^2)，因为没有网格单元将永远被访问不止一次。
假设您知道最顶部和最底部 y 以及最左侧和最右侧 x，将属于每个矩形的四个向量扩展到相应的最大值和最小值 x 和 y 点。保留一组扩展的垂直向量和一组扩展的水平向量。每当添加扩展向量时，它必然会与垂直列表中的每个向量相交 - 交点是矩阵的单元格坐标。
生成单元格坐标列表后，遍历它们并适当地分配值，查找它们是否在原始矩形之内或之外。我不太精通矩形的数据结构，但在我看来，两棵间隔树，一棵用于水平，另一棵用于垂直，可以在每个查询的 O(log n) 时间内找到答案，其中 n是树中的区间数。
总的来说，这个方法似乎是O(n * log m)次，其中n是结果矩阵中单元格坐标的数量，m是原始矩形的数量。