griddy

x.py

from pprint import pprint

points = [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0),
          (0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1),
          (0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2),
          (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (5, 3),
          (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4),
          (0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5)]
 
grid = [3, 2]
 
def subdivide(points, grid):
    cols, rows = grid
    cols = float(cols)
    rows = float(rows)
 
    # could go through a bit faster, maybe, by just flipping through all points
    # once and populated xs, ys at the same time.  Not a big deal unless you get
    # a really big list of points.  Could also just keep track of maxs/mins if
    # you had a really, really big list an did not want to incur the additional
    # memory expenses

    xs = [x for x, _ in points]
    ys = [y for _, y in points]
 
    top = min(ys)
    bottom = max(ys)
    left = min(xs)
    right = max(xs)
 
    colw = (left + right) / cols
    rowh = (top + bottom) / rows
 
    x = 0
    y = 0
 
    # consider defaultdict
    cells = {}
    # The two while loops could be replaced with ranges.  Also iterating over
    # each point for each grid is a bit inefficent, especially if there are a
    # lot of them and they are distributed unevenly
    while x < cols:
        l = (x * colw) + left
        r = ((x + 1) * colw) + left
        # had a typo here, y should be less than rows, not cols
        while y < rows:
            t = (y * rowh) + top
            b = ((y + 1) * rowh) + top
            cells[(x, y)] = []
            for p_x, p_y in points:
                if (l <= p_x <= r) and (t <= p_y <= b):
                    cells[(x, y)].append((p_x, p_y))
            y += 1
        y = 0
        x += 1
 
    return(cells)


# how I might approach it.  Note this is untested, so you will need to run some
# edge cases at it to make sure the bisecting and stepping is working as
# expected in different cases.
# in particular, I am not sure how this will work with points having negative
# addresses -- i simply have not checked


# first, lets grab some useful stuff from the standard library

from collections import defaultdict
from bisect import bisect
from math import ceil

def subi(points, grid):
    '''partition a list of points into a grid sized grid'''

    cols, rows = grid
 
    xs = [x for x, _ in points]
    ys = [y for _, y in points]
 
    top = min(ys)
    left = min(xs)
    right = max(xs)
    bottom = max(ys)
 
    colw = ceil((left + right) / cols)
    rowh = ceil((top + bottom) / rows)


    # you could use these ranges instead of the while loops above
    col_steps = list(range(left, right, colw))
    row_steps = list(range(top, bottom, rowh))

 
    cells = defaultdict(list)

    # using bisect we can just pass over the points once more
    for x,y in points:
        c,r = bisect(col_steps, x)-1, bisect(row_steps, y) -1
        #print('{},{} -> {},{}'.format(x,y,c,r))
        cells[(c,r)].append((x,y))
    return cells




old = subdivide(points, grid)
revised = subi(points, grid)

# compare
for key in old:
    if set(old[key]) != set(revised[key]):
        print('{} different'.format(key))

pprint(old)
pprint(revised)