Ottenere le coordinate degli angoli del poligono su una griglia

Aug 23 2020

Ho un problema in cui ho bisogno di calcolare le coordinate di tutti gli angoli in un dato poligono. Le informazioni che ho a disposizione sono un elenco di tessere / quadrati all'interno di quella forma. La forma è sempre composta da questi quadrati e si allinea sempre esattamente sulla griglia. Due esempi di questi tipi di forme sono i seguenti:

Due esempi

Prendendo la prima forma di esempio, vorrei conoscere le coordinate degli angoli rappresentati dai punti nell'immagine seguente:

Esempio 1 con punti agli angoli

Le informazioni esatte che ho a disposizione sono un elenco di tutte le tessere quadrate che hanno quella forma. Sono rappresentati dal loro angolo più in basso a sinistra. Quindi, nell'esempio 1, ho le seguenti informazioni:

$$(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)$$

Ho provato a scorrere l'elenco e rimuovere i quadrati interni in modo che rimangano solo quelli esterni. Quindi prenderei tutti i valori massimo e minimo. Il problema quindi è che ottengo solo i quattro angoli più esterni e non gli angoli al centro della forma.

Qualcuno sa un buon modo per avvicinarsi a questo?

Risposte

AlexeyBurdin Aug 23 2020 at 18:57
  1. Calcola l'insieme dei bordi esterni (un bordo quadrato è bordo esterno se delimita il quadrato presente da assente)
  2. Ordina i bordi con un algoritmo di esplorazione del grafico, ad esempio bfs.
  3. Dall'insieme ordinato di bordi esterni calcolare i punti desiderati come punti di svolta (quando il bordo precedente non ha la stessa direzione di quello successivo).

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()

Provalo online