找到最小数量的矩形来覆盖二维点数组
find minimal number of rectangles to cover 2D point array
我得到了一个二维点数组，任务是生成最小的矩形列表，其中所有矩形具有相同的大小和方向，覆盖所有二维点位置并且可以重叠。
到目前为止，我有一个不太令人满意的解决方案，其中数组中的第一个点被选为第一个矩形的中心，然后移动矩形以便最近的点适合。重复该过程直到如果要再次移动矩形，已经覆盖的点将丢失。之后，从下一个未覆盖的点开始重复该过程，直到没有留下任何点。不是很满意。
目标是找出一个最优算法。不必是绝对最少的矩形数量，而是尽可能少。
首先，坐标可以translated/projected，矩形大小为1x1，方向为0°（与X/Y轴对齐）。所以我会假设这种情况。
那么您可以进行如下操作：
- 按 x 坐标
对点进行排序
- 创建一个有向图如下：
- 对于每个点a，取x-区间[a中的点x,ax+1],不包括a本身
- 从列表中排除那些 y 坐标不在 [ay-1 范围内的点, ay+1]
- 按y-坐标
对这些点进行排序
- 将这些点放入点 a 的邻接列表中。
- 将所有点标记为未访问
- 如果没有未访问的点，return 0 表示不需要（更多）矩形。
- 从已排序的点列表中取出下一个未访问的点 a：将 a 标记为已访问。
- 如果a没有邻居，则增加矩形数并从第4步开始重复
- 在邻居上滑动一个矩形，其左 x 坐标始终等于 ax，这样：
- 第一个选择的矩形的低y坐标与第一个未访问的相邻点
相同
- 维护一个列表 L 被访问的邻居列表（仅当它们尚未被标记为已访问时）被此矩形覆盖
- 所有下一个矩形位置在其高 y 坐标端各获得一个未访问点。
- L 中在滑动矩形的低 y 侧未被覆盖的点已从 L 并再次标记为未访问
- 每次识别新的矩形位置时，都会进行从第 4 步开始的递归 (DFS) 调用。
- DFS 调用将 return 仍然需要覆盖所有剩余未访问点的矩形数
- 保留所有这些递归调用中的最小值 return，并加 1（对于当前矩形）
- 注意：可以通过将当前最小结果作为分界点来修剪递归树，以避免过多增加矩形数量的搜索。
- 处理完所有矩形位置后，将仍在 L 中的任何点标记为未访问。
- Return 找到的最小矩形数。
这仍然是一个非常昂贵的算法，因为搜索树很容易变得很宽。
一个潜在的改进可能是使用 BFS 而不是 DFS，使用优先级队列（例如最小堆）。要最小化的数字将是已使用的矩形数（即到目前为止的成本）加上最右边（未访问）点和最左边未访问点之间的 x 坐标差，向上舍入（即成本的下限）仍然领先）。这是一个A*算法，所以一旦出现所有点都被覆盖（访问）的情况，你就可以停止搜索。
这种 BFS 方法的缺点是内存使用和管理，因为每个状态（在优先级队列中）都包含一组访问点。
因为只有启发式解决方案可以做到，我会尝试如下：
找到点的全局边界框；
用规则的矩形网格覆盖边界框，没有重叠也没有间隙。
如果一个矩形恰好是空的，则丢弃它。
您可以添加一个post-处理步骤，试图改进：
- select对相邻的矩形，并找到它们覆盖的点的边界框；如果该框适合单个矩形，则合并两个矩形。
请注意，由于矩形具有相同的大小和方向，您可以重新缩放数据，使矩形成为单位正方形。 （trincot 也说过。）
我得到了一个二维点数组，任务是生成最小的矩形列表，其中所有矩形具有相同的大小和方向，覆盖所有二维点位置并且可以重叠。
到目前为止，我有一个不太令人满意的解决方案，其中数组中的第一个点被选为第一个矩形的中心，然后移动矩形以便最近的点适合。重复该过程直到如果要再次移动矩形，已经覆盖的点将丢失。之后，从下一个未覆盖的点开始重复该过程，直到没有留下任何点。不是很满意。
目标是找出一个最优算法。不必是绝对最少的矩形数量，而是尽可能少。
首先，坐标可以translated/projected，矩形大小为1x1，方向为0°（与X/Y轴对齐）。所以我会假设这种情况。
那么您可以进行如下操作：
- 按 x 坐标 对点进行排序
- 创建一个有向图如下：
- 对于每个点a，取x-区间[a中的点x,ax+1],不包括a本身
- 从列表中排除那些 y 坐标不在 [ay-1 范围内的点, ay+1]
- 按y-坐标 对这些点进行排序
- 将这些点放入点 a 的邻接列表中。
- 将所有点标记为未访问
- 如果没有未访问的点，return 0 表示不需要（更多）矩形。
- 从已排序的点列表中取出下一个未访问的点 a：将 a 标记为已访问。
- 如果a没有邻居，则增加矩形数并从第4步开始重复
- 在邻居上滑动一个矩形，其左 x 坐标始终等于 ax，这样：
- 第一个选择的矩形的低y坐标与第一个未访问的相邻点 相同
- 维护一个列表 L 被访问的邻居列表（仅当它们尚未被标记为已访问时）被此矩形覆盖
- 所有下一个矩形位置在其高 y 坐标端各获得一个未访问点。
- L 中在滑动矩形的低 y 侧未被覆盖的点已从 L 并再次标记为未访问
- 每次识别新的矩形位置时，都会进行从第 4 步开始的递归 (DFS) 调用。
- DFS 调用将 return 仍然需要覆盖所有剩余未访问点的矩形数
- 保留所有这些递归调用中的最小值 return，并加 1（对于当前矩形）
- 注意：可以通过将当前最小结果作为分界点来修剪递归树，以避免过多增加矩形数量的搜索。
- 处理完所有矩形位置后，将仍在 L 中的任何点标记为未访问。
- Return 找到的最小矩形数。
这仍然是一个非常昂贵的算法，因为搜索树很容易变得很宽。
一个潜在的改进可能是使用 BFS 而不是 DFS，使用优先级队列（例如最小堆）。要最小化的数字将是已使用的矩形数（即到目前为止的成本）加上最右边（未访问）点和最左边未访问点之间的 x 坐标差，向上舍入（即成本的下限）仍然领先）。这是一个A*算法，所以一旦出现所有点都被覆盖（访问）的情况，你就可以停止搜索。
这种 BFS 方法的缺点是内存使用和管理，因为每个状态（在优先级队列中）都包含一组访问点。
因为只有启发式解决方案可以做到，我会尝试如下：
找到点的全局边界框；
用规则的矩形网格覆盖边界框，没有重叠也没有间隙。
如果一个矩形恰好是空的，则丢弃它。
您可以添加一个post-处理步骤，试图改进：
- select对相邻的矩形，并找到它们覆盖的点的边界框；如果该框适合单个矩形，则合并两个矩形。
请注意，由于矩形具有相同的大小和方向，您可以重新缩放数据，使矩形成为单位正方形。 （trincot 也说过。）