Geometry – Getting Corner Coordinates of a Polygon on a Grid

coordinate systemsgeometrypolygons

I have a problem in which I need to calculate the coordinates of all corners in a given polygon. The information I have available is a list of tiles/squares within that shape. The shape is always made out of these squares and always aligns exactly on the grid. Two examples of these kinds of shapes are as follows:

Two examples

Taking the first example shape, I would like to know the coordinates of the corners represented by the dots in the following image:

Example 1 with corners dots

The exact information I have available is a list of all the squared tiles that are in that shape. They are represented by their most bottom-left corner. So in example 1, I have the following information:

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

I tried to iterate the list and remove the inside squares so that I only have the outer ones left. Then I would take all the maximum and minimum values. The problem then, is that I only get the four most outer corners and not the corners in the middle of the shape.

Anyone know a good way to approach this?

Best Answer

  1. Compute the set of outer edges (an square edge is outer edge if it delimits present square from absent)
  2. Order the edges by some graph walking algorithm, say, bfs.
  3. From the ordered set of outer edges compute the desired points as the turning points (when previous edge do not have the same direction as the next one).

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

Try it online

2

Related Question