python - 如何确定由网格单元组成的任意形状的角/顶点单元

Question

我正在处理由二维网格上的方形图 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 中工作，但任何见解都值得赞赏，即使它是伪代码。

Answer 1

假设您的形状没有内孔。

找到最上面的行。选择这一行最左边的图 block 。这保证我们从一个角落开始。

从这个方 block 开始，尝试向右直行如果不能，则一直直行、直下等，直到您选择了一个方向。这保证我们可以追踪多边形的顺时针周长

继续朝着您选择的方向迈进。每一步之后:

• 如果下一步是在瓷砖上，逆时针旋转并再看一遍。
• 如果下一步要进入空白区域，请顺时针旋转并再次查看。

一旦您移动到空白空间并再次回到瓷砖上，就停止旋转。

如果我们从初始方向旋转，我们一定站在一个顶点上。将其标记为这样。

将您遍历的所有其他图 block 标记为边缘的一部分。

继续沿着边缘走，直到到达您的初始图 block 。在 1 个瓷砖挤压的情况下，您可能会多次走过瓷砖。

如果这个算法在你的头脑中没有意义，试着拿出一些纸并用手跟着它:)