Group a list of coordinate points into neighbors

gistfile1.py

sample = [(1,1), (1,2), (1,3), (1,4), (1,5), (1,6),
                               (2,4), (2,5), (2,6),
          (3,1),               (3,4), (3,5), (3,6),
          (4,1), (4,2), (4,3), (4,4), (4,5), (4,6),

          (6,1), (6,2), (6,3), (6,4), (6,5), (6,6)]
def separate(data):
    """ Separates a list of coordinates into a list of list of coordinates by adjacency """

    # create a dict filled with Nones to make loooking up easier
    record = dict()
    sorted_data = sorted(data)
    for x, y in sorted_data:
        if x in record.keys():
            record[x][y] = None
        else:
            record[x] = dict()
            record[x][y] = None

    def in_record(x, y):
        """ returns true if x, y is in record """
        return x in record.keys() and y in record[x].keys()

    def find_adjacents(x, y):
        """ find adjacent cells (8 directions) """
        check = [((x - 1, y - 1), in_record(x - 1, y - 1)),
                 ((x + 1, y + 1), in_record(x + 1, y + 1)),
                 ((x - 1, y + 1), in_record(x - 1, y + 1)),
                 ((x + 1, y - 1), in_record(x + 1, y - 1)),
                 ((x - 1, y), in_record(x - 1, y)),
                 ((x + 1, y), in_record(x + 1, y)),
                 ((x, y - 1), in_record(x, y - 1)),
                 ((x, y - 1), in_record(x, y - 1))]

        result = []
        for coord, found in check:
            if found:
                result.append(coord)
        return result

    def get_group(cells):
        """ Returns group id number of first of cells, or None """
        for x, y in cells:
            if record[x][y] is not None:
                return record[x][y]
        return None


    # loop over each, assigning a group id
    group_id = 0
    for x, y in sorted_data:
        cells = find_adjacents(x, y)
        if len(cells) == 0:
            # no neighbors found, make a new group
            record[x][y] = group_id
            group_id += 1
        else:
            # found cells
            found_group = get_group(cells)
            if found_group is None:
                # no neighbors have a group
                # give this cell and all neighbors a new group
                record[x][y] = group_id
                for f_x, f_y in cells:
                    record[f_x][f_y] = group_id
                group_id += 1
            else:
                # found a neighbor in a group
                # apply that group to this and all other neighbors
                record[x][y] = found_group
                for f_x, f_y in cells:
                    record[f_x][f_y] = found_group

    result = []
    for i in range(0, group_id):
        result.append([])
        for x, y_dict in record.items():
            for y, group in y_dict.items():
                if group == i:
                    result[i].append( (x, y) )
    result = [r for r in result if len(r) != 0]
    return result

if __name__ == "__main__":
    print(separate(sample))