c# - 以整数精度合并（布尔联合）矩形区域

Question

给定任意数量的相交、不相交和接触的矩形，如何找到（多条）轮廓折线？矩形在像素坐标中定义，因此它们具有整数精度，但它们可能有数千个单位大。

我真的需要轮廓的数字坐标，合并 GDI 区域是行不通的。我知道我可以通过创建 GDI 区域并调用 GetRegionScans 来简化问题，但它仍然不能解决问题。

这是实时 UI 的一部分，所以算法需要相当快（我猜永远不会超过十几个盒子，也许一百个）。

我在 C# 中这样做，但由于这是一个算法问题，我并不真正关心语言。欢迎任何想法。

Answer 1

我不知道这是否满足您的性能要求，但它应该可以工作：

1. 从一组空的矩形开始。
2. 将每个矩形添加到集合中。如果一个矩形与现有的矩形重叠，则根据需要将矩形分割成多个矩形，这样就没有一个矩形与另一个矩形重叠。
3. 将每个非重叠矩形的四个边添加到一组线中。
4. 删除所有不唯一的行。

结果集包含构成轮廓的所有线条。

---