3

我正在处理由二维网格上的方形瓷砖组成的多边形。一个多边形简单地存储为一个元组列表，每个元组代表一个图块的坐标。多边形始终是连续的并且没有孔。

我想要做的是确定哪些图块代表多边形边界的顶点，以便稍后我可以在每个图块之间进行追踪以生成多边形的边界，或者确定两个连续顶点之间的距离以找到长度一方等

这是一个多边形示例（一个 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，但任何见解都值得赞赏，即使它是伪代码。

4

3 回答 3

4

假设您的形状没有内部孔。

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

从这个板块，尝试向右直走 如果你不能，直直直下，直下等，直到你选择了一个方向。这保证了我们可以追踪多边形的顺时针周长

继续朝着您选择的方向迈出步伐。每一步之后：

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

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

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

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

继续走边缘，直到你到达你的初始瓷砖。在 1 个瓷砖挤压的情况下，您可以不止一次地走过瓷砖。

如果此算法在您的脑海中没有意义，请尝试拿出一些纸并手动进行操作：)

于 2013-02-12T08:07:58.487 回答
1

这个问题是一个凸包变化，例如可以应用礼品包装算法。离散坐标和线方向的约束导致简化。这是一些给出所需答案的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)
于 2017-06-04T11:17:06.977 回答
0

我只会计算顶点之间的线的斜率

# 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])
于 2013-02-12T08:11:59.663 回答