algorithm - 在更大的矩形中组合矩形

Question

我有一组矩形，通常彼此平行（但不能保证）。这些矩形通常不重叠。我在下面附上了一个例子。它实际上是 OCR 输出的副产品，其中检测到的文本已被边界框替换。

我想将这些矩形合并成更大的矩形。生成的矩形不能重叠。分组可能如下所示：

最好的方法是什么？我在 Stackoverflow 上找不到以前的答案：

• 网格中的组矩形不适用于此处
• 找到 k 个矩形，使它们覆盖最大数量的点。我不确定它是否适用于我的情况。
• N 个矩形的交集提到了 R-Trees。但不确定 R-Trees 能否解决问题。

标签： algorithmrectangles