在Heightmap阵列中寻找边缘和顶点

Question

假设我已经生成了一个高度图数组，为了简单起见，该数组中只有三个高度值：0、1和2。例如，它可能如下所示：

000000111111110000000000000000000000000000000000
001111111111111111000000000001111111111111000000
000011111111111111100000000000000011122111110000
000000000111111100000000000000000111221110000000
000000000000000000000000000001111122222111111100
000000000000000000000000111111111111111111000000
000000000000000000000111111111100000000000001111
000000000001111111111110000000000000000001111111
000000001111222222211100000000000000000000001110
000000000011112221100000000000000011111000000000
000000000000111111100000000000001111111110000000
000000001111111110000000000000000011111000000000
000000000000000000000000000000000000000000000000

我想要做的是在这个高度图中找到‘顶点’，并以一个逻辑顺序输出它们(这样我就可以画一条直线到每一个连续点，最终跟踪形状的轮廓)。例如，对于右上角的第一组1：

000000111111110000000           .1------2       
001111111111111111000        8-'         `--3   
000011111111111111100  -->    `7---.        .4  
000000000111111100000               6-----5'    
000000000000000000000                           

第二个图中的数字是我需要找到的坐标(按正确的顺序)，而点和破折号是我从每一点跟踪得到形状轮廓的线条。

有什么算法可以用来找出这些顶点吗？如果没有，找到它们的最有效方法是什么？

我目前正在做的是使用递归找到每一个‘岛’或‘群’的数字，然后把这个形状的所有外部点作为顶点。但是，我的方法很慢，而且顶点的顺序也不对。

谢谢你的帮助，我希望这一切都是有意义的。

编辑：，我从评论中意识到，使用顶点会使我失去一些形状的区域。我认为，而不是顶点，那么我需要找到的是所有的点的边缘的形状，但正确的顺序。所以我的例子应该是：

000000111111110000000             12345678       
001111111111111111000         17          9,10   
000011111111111111100  -->     16,15         11  
000000000111111100000               14,13,12     
000000000000000000000                            

很抱歉给你造成了混乱。

Answer 1

(回答编辑的问题：)某种形式的图遍历应该这样做，我只会给出一个非常高层次的描述。从高度图的最高层开始，对于任何岛屿，从内部点开始。向北走，直到你到达岛的边缘或地图的边缘。在顺时针方向(或逆时针方向，无论你需要什么)，只探索那些可以属于岛屿边缘的细胞。

对于较低的级别，从邻近较高层次的岛屿的细胞开始，并进行同样的操作。

(在澄清编辑之前回答问题：)在我看来，你想要每个“岛”的凸壳。使用图遍历(我最喜欢BFS，但口味不同)查找连续组(您的“岛”)，当两个单元格包含相同的值并且相邻时，考虑它们属于同一个岛，然后应用一些凸壳算法。

Answer 2

你可以试试阿尔法形状。α形状定义为delaunay三角剖分，边不超过alpha。