假设我生成了一个高度图数组,为了简单起见,该数组中只有三个高度值: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
抱歉造成困惑。
最佳答案
(回答已编辑的问题:)某种形式的图遍历应该可以做到这一点,我只会给出它的非常高级的描述。从高度图的最高层开始,对于任何岛屿,从某个内部点开始。向北走,直到到达岛屿边缘或 map 边缘。以顺时针(或逆时针,无论您需要什么)的方式,仅探索那些属于岛屿边缘的单元格。
对于较低级别,从与较高级别岛屿相邻的单元格开始并执行相同的操作。
(在澄清编辑之前回答问题:) 在我看来,你想要 convex hull每个“岛屿”。通过图形遍历找到连续的组(您的“岛屿”)(我最喜欢BFS,但口味不同;只要两个单元格包含相同的值并且相邻,就认为它们属于同一个岛),然后应用一些convex hull algorithm .
关于java - 查找高度图数组中的边和顶点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29736809/