在高度图数组中查找边和顶点
Finding Edges and Vertices Within Heightmap Array
假设我生成了一个高度图数组，为简单起见，其中只有三个高度值：0、1 和2。例如，它可能看起来像这样：
000000111111110000000000000000000000000000000000
001111111111111111000000000001111111111111000000
000011111111111111100000000000000011122111110000
000000000111111100000000000000000111221110000000
000000000000000000000000000001111122222111111100
000000000000000000000000111111111111111111000000
000000000000000000000111111111100000000000001111
000000000001111111111110000000000000000001111111
000000001111222222211100000000000000000000001110
000000000011112221100000000000000011111000000000
000000000000111111100000000000001111111110000000
000000001111111110000000000000000011111000000000
000000000000000000000000000000000000000000000000
我想要做的是在这个高度图中找到 'vertices'，并以逻辑顺序输出它们（这样我就可以画一条线到每个连续的点，最终将追踪轮廓的形状）。例如，对于右上角 1 中的第一个 'group'：
000000111111110000000 .1------2
001111111111111111000 8-' `--3
000011111111111111100 --> `7---. .4
000000000111111100000 6-----5'
000000000000000000000
第二张图中的数字是我需要找到的坐标（以正确的顺序），点和破折号是我从每个点追踪以获得形状轮廓的线。
有什么算法可以用来找到这些顶点吗？如果没有，找到它们的最有效方法是什么？
我现在做的是用递归的方式找到每一个'islands'或者'groups'的数字，然后把这个形状所有外面的点作为顶点。但是，我的方法很慢，而且顶点顺序不正确。
感谢您的帮助，我希望这一切都有意义。
编辑：
我从评论中意识到，使用顶点会使我失去形状的某些区域。我认为我需要找到的不是顶点，而是 all 形状边缘的点，但顺序正确。所以我的例子应该是：
000000111111110000000 12345678
001111111111111111000 17 9,10
000011111111111111100 --> 16,15 11
000000000111111100000 14,13,12
000000000000000000000
抱歉造成混淆。
您可以尝试 alpha 形状。 Alpha 形状定义为边缘不超过 alpha 的 delaunay 三角剖分。
（编辑后的问题的答案：）某种形式的图遍历应该可以做到这一点，我只会给出一个非常高级的描述。从高度图的最高层开始，对于任何岛屿，从某个内部点开始。向北走，直到到达岛的边缘或地图的边缘。以顺时针（或逆时针，无论您需要哪个）的方式，只探索那些属于岛边缘的单元格。
对于较低级别，从与较高级别岛屿相邻的单元格开始，并执行相同的操作。
（在澄清编辑之前回答问题：）
在我看来你想要 convex hull of every "island". Find contiguous groups (your "islands") with graph traversal (I like BFS best, but tastes differ; consider two cell to belong to the same island whenever they contain the same value and are adjacent), then apply some convex hull algorithm.
假设我生成了一个高度图数组，为简单起见，其中只有三个高度值：0、1 和2。例如，它可能看起来像这样：
000000111111110000000000000000000000000000000000
001111111111111111000000000001111111111111000000
000011111111111111100000000000000011122111110000
000000000111111100000000000000000111221110000000
000000000000000000000000000001111122222111111100
000000000000000000000000111111111111111111000000
000000000000000000000111111111100000000000001111
000000000001111111111110000000000000000001111111
000000001111222222211100000000000000000000001110
000000000011112221100000000000000011111000000000
000000000000111111100000000000001111111110000000
000000001111111110000000000000000011111000000000
000000000000000000000000000000000000000000000000
我想要做的是在这个高度图中找到 'vertices'，并以逻辑顺序输出它们（这样我就可以画一条线到每个连续的点，最终将追踪轮廓的形状）。例如，对于右上角 1 中的第一个 'group'：
000000111111110000000 .1------2
001111111111111111000 8-' `--3
000011111111111111100 --> `7---. .4
000000000111111100000 6-----5'
000000000000000000000
第二张图中的数字是我需要找到的坐标（以正确的顺序），点和破折号是我从每个点追踪以获得形状轮廓的线。
有什么算法可以用来找到这些顶点吗？如果没有，找到它们的最有效方法是什么？
我现在做的是用递归的方式找到每一个'islands'或者'groups'的数字，然后把这个形状所有外面的点作为顶点。但是，我的方法很慢，而且顶点顺序不正确。
感谢您的帮助，我希望这一切都有意义。
编辑： 我从评论中意识到，使用顶点会使我失去形状的某些区域。我认为我需要找到的不是顶点，而是 all 形状边缘的点，但顺序正确。所以我的例子应该是：
000000111111110000000 12345678
001111111111111111000 17 9,10
000011111111111111100 --> 16,15 11
000000000111111100000 14,13,12
000000000000000000000
抱歉造成混淆。
您可以尝试 alpha 形状。 Alpha 形状定义为边缘不超过 alpha 的 delaunay 三角剖分。
（编辑后的问题的答案：）某种形式的图遍历应该可以做到这一点，我只会给出一个非常高级的描述。从高度图的最高层开始，对于任何岛屿，从某个内部点开始。向北走，直到到达岛的边缘或地图的边缘。以顺时针（或逆时针，无论您需要哪个）的方式，只探索那些属于岛边缘的单元格。
对于较低级别，从与较高级别岛屿相邻的单元格开始，并执行相同的操作。
（在澄清编辑之前回答问题：） 在我看来你想要 convex hull of every "island". Find contiguous groups (your "islands") with graph traversal (I like BFS best, but tastes differ; consider two cell to belong to the same island whenever they contain the same value and are adjacent), then apply some convex hull algorithm.