由正方形网格组成的多边形
pig*_*sus 7 algorithm polygon computational-geometry graph-algorithm
我正在寻找一种算法来查找围绕连续的没有孔的正方形网格的多边形，如下所示：
。
我已经让每个网格方块存储有关它们所组成的周围区域的边缘类型的数据（即顶部、右上角、顶部底部、无边缘等），所以我认为这数据可以被算法利用。如果有人能为这种算法提供一些伪代码，那就太好了。
算法的输入将是一个数据对象列表，每个数据对象都有一个描述网格位置的 Vector2Int（请注意，这些只是网格内的位置，而不是顶点）以及给出正方形所具有的边类型的 Enum与周边地区。输出将是描述周围多边形顶点的 Vector2 的有序列表，假设每个网格正方形的大小都是一个单位。
我在下面的链接中发现了类似的问题，但我想对特定于我的情况的算法进行一些详细说明，特别是考虑到我已经存储的有关边缘的数据。我还希望该算法避免计算每个正方形的顶点并运行一堆简单的搜索来消除共享的顶点，因为我觉得这对于我的特定应用程序来说计算成本可能太高。我只是怀疑必须有更好的方法。
编辑：现在我开始认为某种迷宫行走算法实际上可能适合我的情况。我正在研究一个我认为可行的解决方案，但编写起来非常麻烦（涉及对方形边缘和圆周行进方向的大量条件检查）并且可能没有那么快。