我正在尝试为我玩的游戏开发在线地图编辑程序。
地图的数据有点大。如果我为每个正方形发送数据,则中等大小的地图数据接近 1 mb。
我认为我能做的是在地图上找到边界并以此为基础创建多边形。
目前我:
- 找到最西北的边界并从那里开始。对于我的示例地图,它是 (3,2)
- 然后,检查北、东、南,然后是西,然后转到第一个没有 1 作为数据的未访问位置。
- 如果没有未访问的位置,请转到历史上最远的位置。
这适用于北部地区。但是,当我到达南部地区时,它会向北检查并发现这是一个未访问的位置并前往那里。它搞砸的地方的坐标是 13,11。
显然,这并没有给我想要的边界,也没有走遍整个地图。所以,有些事情需要改变。
我考虑以与以前相同的操作顺序添加边界检查(NESW)。但是,也有可能把它搞砸。
在 (13,11) 处,它会向北检查,发现它是一个未访问的位置。而这一次,那里有一个边界,所以它会认为可以去那里。
我应该怎么做才能走完整个外边界?
我确实看过这里提到的凸包算法,但我认为这不是我需要的。我可能不正确,但这是我期望的凸包结果。
虽然这确实减少了一点地图的大小,但仍有很多我不需要的数据。当我需要获取地图中项目的内部边界时,尺寸减小会丢失,因为它们也是不规则的。
那么,我如何确保我实际上是在走外边界呢?