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

Question

我正在处理由方形瓷砖组成的多边形，这些瓷砖在一个二维网格上。简单来说，多边形就是用一系列坐标点来表示，每个坐标点对应一个瓷砖。所有的多边形都是连在一起的，没有空洞。

我想做的是找出哪些瓷砖是多边形边界上的顶点，这样我就可以在这些顶点之间画出多边形的边界，或者计算两个相邻顶点之间的距离来找出边的长度等等。

这里有一个多边形的例子（一个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)]

顶点按顺时针方向列出，围绕边界走一圈。

在测试一些案例时，我发现这个问题比我想象的要复杂得多，尤其是在一些特殊情况下，比如当多边形有一个1块瓷砖宽的突起时（在这种情况下，可能需要把其中一块瓷砖作为顶点存储两次？？）。

我正在用Python编程，但任何见解都很受欢迎，即使是伪代码也可以。

Answer 1

我只需要计算一下顶点之间的线的斜率。

# Do sort stuff

vertices = []
for position, polygon in enumerate(polygon_tiles):
    # look for IndexErrors
    try:
         polygon_tiles[position+1]
    except IndexError:
         break

    try:
        polygon_tiles[position+2]
    except IndexError:
        # Bad practice
        position = position - 1

    # calculate the slope of the line between of vertex 1 and vertex 2  
    s1 = (polygon_tiles[position+1][1] - polygon[1]) / (polygon_tiles[position+1][0] - polygon[0])
    # calculate the slope of vertex 2 and vertex 3
    s2 = (polygon_tiles[position+2][1] - polygon_tiles[position+1][1]) / (polygon_tiles[position+2][0] - polygon_tiles[position+1][0])
    # if the slopes differ then you have a vertex
    if d1 != d2:
        vertices.append(polygon_tiles[position+1])

Answer 2

这个问题是一个凸包的变种，比如可以用礼物包装算法来解决。由于坐标是离散的，而且线的方向有要求，这让问题变得简单一些。下面是一些Python代码，可以得到想要的结果（Patashu的回答也是这个意思）：

#!/usr/bin/python                                                                                                                                                              

import math

def neighbors(coord):
    for dir in (1,0):
        for delta in (-1,1):
            yield (coord[0]+dir*delta, coord[1]+(1-dir)*delta)

def get_angle(dir1, dir2):
    angle = math.acos(dir1[0] * dir2[0] + dir1[1] * dir2[1])
    cross = dir1[1] * dir2[0] - dir1[0] * dir2[1]
    if cross > 0:
        angle = -angle
    return angle

def trace(p):
    if len(p) <= 1:
        return p

    # start at top left-most point                                                                                                                                             
    pt0 = min(p, key = lambda t: (t[1],t[0]))
    dir = (0,-1)
    pt = pt0
    outline = [pt0]
    while True:
        pt_next = None
        angle_next = 10 # dummy value to be replaced                                                                                                                           
        dir_next = None

        # find leftmost neighbor                                                                                                                                               
        for n in neighbors(pt):
            if n in p:
                dir2 = (n[0]-pt[0], n[1]-pt[1])
                angle = get_angle(dir, dir2)
                if angle < angle_next:
                    pt_next = n
                    angle_next = angle
                    dir_next = dir2
        if angle_next != 0:
           outline.append(pt_next)
        else:
            # previous point was unnecessary                                                                                                                                   
            outline[-1]=pt_next
        if pt_next == pt0:
            return outline[:-1]
        pt = pt_next
        dir = dir_next

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)]
outline = trace(polygon_tiles)
print(outline)

Answer 3

假设你的形状没有内部的洞。

首先找到最上面的一行。然后选择这一行最左边的方块。这样可以确保我们从一个角落开始。

从这个方块出发，试着向右走。如果不能，就试着向右下走、向下走，等等，直到你找到一个可以走的方向。这样可以确保我们能顺着多边形的边缘顺时针走一圈。

继续朝着你选择的方向走。每走一步后：

• 如果下一步会走到一个方块上，就逆时针转动一下再看看。
• 如果下一步会走到空地上，就顺时针转动一下再看看。

一旦你走到了空地上，然后又回到了方块上，就停止转动。

如果我们从最初的方向转动了，那我们一定是在一个顶点上。把它标记出来。

把你经过的每一个方块都标记为边的一部分。

继续沿着边走，直到回到你最开始的方块。如果有一个方块突出，你可以多次走过同一个方块。

如果这个算法在你脑海中不太清晰，可以试着拿出纸来，手动跟着这个步骤走一遍 :)