c++ - 二维平铺世界中矩形的并集

Question

我试图在二维平铺世界中找到一组相邻单元格(行，列)(可转换为矩形)的边界多边形。

在for循环中处理单元格并使用相邻单元格的邻域属性，可以消除所有内部边缘并存储其余边缘。
边存储在std::vector;中。

现在，我需要合并存在相同顶点和斜率相同的边。
合并边缘后，我需要制作一个边界多边形，从一个逆时针的顶点开始。

请帮助找到使之成为可能的方法。

Answer 1

我认为这是实现该目标的简单算法。

考虑我们将其作为输入:

 |   |   |   |   |   |
-+---+---+---+---+---+-
 |   |   |   |   |   |
-+---+---+---+---+---+-
 |   |   | a |   |   |
-+---+---+---+---+---+-
 |   | b | c | d |   |
-+---+---+---+---+---+-
 |   |   | e |   |   |
-+---+---+---+---+---+-
 |   |   |   |   |   |

其中 a， b， c， d和 e是我们存储为成对 vector (坐标)的输入图块:

std::vector<std::pair<unsigned,unsigned>> tiles;

我们想要的是:

 |   |   |   |   |   |
-+---+---+---+---+---+-
 |   |   |   |   |   |
-+---+---*---*---+---+-
 |   |   |   |   |   |
-+---*---*   *---*---+-
 |   |           |   |
-+---*---*   *---*---+-
 |   |   |   |   |   |
-+---+---*---*---+---+-
 |   |   |   |   |   |

该算法的工作原理如下:

构建一个 bool(boolean) 数组，将整个图块封装起来。您必须遍历集合以找到该矩形的边界。将表示集合图块的数组位置设置为true，否则设置为false。
该示例中的输出将是(T为true，f为false):

+---+---+---+  
| f | T | f |  
+---+---+---+  
| T | T | T |  
+---+---+---+  
| f | T | f ]  
+---+---+---+  

现在，您必须遍历船体多边形的边界。从标志数组中标记为true的第一个元素开始，并沿相同方向遍历顶点，直到使用以下规则再次到达第一个顶点:

如果当前方向/位置前面的两个图块为假，请顺时针旋转，然后将顶点添加到输出列表(多边形)中:
(*是添加到多边形的顶点，X是当前顶点，箭头是当前方向)

+---+---+---+  
| f | f | f |  
*---+---X---+ --->   
| T | T | f |  
*---+---+---+  
| f | T | f ]  
+---+---+---+  

goes to

+---+---+---+  
| f | f | f |  |
*---+---*---+  |
| T | T | f |  v
*---+---X---+  
| f | T | f ]  
+---+---+---+  

如果一个图块为假，一个为真，则朝同一方向前进(请注意，true-false或false-true表示您处于边界):

+---+---+---+  
| f | f | f | |   
*---+---*---+ |  
| T | T | f | v  
*---+---X---+  
| f | T | f ]  
+---+---+---+  

goes to

+---+---+---+  
| f | f | f |  |
*---+---*---+  |
| T | T | f |  v
*---+---+---+  
| f | T | f ]  
+---+---X---+  

如果两个图块都为true，则逆时针旋转，然后将顶点添加到输出列表中(请注意，true-true表示您已到达图块集合的一部分，即“墙”):

+---+---+---+  
| f | f | f | |   
*---+---*---+ |  
| T | T | f | v  
*---+---X---+  
| f | T | T ]  
+---+---+---+  

goes to

+---+---+---+  
| f | f | f |  
+---+---*---+  
| T | T | f |  --->
+---+---*---X  
| f | T | T ]  
+---+---+---+  

注意事项:

tilemap坐标vs标志数组坐标

标记数组表示放置图块的图块 map 的矩形区域。因此，其第一个元素(tile)的tilemap坐标为 (left,top)，其中 left是所选图块集合的最小x坐标，而 top是所选图块集合的最小y坐标。

在方法的第二步中，使用数组作为指导遍历图块集的边界(边界)。请注意，您真正遍历的是该数组，因此 必须将坐标从标志坐标(逻辑坐标)转换为tilemap坐标(物理坐标)才能存储多边形的顶点。当然很简单。

还要注意，该算法抽象步骤遍历边缘的 顶点(物理 slice 坐标)，而不是遍历逻辑坐标。您必须确定“我在那个顶点”是什么意思，以及“前进”和“转弯”在标志数组坐标方面是什么意思。

边境条件和前平铺检查

我们定义了三个规则以沿着图块集的边界前进。我们已经使用标志数组作为指导来决定要做什么(前进，顺时针旋转或逆时针旋转)。请注意，当当前顶点在数组的边界中时， 可以(应该)认为它具有带有错误值的邻居 slice 。

例如:

+---+---+---+  
| f | f | f |  |  
*---+---*---+  |  
| T | T | f |  v
*---+---+---+  
| f | T | f ]  
+---+---X---+  

去

+---+---+---+  
| f | f | f |  
*---+---*---+  <--
| T | T | f |  
*---+---+---+  
| f | T | f ]  
+---X---*---+  

就像是这样:

+---+---+---+  
| f | f | f |  |  
*---+---*---+  |  
| T | T | f |  v
*---+---+---+  
| f | T | f ]  
+---+---X---+
| f | f | f |  
*---*---*---+ 

可能的优化

第一步计算标志数组，因为该算法将选择的一组图块作为 vector 。如果您的图块引擎支持它，则可以向图块添加一个属性( bool selected)并直接传递tilemap， 避免计算和顶点坐标转换。

例

给定这个标志数组:

+---+---+---+  
| T | f | f |    
+---+---+---+    
| T | T | T |
+---+---+---+  
| f | T | T |  
+---+---+---+  

执行工作如下 (注意，图形是执行步骤后的状态):

查找第一个true磁贴。在这种情况下为(0,0)。因此，我们从其一个顶点开始(例如，左下顶点，向上看。请注意，因为它是第一个真图块，所以可以使用该顶点来确保它属于多边形。因此将该第一个顶点添加到多边形):

Current position: (0,1)
Polygon: {(0,1)} 

+---+---+---+ ^ 
| T | f | f | |  
X---+---+---+ |    
| T | T | T |
+---+---+---+  
| f | T | T |  
+---+---+---+  

开始遍历。在这种情况下，前面的图块是false-true，因此会优先:

Current position: (0,0)
Polygon: {(0,1)} 

X---+---+---+ ^ 
| T | f | f | |  
*---+---+---+ |    
| T | T | T |
+---+---+---+  
| f | T | T |  
+---+---+---+  

前面的图块是false-false(我们处于边界中)，因此顺时针旋转并添加顶点:

Current position: (1,0)
Polygon: {(0,1),(0,0)} 

*---X---+---+ 
| T | f | f |   
*---+---+---+     
| T | T | T | --->
+---+---+---+  
| f | T | T |  
+---+---+---+ 

现在，fron-tiles为false-false(一个不在数组中，另一个为false)。 顺时针旋转并添加顶点:

Current position: (1,1)
Polygon: {(0,1),(0,0),(1,0)} 

*---*---+---+ 
| T | f | f | | 
*---X---+---+ |   
| T | T | T | v
+---+---+---+  
| f | T | T |  
+---+---+---+ 

这两个前瓷砖是true:逆时针旋转并添加顶点:

Current position: (1,2)
Polygon: {(0,1),(0,0),(1,0),(1,1)} 

*---*---+---+ 
| T | f | f |   
*---*---X---+     
| T | T | T | --->
+---+---+---+  
| f | T | T |  
+---+---+---+ 

一个图块是false，另一个是true:高级:

Current position: (1,3)
Polygon: {(0,1),(0,0),(1,0),(1,1)} 

*---*---+---+ 
| T | f | f |   
*---*---+---X     
| T | T | T | --->
+---+---+---+  
| f | T | T |  
+---+---+---+ 

两个false磁贴(均不在阵列中):顺时针旋转并添加顶点:

Current position: (2,3)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1)} 

*---*---+---+ 
| T | f | f | | 
*---*---+---* |   
| T | T | T | v
+---+---+---X  
| f | T | T |  
+---+---+---+ 

一个true和一个false(数组外):高级:

Current position: (3,3)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1)} 

*---*---+---+ 
| T | f | f | | 
*---*---+---* |   
| T | T | T | v
+---+---+---+  
| f | T | T |  
+---+---+---X 

两个false(数组外)前瓷砖:顺时针旋转并添加顶点:

Current position: (2,3)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3)} 

*---*---+---+ 
| T | f | f |  
*---*---+---*    
| T | T | T | <---
+---+---+---+  
| f | T | T |  
+---+---X---* 

true-false(一个true和一个越界):高级:

Current position: (1,3)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3)} 

*---*---+---+ 
| T | f | f |  
*---*---+---*    
| T | T | T | <---
+---+---+---+  
| f | T | T |  
+---X---+---* 

false-false(一个false和一个越界):顺时针旋转并添加顶点:

Current position: (1,2)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3),(1,3)} 

*---*---+---+ 
| T | f | f | ^ 
*---*---+---* |   
| T | T | T | |
+---X---+---+  
| f | T | T |  
+---*---+---* 

true-true前置图块:逆时针旋转并添加顶点:

Current position: (0,2)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3),(1,3),(1,2)} 

*---*---+---+ 
| T | f | f | 
*---*---+---*    
| T | T | T | <---
X---*---+---+  
| f | T | T |  
+---*---+---* 

false-false前置图块:顺时针旋转并添加顶点:

Current position: (0,1)
Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3),(1,3),(1,2),(0,2)} 

*---*---+---+ 
| T | f | f | ^ 
X---*---+---* |   
| T | T | T | |
*---*---+---+  
| f | T | T |  
+---*---+---* 

当前顶点是多边形的第一个顶点:执行已完成。结果如下:

Polygon: {(0,1),(0,0),(1,0),(1,1),(3,1),(3,3),(1,3),(1,2),(0,2)} 

*---* 
|   |  
*   *-------*    
|           | 
*---*       |  
    |       |  
    *-------*