计算多个链接矩形周围的边界

使用该示例,其中矩形彼此垂直,因此可以用四个值(两个X坐标和两个Y坐标)表示:

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       |
5              +   C   +
               |       |
6              +---+---+

1)将所有X坐标(左、右)收集到一个列表中,然后对其进行排序并删除重复项

1 3 4 5 6

2)将所有Y坐标(顶部和底部)收集到一个列表中,然后对其进行排序并删除重复项

1 2 3 4 6

3)通过唯一X坐标之间的间隙数*唯一Y坐标之间的间隙数创建二维阵列。它只需要每个单元一个比特,所以在C++中,vector & lt;BOOL & GT;很可能会给你一个非常有效的内存版本。

4 * 4

4)在网格中绘制所有矩形

   1   3   4   5   6

1  +---+
   | 1 | 0   0   0
2  +---+---+---+
   | 1 | 1 | 1 | 0
3  +---+---+---+---+
   | 1 | 1 | 1 | 1 |
4  +---+---+---+---+
     0   0 | 1 | 1 |
6          +---+---+

5)对于网格中的每个单元,对于每个边,如果其旁边的单元在该基本方向上没有绘制,则为该边绘制边界线。

在这个问题中,矩形被描述为四个向量,每个向量代表一个角。如果每个矩形都可以任意旋转,并且与其他矩形的旋转方式不同,那么我上面概述的方法将不起作用。找到复杂多边形周围路径的问题通常由矢量图形光栅器解决,解决该问题的好方法是使用cairo之类的库来为您完成工作!

这个问题的一般解决方案是用扫描线实现布尔运算。你可以找到一个简短的讨论 here 开始吧。从文本中:

布尔算法的基础是扫描线。关于基本原则,本书: Computational Geometry an Introduction 弗朗哥P.普雷帕塔和迈克尔·伊恩·萨莫斯的作品非常出色。”

我拥有这本书,虽然它现在在办公室里,所以我找不到你应该读的页码,尽管第8章,关于矩形的几何可能是最好的起点。

1. 分别计算三个矩形的边界之和
2. 计算A和B的重叠矩形,并从和中减去它
3. 对b和c的重叠矩形执行相同的操作

(从A和B得到重叠的矩形,取中间的2个x位置,以及中间的2个y位置)

示例(x1,y1)-(x2,y2):

• 矩形A:(1,1)-(3,4)
• 矩形B:(3,2)-(5,4)
• 矩形C:(4,3)-(6,6)

计算:

1. 10+8+10=28
2. x坐标顺序=1,3,3,5中间两个是3和3
   Y坐标顺序=1,2,4,4中间两个是2和4
   所以:(3,2)-(3,4):边界=4
3. X坐标顺序=3,4,5,6中间两个是4和5
   Y坐标顺序=2,3,4,6中间两个是3和4
   所以:(4,3)-(5,4):边界=4
4. 28 - 4 - 4=20

这是我的可视化示例:

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       | 
5              +   C   +
               |       |
6              +---+---+

一个简单的技巧应该是:

1. 从第一个矩形创建区域
2. 将其他矩形添加到区域
3. 得到该区域的边界(不知何故?P)

经过一番思考,我可能最终会这样做:

伪代码:

 LinkRectsConnectedTo(Rectangle rectangle,Edge startEdge) // Edge can be West,North,East,South 
    for each edge in rectangle starting with the edge facing last rectangle
       add vertices in the edge to the final boundary polygon
       if edge is connected to another rectangle
          if edge not equals startEdge
             recursively call LinkRectsConnectedTo(rectangle,startEdge)

很明显,这个伪代码需要改进一点,可能不能覆盖所有的情况,但我想我可能已经解决了我自己的问题。

我还没有完全想清楚,但我想知道你是否不能做如下的事情:

• 列出所有边。
• 得到所有边,其中p1.x=p2.x
• 在这个列表中,得到x相等的对。
• 对于每对零件,对于不重叠的零件,用一个或两个边缘替换。
• 做些聪明的事使边缘整齐

你的矩形会一直水平对齐吗,如果不是的话,你需要做同样的事情,但对Y也一样? 他们是不是总是保证会触摸?如果不是这样,算法就不会被破坏,但是“正确的顺序”是不可定义的。