Scan all grid points in a ring around a center point

ringscan.py

#!/usr/bin/python

#
# Scan all grid points in a ring around a center point
# @author Daniel Pulido <dpmcmlxxvi@gmail.com>
# @copyright Copyright (c) 2014 Daniel Pulido <dpmcmlxxvi@gmail.com>
# @file ringscan.py
# @license MIT License (http://opensource.org/licenses/MIT)
#

def chebyshev(point1, point2):
    """
    Scan points in a square pattern
    """

    return max(abs(point1[0] - point2[0]), abs(point1[1] - point2[1]))

def manhattan(point1, point2):
    """
    Scan points in a diamond pattern
    """

    return abs(point1[0] - point2[0]) + abs(point1[1] - point2[1])

def ringscan(x0, y0, distance, metric=chebyshev):
    """
    Scan all grid points in a ring around a center point
    """

    center = [x0, y0]
    initial = [x0 + distance, y0]
    current = initial

    # Define clock-wise step directions
    direction = 0
    steps = {0: [ 0, 1],
             1: [-1, 1],
             2: [-1, 0],
             3: [-1,-1],
             4: [ 0,-1],
             5: [ 1,-1],
             6: [ 1, 0],
             7: [ 1, 1]}
    nsteps = len(steps)

    while True:

        # Short-circuit special case
        if distance == 0:
            yield current[0], current[1]
            break

        # Try and take a step and check if still within distance
        next = [current[i] + steps[direction][i] for i in range(2)]
        if metric(center, next) != distance:
            direction = (direction + 1) % nsteps
            continue
        yield current[0], current[1]

        # Check if we have come all the way around
        current = next
        if current == initial:
            break

def main():

    # Define center point and radius to search
    x0 = 0
    y0 = 0
    radius = 1
    for x, y in ringscan(x0, y0, radius):
        print x, y

if __name__ == "__main__":
    main()