How to determine corner/vertex cells in an arbitrary shape composed of grid cells

Question

I am dealing with polygons composed of square tiles on a 2D grid. A polygon is simply stored as a list of tuples, with each tuple representing the coordinates of a tile. The polygons are always contiguous and have no holes.

What I want to be able to do is determine which of the tiles represent vertices along the border of the polygon, such that later I could trace between each one to produce the polygon's border, or determine the distance between two consecutive vertices to find the length of a side, etc.

Here is an example of a polygon (a 5x4 rectangle with a 3x2 rectangle subtracted from the top left, producing a backward '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)]

Ideally the algorithm I am seeking would produce a result that looked like this:

polygon_verts = [(3, 0), (4, 0), (4, 3), (0, 3), (0, 2), (3, 2)]

with the vertices listed in order tracing around the border clockwise.

Just fiddling around with some test cases, this problem seems to be much more complicated than I would have thought, especially in weird circumstances like when a polygon has a 1-tile-wide extrusion (in this case one of the tiles might have to be stored as a vertex twice??).

I'm working in Python, but any insight is appreciated, even if it's in pseudocode.

Answer 1

This problem is a convex hull variation, for which e.g. the gift wrapping algorithm could be applied. The constraints of discrete coordinates and line directions lead to simplifications. Here is some python code that gives the desired answer (Patashu's answer is in the same spirit):

#!/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)

Answer 2

I would just calculate the slopes of the lines between the vertices

# 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

Assuming your shape has no internal holes.

Find the topmost row. Pick the leftmost tile of this row. This guarantees we begin on a corner.

From this tile, attempt to go straight right If you can't, go straight downright, straight down, etc until you have picked a direction. This guarnatees we can trace a clockwise perimeter of the polygon

Continue to take steps in your chosen direction. After each step:

• If the next step would be onto a tile, rotate counterclockwise and look again.
• If the next step would be onto an empty space, rotate clockwise and look again.

Stop rotating once you have moved onto empty space and back onto a tile again.

If we rotated from the initial direction, we must be standing on a vertex. Mark it as such.

Mark every other tile you traverse as being part of the edge.

Keep walking the edge until you arrive at your initial tile. You may walk over tiles more than once in the case of 1 tile extrusions.

If this algorithm doesn't make sense in your head, try getting out some paper and following it by hand :)