对于绘制多边形，需要对其顶点进行排序。

Question

我有一个矩阵（0表示没有东西，1表示地形），它代表我的游戏中的一个关卡。该矩阵对应着我屏幕上被分割成的网格，并指示了我的地形的位置。

实际上，我的地形由网格内每个块的四个角落的点组成。当您有多个连接的块时，我使用合并单元算法来删除重复点和任何内部点。结果是，我最终得到一个表示多边形外边缘的点列表。

要绘制此多边形，我需要将点按某种顺序排列（顺时针或逆时针），以便每个点都跟随其相邻的点。显然，第一个和最后一个点需要是相邻的。由于这全部在网格中，我知道相邻点之间的确切距离。

问题在于，我正在努力想出一种算法，使我能够“沿着”多边形的边缘行走，同时按顺序放置点。我相信应该有一种方法可以利用表示几何图形的矩阵的事实，这意味着只有一种可能的绘制多边形的方式（即使它是凹的）。

我已经尝试了几种贪心类型的算法，但似乎找不到一种方法，在每种情况下都知道要移动的方向。鉴于任何特定点最多可以有3个相邻点（第四个未包含，因为它是“起始”点，这意味着我已经对其进行了排序），我需要一种方法来确定移动的方向。

另一种我一直在尝试的方法是按其X（Y作为平局破解者）对点进行排序，这给我了最上/最左边缘。它还保证我从外部开始。然而，我仍然在努力找到一种算法，确保我留在外面而不会穿过去。

这是一个示例矩阵: 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0

它对应着这个（黑点代表我的点）: https://istack.dev59.com/Q00Y0.webp

- Kinru

---

能否先创建所有的三角形以便有一个参考，然后再合并所有点呢？ActionScript/Flash期望点的顺序是什么？三角形带？ - Anthony Raimondo

据我所知，这似乎是不可能的，因为这是一个关卡编辑器，方块可以以任何顺序创建/销毁。这意味着你可以从屏幕的一侧开始，然后随机连接方块，直到形成一些奇怪的凹形。由于方块共享点，无法知道它们被创建的顺序。不过，我认为必须有一种简单的方法来利用我的矩阵来获得顺序。对于Flash，我不知道底层绘图代码是什么（他们没有提供访问或文档）。你只需开始填充，然后按顺序连接点即可。 - Kinru

@Obicere 我实际上使用泛洪填充来合并单元格，但我不太明白如何用它来对点进行排序？不确定我是否理解你的图表。 - Kinru

@Obicere 我理解你的意思，但我不太明白这如何让你知道你正在前往哪个方向。是什么阻止你向下而不是向右移动？如果你有一个5x5的地形块，洪水填充可能会通过中间走一些随机路线，从而破坏顺序。 - Kinru

@Obicere，你能否用一个完整的例子/伪代码来写出你的想法并将其作为答案呈现？ - Kinru

Answer 1

首先请注意，对于一般矩阵，输出可能由多个封闭回路组成；例如矩阵的边界可以形成三个不同的回路，其中一个回路位于另一个回路内部。

要提取这些回路，第一步是构建所有“墙壁”的地图：每当一个单元格的内容与同一行中下一个单元格的内容不同时，就会出现垂直墙壁；相反，当该内容与下一行中同一单元格的内容不同时，就会出现水平墙壁。

data = [[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
        [ 0, 1, 1, 1, 1, 0, 0, 0, 0, 0 ],
        [ 0, 1, 0, 0, 1, 0, 1, 1, 0, 0 ],
        [ 0, 1, 0, 0, 1, 0, 1, 1, 1, 0 ],
        [ 0, 1, 1, 1, 1, 0, 0, 1, 1, 0 ],
        [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]]

rows = len(data)
cols = len(data[0])

walls = [[2*(data[r][c] != data[r][c+1]) + (data[r][c] != data[r+1][c])
          for c in range(cols-1)]
         for r in range(rows-1)]

在上面的示例中，我使用了两个位：0x01用于标记水平墙壁，0x02用于标记垂直墙壁。对于给定的单元格(r,c)，墙是该单元格的右侧和底部墙壁。

为了简化起见，我还假设有趣的区域没有接触矩阵的限制；这可以通过添加额外的零行和列或通过在返回虚拟元素的矩阵访问函数中包装来解决。

要构建边界列表，只需从墙上的任意点开始移动，并按照墙壁的方向移动，处理它们时从地图中删除墙壁。当您无法再移动时，已完成一个循环（因为在从内/外标志矩阵构建的图中，所有顶点的度数保证是偶数，所以您保证会完成循环）。

同时使用奇偶填充规则填充所有这些周期也保证能够复制原始矩阵。

在以下代码中，我使用r和c作为行/列索引，而使用i和j来表示边界上的点...例如对于单元格(r=3, c=2)，模式如下：

其中红色墙对应于位0x02，绿色墙对应于位0x01。 walls矩阵比原始数据矩阵少一行和一列，因为假定最后一行或列上不可能出现墙壁。

result = []
for r in range(rows-1):
    for c in range(cols-1):
        if walls[r][c] & 1:
            i, j = r+1, c
            cycle = [(i, j)]
            while True:
                if i < rows-1 and walls[i][j-1] & 2:
                    ii, jj = i+1, j
                    walls[i][j-1] -= 2
                elif i > 0 and walls[i-1][j-1] & 2:
                    ii, jj = i-1, j
                    walls[i-1][j-1] -= 2
                elif j < cols-1 and walls[i-1][j] & 1:
                    ii, jj = i, j+1
                    walls[i-1][j] -= 1
                elif j > 0 and walls[i-1][j-1] & 1:
                    ii, jj = i, j-1
                    walls[i-1][j-1] -= 1
                else:
                    break
                i, j = ii, jj
                cycle.append((ii, jj))
            result.append(cycle)

基本上，代码从边界的一个点开始，检查是否可以沿着墙壁向上、向下、向左或向右移动。当无法再移动时，一个循环已经完成，可以添加到最终结果中。

该算法的复杂度为O(rows*cols)，即与输入大小成比例，并且它是最优的（在大O意义下），因为您不能在不读取输入的情况下计算结果。这很容易理解，因为while循环的主体不能进入比地图中的墙壁总数更多的次数（每次迭代都会删除一堵墙）。

编辑：

该算法可以修改为仅生成简单循环作为输出（即只访问每个顶点一次的路径）。

result = []
index = [[-1] * cols for x in range(rows)]
for r in range(rows-1):
    for c in range(cols-1):
        if walls[r][c] & 1:
            i, j = r+1, c
            cycle = [(i, j)]
            index[i][j] = 0
            while True:
                if i > 0 and walls[i-1][j-1] & 2:
                    ii, jj = i-1, j
                    walls[i-1][j-1] -= 2
                elif j > 0 and walls[i-1][j-1] & 1:
                    ii, jj = i, j-1
                    walls[i-1][j-1] -= 1
                elif i < rows-1 and walls[i][j-1] & 2:
                    ii, jj = i+1, j
                    walls[i][j-1] -= 2
                elif j < cols-1 and walls[i-1][j] & 1:
                    ii, jj = i, j+1
                    walls[i-1][j] -= 1
                else:
                    break
                i, j = ii, jj
                cycle.append((ii, jj))
                ix = index[i][j]
                if ix >= 0:
                    # closed a loop
                    result.append(cycle[ix:])
                    for i_, j_ in cycle[ix:]:
                        index[i_][j_] = -1
                    cycle = cycle[:ix+1]
                index[i][j] = len(cycle)-1

在处理过程中，如果遇到相同的顶点两次，则通过添加单独的循环来实现此操作（index表存储给定i,j点在当前构建的循环中的基于0的索引）。

- 6502

---

我看到这段代码唯一的问题是，它将对角块视为同一个整体块。也就是说，如果矩阵中只有两个“1”是对角线上的，你的算法将返回一个包含这两个点的环。在这种情况下，我需要得到两个不同的循环。有没有快速的改变方式来实现这个目标呢？ - Kinru

@Kinru：请查看编辑。这个修改版本的输出由非自交循环组成。但是请注意，仍然可能存在一个包含在另一个循环中的循环...（孔） - 6502

@Kinru 为什么需要两个不同的循环？这不是原始问题定义的一部分。 - Mark Ransom

@MarkRansom 那是我原来问题中的一个错误，我应该更清楚地表达。 - Kinru

@Kinru，我仍然想知道为什么存在这个约束条件，因为它使问题变得更加复杂。 - Mark Ransom

由于这些点实际上组成的“地形”类型，根据我的当前实现，它们只能有两个邻居。这是因为它们之间存在类似弹簧的力，如果允许一个角点与我所谓的多个块相交，那么会极大地复杂化我的物理模型。这与绘制多边形没有什么关系。 - Kinru

Answer 2

我猜这可以用不同的方法来实现，对于斜线相连的单元格被视为不同轮廓的情况，可能有一种相当简单的方法：

你只需要保持单元格和角落的方向。例如，你从某个地球单元格的右上角开始（假设如果它是边界，则上方或右侧的单元格或两者都是空的），并想顺时针走。

如果右侧的单元格是地球，则将当前单元格更改为该单元格，并将角落更改为左上角（它是相同的点）。然后进行下一次迭代。

在另一种情况下，如果您从某个地球单元的右上角开始并想顺时针移动。如果右侧的单元格不是地球，则不更改当前单元格并将角落更改为右下角（即下一个点）。

所以你也可以对其他三个可能的角落进行对称操作，直到回到起点为止。

这里是我写的伪代码，它使用与图片相同的索引方式，并假设沿边界的所有单元格都是空闲的，否则您需要检查索引是否超出范围。

我还需要一个额外的数组，几乎与矩阵具有相同的维度来标记已处理的轮廓，它需要比矩阵宽1个单元格，因为我将标记垂直线，每个垂直线都应该具有其右侧单元格的坐标。请注意，在上述8个描述中只有2种情况需要标记垂直线。

    int mark[,] = new int[height,width+1]       
    start_i = i = 0;
    start_j = j = 0;
    direction = start_direction = top_left;
    index = 0;

    //outer cycle through different contours
    while(true)
    {
      ++index;
      //scanning for contours through all the matrix
      //continue from the same place, we stopped last time
      for(/*i = i*/; i < n; i++)
      {
        for(/*j = j*/; j < n; j++)
        {
           //if we found earth
           if(m[i,j] == 1)
           {
               //check if previous cell is nothing
               //check if line between this and previous contour doesn't already added
               if(m[i,j - 1] == 0 && mark[i,j] == 0)
               {
                   direction = bottom_left;
                   break;
               }

               //the same for next cell
               if(m[i,j + 1] == 0 && mark[i,j+1] == 0)
               {
                   direction = top_right;
                   break;
               }
           }
        }
        //break if we found contour
        if(i != start_i || j != start_j)
          break;
      }

      //stop if we didn't find any contour
      if(i == start_i && j == start_j)
      {
        break;
      }

      polygon = new polygon;
      start_i = i;
      start_j = j;
      start_direction = direction;

      //now the main part of algorithm described above
      do
      {
        if(direction == top_left)
        {
           if(n(i-1,j) == 1)
           {
              direction = bottom_left;
              position = (i-1,j)
           }
           else
           {
              direction = top_right;
              polygon.Add(i,j+1);       
           }
        }
        if(direction == top_right;)
        {
           if(n[i,j + 1] == 1)
           {
              direction = top_left;
              position = (i,j + 1)
           }
           else
           {
              direction = bottom_right;
              mark[i, j + 1] = index;//don't forget to mark edges!
              polygon.Add(i+1,j+1);       
           }
        } 
        if(direction == bottom_right;
        {
           if(n[i+1,j] == 1)
           {
              direction = top_right;
              position = (i+1,j)
           }
           else
           {
              direction = bottom_left;
              polygon.Add(i+1,j);       
           }
        } 
        if(direction == bottom_left)
        {
           if(n[i,j - 1] == 1)
           {
              direction = bottom_right;
              position = [i,j - 1]
           }
           else
           {
              direction = top_left;
              mark[i, j] = index;//don't forget to mark edges!
              polygon.Add(i,j);       
           }
        } 
      //and we can stop as we reached the starting state
      }while(i != start_i || j != start_j || direction != start_direction);

      //stop if it was last cell
      if(i == n-1 && j == n- 1)
      {
        break;
      }
    }

此外，您可能需要知道哪个轮廓在哪个轮廓内部，并且您可能需要一个堆栈来保持您在扫描时所处的轮廓，因此每次您穿过现有轮廓时，您需要将其添加到堆栈中或者如果它已经在堆栈顶部，则将其移除。

这将导致代码的下列更改：

  ...
  //continue from the same place, we stopped last time
  for(/*i = i*/; i < n; i++)
  {
    for(/*j = j*/; j < n; j++)
    {
       if(mark[i,j] != 0)
       {
           if(stack.top() == mark [i,j])
           {
                stack.pop();
           }
           else
           {
                stack.push(mark [i,j]);
           }
       }
       //if we found earth
       if(m[i,j] == 1)
       {
           ...

- Lurr

Answer 3

如果你的矩阵可能包含随机模式，那么答案比看起来更加复杂。

一方面，它们可能是任意数量的不同多边形，而且每个多边形都可能是空心的。

此外，即使没有洞，找到区域的轮廓对于绘制表面也没什么帮助。您的GPU最终需要三角形，这意味着您需要将多边形分解为矩形。

寻找覆盖一堆中空正方形的最小矩形集（即没有已知解决方案的NP完全问题）已经得到深入研究。

存在算法可以找到这些没有孔的形状的最优分解，但它们非常复杂。

贪婪算法易于实现，通常可以产生可接受的结果。

因此，我会在您的矩阵上进行贪婪搜索，收集矩形，直到所有“1”值都被访问。将这些矩形转换为坐标应该很容易，因为您确切地知道左上角和右下角的位置。

贪心扫描如下：

while your matrix is not empty
    move to first "1" value. This is the rectangle top left corner
    from this corner, extend the rectangle in x and y to maximize its surface
    store the rectangle in a list and clear all corresponding "1" values

- kuroi neko

Answer 4

我认为这个方法可行：

对于每个填充的方块，检查它的邻居是否填充。对于未填充的邻居，将其适当的边添加到边列表中。生成这些边时，按顺时针或逆时针方向进行。

要构建完整的路径，请从集合中取出任何一条边并将其添加到路径中。这些边是有序的，所以看第二个顶点。在集合中找到第一个顶点等于该第二个顶点的边。从集合中取出该边并将其添加到路径中。继续操作，直到路径闭合。

重复上述步骤以生成路径列表。简单多边形应该组成一条路径。复杂多边形——在此情况下是有中间孔的——应由几个路径组成。

- Tommy