グリッド上のポリゴンのコーナー座標を取得する

Question

特定のポリゴンのすべてのコーナーの座標を計算する必要があるという問題があります。私が入手できる情報は、その形状内のタイル/正方形のリストです。形状は常にこれらの正方形で構成され、常にグリッド上に正確に配置されます。これらの種類の形状の2つの例は次のとおりです。

2つの例

最初の例の形状を取り上げて、次の画像のドットで表されるコーナーの座標を知りたいと思います。

コーナードットのある例1

私が入手できる正確な情報は、その形をしているすべての正方形のタイルのリストです。それらは、左下隅で表されます。したがって、例1では、次の情報があります。

$$(0,0); (0,1); (0,2); (0,3); (1,0); (1,1); (1,2); (1,3); (2,0); (2,1); (2,2); (3,0); (3,1); (3,2); (4,2); (5,2); (5,3)$$

リストを繰り返し、内側の正方形を削除して、外側の正方形だけが残るようにしました。次に、すべての最大値と最小値を取得します。問題は、形状の中央のコーナーではなく、最も外側の4つのコーナーしか取得できないことです。

誰かがこれにアプローチする良い方法を知っていますか？

Answer 1

1. 外側のエッジのセットを計算します（正方形のエッジは、存在する正方形と存在しない正方形を区切る場合、外側のエッジです）
2. グラフウォーキングアルゴリズム、たとえばbfsによってエッジを並べ替えます。
3. 順序付けられた外側のエッジのセットから、目的のポイントをターニングポイントとして計算します（前のエッジの方向が次のエッジと同じでない場合）。

import copy
from collections import deque
from PIL import Image, ImageDraw
s=('(0,0);(0,1);(0,2);(0,3);(1,0);(1,1);(1,2);(1,3);(2,0);(2,1);(2,2);'
   '(3,0);(3,1);(3,2);(4,2);(5,2);(5,3)')
s=[tuple(int(j) for j in i.strip('()').split(',')) for i in s.split(';')]
mx,my=[max(i[j] for i in s) for j in [0,1]]
im=Image.new('RGB',(20*(mx+2),20*(my+2)),(255,255,255))
draw=ImageDraw.Draw(im)
for x,y in s:
    draw.rectangle(tuple(i*20+10 for i in [x,y,x+1,y+1]),
                   fill=(192,192,192),outline=None,width=0)

borders=lambda x,y:[frozenset([(x+a,y+b),(x+c,y+d)])
    for (a,b),(c,d),(e,f) in [
        ((0,0),(0,1),(0,-1)),
        ((0,0),(1,0),(-1,0)),
        ((1,0),(1,1),(0,1)),
        ((0,1),(1,1),(1,0)),
         ]
    if (x+f,y+e) not in s]
edges=sum((borders(*i) for i in s),[])
for e in edges:
    draw.line(tuple(i*20+10 for i in [j for p in e for j in p]),
              fill=(0,0,0),width=1)
#im.show()
adjacent=lambda x,y:[(x+i,y+j) for i,j in
                     [(1,0),(0,1),(-1,0),(0,-1)]]
def bfs(s):
    res,res_p=[],[]
    s=copy.copy(s)
    s_taken=set()
    #assuming 1 connected component
    for x in s:break
    s.remove(x)
    res.append(x)
    p=list(x)[0]
    res_p.append(p)
    q=deque([p])
    #print(p)
    while q:
        p=q.popleft()
        for p1 in adjacent(*p):
            e=frozenset([p,p1])
            if e in s:
                q.append(p1)
                s.remove(e)
                res.append(e)
                res_p.append(p1)
                break
    return res,res_p

ordered_edges,ordered_points=bfs(set(edges))
orientation=lambda x:(lambda y:y[0][0]==y[1][0])(list(x))
res=[]
for e1,p,e2 in zip(ordered_edges,
                   ordered_points,
                   ordered_edges[1:]+ordered_edges[:1]):
    if orientation(e1)!=orientation(e2):
        res.append(p)

for x,y in res:
    draw.ellipse((20*x+10-2,20*y+10-2,20*x+10+2,20*y+10+2),
                 fill=(0,0,255))
im.show()

オンラインでお試しください