联合非重叠矩形列表的算法

Question

输入： 一组不重叠的矩形

输出： 勾画出所有矩形轮廓的点数组

矩形表示如下：{x1, y1, x2, y2}

我尝试过的

我尝试过使用凸包和凹包算法。

这些不形成纯水平和垂直线的轮廓。

（这些算法的输出甚至不适合简化）

Answer 1

很难定义任意情况的边界。但是，如果您正在寻找的内容已通过发布的图片进行说明，我们可以尝试通过定义内部点来定义边界。

观察图中红色边界线内外的点之间的差异，我们可以定义一个内部点为以下至少有两个距离小于给定阈值的点：

• +x 方向到矩形的最近距离
• -x 方向到矩形的最近距离
• +y 方向到矩形的最近距离
• -y 方向到矩形的最近距离

我认为那里一定有一个距离阈值，因为红线在第一行中向下和向上，其中两个矩形彼此相距很远，而红线在第二行中是笔直的，其中两个矩形彼此相距较远。矩形彼此靠近。

如果这个定义合理，我们可以使用以下算法供大家参考：

1. 找到包含所有矩形的最小矩形
2. 生成一个 m x n 网格并计算每个网格点在 4 个方向上到附近矩形的距离。
3. 根据定义将网格点分类为内点或非内点。
4. 找到边界点并追踪。

我知道这不是一个完美的解决方案。为简单起见，这里我们忽略潜在的漏洞和孤岛。由于网格离散化，边界也可能不在矩形的边缘。我希望该解决方案可以作为完美解决方案的起点。