合并(布尔联合)矩形区域,具有整数精度

Question

给定任意数量的交点,不相交和触摸矩形,如何找到(多个)轮廓折线？矩形在像素坐标中定义,因此它们具有整数精度,但它们可能是数千个单位大.

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

这是实时UI的一部分,因此算法需要相当快(我猜测从不超过十几个盒子,可能是一百个).

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

Answer 1

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

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

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