对多边形的点进行排序以进行绘制
Sort polygon's points for drawing
我有一个矩阵（0 表示无，1 表示地形）代表我游戏中的一个关卡。矩阵对应于我的屏幕被分解成的网格，并指示我的地形走向。
我的地形实际上是由网格内每个块的角上的 4 个点组成的。当您有多个连接的块时，我使用合并单元格算法来删除重复点和任何内部点。结果是我得到了一个仅代表多边形外边缘的点列表。
要绘制此多边形，我需要将这些点按某种顺序（顺时针或逆时针）排列，以便每个点后面都有它的相邻点。显然第一个和最后一个点需要是邻居。由于这一切都在一个网格中，我知道相邻点之间的确切距离。
问题是我无法想出一种算法，该算法允许我在按顺序排列点的同时绕着多边形的边缘“走动”。我相信应该有一种方法可以利用我有代表几何的矩阵这一事实，这意味着只有一种可能的方法来绘制多边形（即使它是凹面的）。
我已经尝试了几种使用贪婪算法的方法，但似乎无法找到一种方法来知道在每种情况下我想朝哪个方向行进。鉴于任何特定点最多可以有 3 个邻居（第四个不包括在内，因为它是“起点”，这意味着我已经对它进行了排序）我需要一种方法来知道移动的方向。
更新
我一直在尝试的另一种方法是按 X（使用 Y 的决胜局）对点进行排序，这给了我 topmost/leftmost 优势。它还保证我从外边缘开始。然而，我仍在努力寻找一种算法，保证我在外面不穿越。
这是一个示例矩阵：
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
对应于此（黑点代表我的观点）：
我想有不同的方法可以做到这一点，我想有一个非常简单的方法来处理对角线连接的单元格计算为不同轮廓的情况：
你只需要保持单元格和角的方向。例如，您从某个地球单元格的右上角开始（假设是上部或右侧单元格，或者如果是边界则两者都什么都不是）并想顺时针方向走。
如果右边的单元格是地球，则将当前单元格更改为它并将角更改为左上角（这是同一点）。然后你进入下一次迭代。
在其他情况下，如果您从某个地球单元格的右上角开始并想顺时针方向走。如果右边的单元格不是地球，那么您不要更改当前单元格并将角更改为右下角，（这是下一个点）
所以其他三个可能的角你也有对称的情况，你可以进行下一次迭代，直到回到起点。
所以这是我写的伪代码，它使用与图片相同的索引，并假设所有边框上的单元格都是空闲的，否则你需要检查索引id是否超出范围。
我还需要额外的数组，其尺寸几乎与矩阵相同，以标记处理过的轮廓，它需要比矩阵宽 1 个单元格，因为我要标记垂直线，并且每条垂直线应该有它右侧的单元格坐标。注意上面8个dwscribe中只有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)
{
...
这似乎对我有用：
对于每个填充的方块，检查它的哪些相邻方块被填充。对于那些不是的边，将适当的边添加到边列表中。根据指示顺时针或逆时针生成这些边。
要构建完整路径，首先从集合中拉出任何边并将其添加到路径中。它有一个顺序，所以看第二个顶点。在集合中找到第一个顶点等于第二个顶点的边。从集合中拉出该边并将其添加到路径中。继续，直到路径关闭。
重复生成路径列表。一个简单的多边形最终应该是一条路径。一个复杂的多边形——在这种情况下中间有孔的多边形——将有多个。
如果您的矩阵可以包含随机模式，那么答案比看起来要复杂得多。
一方面，它们可能是任意数量的不同多边形，而且每个多边形都可能是空心的。
此外，找到一个区域的轮廓（即使没有孔）对绘制表面帮助不大。您的 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
首先请考虑一般矩阵的输出可以由多个闭环组成；例如矩阵的边界
形成三个不同的循环，其中一个放在另一个循环中。
要提取这些循环，第一步是构建所有内容的地图 "walls"：每当一个单元格的内容与同一行中的下一个单元格的内容不同时，您就会有一堵垂直墙；当内容与下一行中的同一单元格不同时，您就会看到一堵水平墙。
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) 单元格，壁是单元格的右壁和底壁。
为简单起见，我还假设感兴趣的区域没有触及矩阵的极限；这可以通过添加额外的零行和列或通过将矩阵访问包装在一个函数中来解决，该函数 returns 0 对于矩阵外的虚拟元素。
要构建边界列表，您需要简单地从墙上的任意点开始并沿着墙壁移动，在处理它们时从地图上移除墙壁。当你不能再移动时，一个循环已经完成（你保证完成循环，因为在以这种方式从 inside/outside 矩阵构建的图形中，标志的度数保证在所有顶点中都是均匀的）。
使用奇偶填充规则同时填充所有这些循环也可以保证重现原始矩阵。
在下面的代码中，我使用 r 和 c 作为 row/col 索引，使用 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 table 存储给定的 i,j 点 0正在构建的当前周期中基于索引的索引）。
我有一个矩阵（0 表示无，1 表示地形）代表我游戏中的一个关卡。矩阵对应于我的屏幕被分解成的网格，并指示我的地形走向。
我的地形实际上是由网格内每个块的角上的 4 个点组成的。当您有多个连接的块时，我使用合并单元格算法来删除重复点和任何内部点。结果是我得到了一个仅代表多边形外边缘的点列表。
要绘制此多边形，我需要将这些点按某种顺序（顺时针或逆时针）排列，以便每个点后面都有它的相邻点。显然第一个和最后一个点需要是邻居。由于这一切都在一个网格中，我知道相邻点之间的确切距离。
问题是我无法想出一种算法，该算法允许我在按顺序排列点的同时绕着多边形的边缘“走动”。我相信应该有一种方法可以利用我有代表几何的矩阵这一事实，这意味着只有一种可能的方法来绘制多边形（即使它是凹面的）。
我已经尝试了几种使用贪婪算法的方法，但似乎无法找到一种方法来知道在每种情况下我想朝哪个方向行进。鉴于任何特定点最多可以有 3 个邻居（第四个不包括在内，因为它是“起点”，这意味着我已经对它进行了排序）我需要一种方法来知道移动的方向。
更新
我一直在尝试的另一种方法是按 X（使用 Y 的决胜局）对点进行排序，这给了我 topmost/leftmost 优势。它还保证我从外边缘开始。然而，我仍在努力寻找一种算法，保证我在外面不穿越。
这是一个示例矩阵：
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
对应于此（黑点代表我的观点）：
我想有不同的方法可以做到这一点，我想有一个非常简单的方法来处理对角线连接的单元格计算为不同轮廓的情况：
你只需要保持单元格和角的方向。例如，您从某个地球单元格的右上角开始（假设是上部或右侧单元格，或者如果是边界则两者都什么都不是）并想顺时针方向走。
如果右边的单元格是地球，则将当前单元格更改为它并将角更改为左上角（这是同一点）。然后你进入下一次迭代。
在其他情况下，如果您从某个地球单元格的右上角开始并想顺时针方向走。如果右边的单元格不是地球，那么您不要更改当前单元格并将角更改为右下角，（这是下一个点）
所以其他三个可能的角你也有对称的情况，你可以进行下一次迭代，直到回到起点。
所以这是我写的伪代码，它使用与图片相同的索引，并假设所有边框上的单元格都是空闲的，否则你需要检查索引id是否超出范围。
我还需要额外的数组，其尺寸几乎与矩阵相同，以标记处理过的轮廓，它需要比矩阵宽 1 个单元格，因为我要标记垂直线，并且每条垂直线应该有它右侧的单元格坐标。注意上面8个dwscribe中只有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)
{
...
这似乎对我有用：
对于每个填充的方块，检查它的哪些相邻方块被填充。对于那些不是的边，将适当的边添加到边列表中。根据指示顺时针或逆时针生成这些边。
要构建完整路径，首先从集合中拉出任何边并将其添加到路径中。它有一个顺序，所以看第二个顶点。在集合中找到第一个顶点等于第二个顶点的边。从集合中拉出该边并将其添加到路径中。继续，直到路径关闭。
重复生成路径列表。一个简单的多边形最终应该是一条路径。一个复杂的多边形——在这种情况下中间有孔的多边形——将有多个。
如果您的矩阵可以包含随机模式，那么答案比看起来要复杂得多。
一方面，它们可能是任意数量的不同多边形，而且每个多边形都可能是空心的。
此外，找到一个区域的轮廓（即使没有孔）对绘制表面帮助不大。您的 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
首先请考虑一般矩阵的输出可以由多个闭环组成；例如矩阵的边界
形成三个不同的循环，其中一个放在另一个循环中。
要提取这些循环，第一步是构建所有内容的地图 "walls"：每当一个单元格的内容与同一行中的下一个单元格的内容不同时，您就会有一堵垂直墙；当内容与下一行中的同一单元格不同时，您就会看到一堵水平墙。
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) 单元格，壁是单元格的右壁和底壁。
为简单起见，我还假设感兴趣的区域没有触及矩阵的极限；这可以通过添加额外的零行和列或通过将矩阵访问包装在一个函数中来解决，该函数 returns 0 对于矩阵外的虚拟元素。
要构建边界列表，您需要简单地从墙上的任意点开始并沿着墙壁移动，在处理它们时从地图上移除墙壁。当你不能再移动时，一个循环已经完成（你保证完成循环，因为在以这种方式从 inside/outside 矩阵构建的图形中，标志的度数保证在所有顶点中都是均匀的）。
使用奇偶填充规则同时填充所有这些循环也可以保证重现原始矩阵。
在下面的代码中，我使用 r 和 c 作为 row/col 索引，使用 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 table 存储给定的 i,j 点 0正在构建的当前周期中基于索引的索引）。