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

我正在开发一个项目,我需要围绕一组矩形创建边界.

让我们用这张照片作为我想要完成的事情的一个例子.

编辑:无法使图像标记正常工作,所以这里是完整的链接:http: //www.flickr.com/photos/21093416@N04/3029621742/

我们有通过特殊链接矩形B链接的矩形A和C.您可以将其视为图形(A,C)中的两个节点以及它们之间的边缘(B).这意味着矩形按以下方式指向彼此:A-> B,A <-B-> C,C-> B

每个矩形有四个顶点存储在一个数组中,其中索引0在左下角,索引3在右下角.

我想"遍历"这个链接结构并计算构成它周围边界(红线)的顶点.我已经有一些关于如何实现这个目标的小想法,但是想知道你们中有些人在数学上倾向于有一些巧妙的技巧.

我在这里发布的原因只是有人可能以前解决了类似的问题,并且有一些我可以使用的想法.我不指望任何人坐下来思考这个漫长而艰难的过程.当我等待答案时,我将在并行解决方案.

任何输入都非常感谢.

使用这个例子,矩形彼此垂直,因此可以用四个值(两个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)通过唯一y坐标之间的间隙数*创建2D阵列*唯一y坐标之间的间隙数.每个单元只需要一位,所以在c ++中,vector 可能会给你一个非常节省内存的版本

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)对于网格中的每个单元格,对于每个边缘,如果在该基本方向上旁边的单元格未绘制,则绘制该边缘的边界线

在这个问题中,矩形被描述为四个向量,每个向量代表一个角.如果每个矩形可以与其他矩形处于任意和不同的旋转,那么我上面概述的方法将不起作用.寻找复杂多边形周围路径的问题通常由矢量图形光栅化器解决,解决问题的一个好方法是使用像开罗这样的库来为你工作!