如何確定由網格單元格組成的任意形狀的拐角/頂點單元格

Question

我正在處理由2D網格上的正方形瓷磚組成的多邊形。多邊形只是存儲爲元組列表，每個元組代表一個圖塊的座標。多邊形總是連續的，沒有孔。

我想要做的是確定哪個圖塊表示沿着多邊形邊界的頂點，以便稍後我可以在每個圖塊之間跟蹤以產生多邊形的邊界，或者確定兩個連續頂點之間的距離找到一個邊的長度等

這裏是一個多邊形的一個例子（5×4矩形從左上角減去3×2矩形，產生一個向後的「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

假設你的形狀沒有內部孔。

找到最上面的一行。選取該行的最左邊的圖塊。這保證我們從一個角落開始。

從這個瓷磚，試圖直走右如果你不能，直走，直下等，直到你選擇了一個方向。這可以追蹤多邊形的順時針周長

繼續按照您選擇的方向採取措施。每個步驟後：

• 如果下一步將在瓷磚上，逆時針旋轉並再次看。
• 如果下一步將進入空白區域，請順時針旋轉並再次查看。

一旦移動到空白區域並再次回到瓷磚上，停止旋轉。

如果我們從最初的方向旋轉，我們必須站在頂點上。標記爲這樣。

標記您穿過邊緣的一部分的所有其他瓷磚。

繼續走邊緣，直到您到達您的初始瓷磚。在1個瓷磚擠壓的情況下，您可以不止一次地在瓷磚上行走。

如果在你的腦袋該算法沒有意義，嘗試獲得了一些文件，並用手:)

Answer 2

我只想計算頂點之間的直線的斜率下它

# 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 3

這個問題是一個convex hull變化，爲此例如可以應用gift wrapping algorithm。離散座標和線方向的限制導致簡化。下面是一些給出所需答案的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)