java - 在高度图数组中查找边和顶点

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

(已编辑问题的答案:)某种形式的图遍历应该可以做到这一点，我只会给出一个非常高级的描述。从高度图的最高层开始，对于任何岛屿，从某个内部点开始。向北走，直到到达岛的边缘或 map 的边缘。以顺时针(或逆时针，无论您需要哪个)的方式，仅探索那些属于岛边缘的单元格。

对于较低级别，从与较高级别岛屿相邻的单元格开始，并执行相同的操作。

---

(在澄清编辑之前回答问题:)在我看来你想要 convex hull每个“岛屿”。使用图形遍历找到连续的组(您的“岛”)(我最喜欢 BFS，但口味不同；只要两个单元格包含相同的值并且相邻，就认为它们属于同一个岛)，然后应用一些 convex hull algorithm .