我正在处理由二维网格上的方形图 block 组成的多边形。多边形简单地存储为元组列表，每个元组代表一个图 block 的坐标。多边形始终是连续的并且没有孔。
我想要做的是确定哪些图 block 代表沿多边形边界的顶点，这样以后我可以在每个图 block 之间进行追踪以生成多边形的边界，或者确定两个连续顶点之间的距离找到边的长度等。
这是一个多边形的例子(一个 5x4 的矩形，从左上角减去一个 3x2 的矩形，产生一个向后的“L”):
polygon_tiles = [(3, 0), (4, 0), (3, 1), (4, 1), (0, 2), (1, 2), (2, 2), (3, 2),
(4, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3)]
理想情况下，我正在寻找的算法会产生如下所示的结果:
polygon_verts = [(3, 0), (4, 0), (4, 3), (0, 3), (0, 2), (3, 2)]
按照顺时针方向围绕边界追踪的顺序列出顶点。
只是fiddling around对于一些测试用例，这个问题似乎比我想象的要复杂得多，尤其是在奇怪的情况下，比如当一个多边形有一个 1 瓦宽的挤压时(在这种情况下，其中一个瓦片可能必须存储为顶点两次？？)。
我在 Python 中工作，但任何见解都值得赞赏，即使它是伪代码。
最佳答案
假设您的形状没有内孔。
找到最上面的行。选择这一行最左边的图 block 。这保证我们从一个角落开始。
从这个方 block 开始，尝试向右直行如果不能，则一直直行、直下等，直到您选择了一个方向。这保证我们可以追踪多边形的顺时针周长
继续朝着您选择的方向迈进。每一步之后:
- 如果下一步是在瓷砖上，逆时针旋转并再看一遍。
- 如果下一步要进入空白区域，请顺时针旋转并再次查看。
一旦您移动到空白空间并再次回到瓷砖上，就停止旋转。
如果我们从初始方向旋转，我们一定站在一个顶点上。将其标记为这样。
将您遍历的所有其他图 block 标记为边缘的一部分。
继续沿着边缘走，直到到达您的初始图 block 。在 1 个瓷砖挤压的情况下，您可能会多次走过瓷砖。
如果这个算法在你的头脑中没有意义，试着拿出一些纸并用手跟着它:)
关于python - 如何确定由网格单元组成的任意形状的角/顶点单元，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14827775/