我正在做一个项目，我需要在一组矩形周围创建一个边界。
让我们以这张图片为例来说明我想要完成的事情。
编辑：无法使图像标签正常工作，所以这里是完整链接： http ://www.flickr.com/photos/21093416@N04/3029621742/
我们有矩形 A 和 C，它们通过特殊的链接矩形 B 链接。您可以将其视为图中的两个节点 (A,C) 和它们之间的边 (B)。这意味着矩形以下列方式具有彼此的指针：A->B、A<-B->C、C->B
每个矩形有四个顶点存储在一个数组中，其中索引 0 位于左下角，索引 3 位于右下角。
我想“遍历”这个链接结构并计算构成它周围边界（红线）的顶点。关于如何实现这一点，我已经有了一些小想法，但想知道你们中的一些更倾向于数学的人是否有一些巧妙的技巧。
我在这里发布这个的原因只是有人可能以前解决过类似的问题，并且有一些我可以使用的想法。我不希望任何人坐下来仔细思考这个问题。在等待答案的同时，我将并行研究解决方案。
非常感谢任何输入。
使用示例，其中矩形相互垂直，因此可以由四个值（两个 x 坐标和两个 y 坐标）表示：
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | 乙|
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
1）将所有x坐标（左右）收集到一个列表中，然后对其进行排序并删除重复项
1 3 4 5 6
2）将所有y坐标（顶部和底部）收集到一个列表中，然后对其进行排序并删除重复项
1 2 3 4 6
3) 通过唯一 x 坐标之间的间隙数 * 唯一 y 坐标之间的间隙数创建一个 2D 数组。每个单元只需要一位，因此在 c++ 中，vector<bool> 可能会为您提供一个非常节省内存的版本
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 这样的库来为您完成这项工作！
这个问题的通用解决方案是根据扫描线实现布尔运算。你可以在这里找到一个简短的讨论来帮助你开始。从文中：
“布尔算法的基础是扫描线。对于基本原理，Franco P. Preparata 和 Michael Ian Shamos 的Computational Geometry an Introduction这本书非常好。”
我拥有这本书，虽然它现在在办公室，所以我无法查找你应该阅读的页码，尽管第 8 章关于矩形的几何形状可能是最好的起点。
（要从 A 和 B 中获取重叠矩形，取中间 2 个 X 位置，以及中间 2 个 Y 位置）
示例 (x1,y1) - (x2,y2)：
计算：
这是我的可视化示例：
1 2 3 4 5 6
1 +---+---+
| |
2 + A +---+---+
| | B |
3 + + +---+---+
| | | | |
4 +---+---+---+---+ +
| |
5 + C +
| |
6 +---+---+
一个简单的技巧应该是：
经过一番思考，我最终可能会做这样的事情：
伪代码：
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)
Obvisouly 这个伪代码必须稍微改进一下，可能无法涵盖所有情况，但我想我可能已经解决了我自己的问题。
我还没有完全想到这一点，但我想知道你是否不能这样做：
你的矩形是否总是水平对齐的，如果不是，你也需要做同样的事情，但对于 Y 呢？并且他们总是保证是感动的吗？如果不是，算法不会被破坏，但“正确的顺序”将无法定义。