2

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

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

现在我需要合并有共同顶点且斜率相同的边。合并边缘后，我需要制作边界多边形，从逆时针方向的顶点开始。

请帮助找到一种方法，使其成为可能。

4

2 回答 2

2

我认为这是一个简单的算法来实现这一点。

考虑我们有这个作为输入：

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

其中a、b、c、d和e是我们的输入图块，它们存储为成对向量（坐标）：

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

我们想要的是这样的：

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

该算法的工作原理如下：

  1. 构建一个包含整个图块集的布尔值数组。您必须遍历集合才能找到该矩形的边界。将表示集合中的一个拼贴的数组位置设置为 true，否则设置为 false。
    示例中的输出将是（T is trueand f is false）：

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

  2. 现在您必须遍历船体多边形的边界。从标记为标志数组中的第一个元素开始，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 ]  
+---+---+---+

    • 如果一个瓷砖是假的，一个是真的，朝同一个方向走（注意真假或假真意味着你在一个边界）：

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

goes to

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

    • 如果两个图块都为真，逆时针旋转并将顶点添加到输出列表（请注意，真-真表示您已到达图块集的一部分，即“墙”）：

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

goes to

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

注意事项：

瓷砖地图坐标与标志数组坐标

flag-array 表示放置瓷砖的瓷砖地图的矩形区域。所以它的第一个元素（瓦片）的瓦片地图坐标是(left,top)其中left是所选瓦片集的最小 x 坐标，并且top是所选瓦片集的最小 y 坐标。

在算法的第二步中，您使用数组作为向导，遍历图块集的边界（边界）。请注意，您真正遍历的是该数组，因此您必须将坐标从标志坐标（逻辑坐标）转换为 tilemap 坐标（物理坐标）以存储多边形的顶点。当然这很容易。

另请注意，算法抽象步骤遍历边的顶点（物理平铺坐标），而不是逻辑坐标。您必须确定“我在那个顶点”的含义以及“前进”和“转弯”在标志数组坐标方面的含义。

边界条件和正面瓷砖检查

我们已经定义了三个规则来沿着这组图块的边界前进。我们使用标志数组作为指导来决定做什么（前进、顺时针转动或逆时针转动）。请注意，当当前顶点位于数组的边界时，您可以（您应该）认为它具有 false 值的相邻图块。

例如：

+---+---+---+  
| 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 |  
*---*---*---+

可能的优化

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

例子

给定这个标志数组：

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

执行工作如下（注意，图纸是执行步骤后的状态）：

  1. 找到第true一块瓷砖。在这种情况下(0,0)。所以我们从它的一个顶点开始（例如，左下顶点，向上看。请注意，因为它是第一个真正的图块，您可以使用该顶点以确保它属于多边形。所以将第一个顶点添加到多边形）：

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

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

  2. 开始横穿。在这种情况下，前面的瓷砖是false-true，所以提前：

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

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

  3. 前面的瓷砖是false-false（我们在一个边界），所以顺时针转动并添加顶点：

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

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

  4. 现在前面板是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 |  
+---+---+---+

  5. 两个前面的瓷砖是true：逆时针转动并添加顶点：

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

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

  6. 一张是false，另一张是true：Advance：

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

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

  7. 两个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 |  
+---+---+---+

  8. 一true加一false（数组外）：Advance：

    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

  9. 两个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---*

  10. 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---+---*

  11. 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 |  
+---*---+---*

  12. true-truefront-tiles：逆时针旋转并添加顶点：

    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 |  
+---*---+---*

  13. false-falsefront-tiles：顺时针旋转并添加顶点：

    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 |  
+---*---+---*

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

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

*---* 
|   |  
*   *-------*    
|           | 
*---*       |  
    |       |  
    *-------*
于 2013-10-04T12:27:27.550 回答
0

由于瓷砖，这是寻找边界多边形的“特殊情况”。我会采用一些简单的方法。

平铺 (x,y) 由顶点 [(x,y), (x+1,y), (x+1,y+1), (x,y+1)] 组成。如果顶点位于 1、2 或 3 个瓦片中，则它是边界多边形的一部分。要找到边界上的顶点，计算它所在的图块数量就足够了。为此，通过图块并增加图块 4 顶点的顶点外观计数就足够了。切片数为 1、2 或 3 的顶点位于边界多边形上。

要对顶点进行排序，从边界上的某个顶点开始并寻找也在边界上的相邻顶点就足够了。要沿相同方向遍历顶点，重要的是要注意要检查的相邻顶点的方向顺序。例如，如果最后一个顶点在 -x 上，则检查方向的顺序是 +y、+x、-y。

由于最后一条边的方向是已知的，如果下一条边与该顶点的方向相同，则用于删除。如果区域是简单连接的，则也可以从图块计数中知道移除。如果顶点的平铺计数为 2，则顶点将被移除。

目前我们不能保证顺序是顺时针的。这可以通过检查（一些）最上面的边缘是否是顺时针方向来检查。如果不是，则反转多边形。

于 2013-10-07T18:09:10.190 回答