CODEWITHSUNDEEP
pythonalgorithmdata-structuresbins
donut juice
donut juice

Reputation: 267

python - divide world into bins

I am working on trying to put moving balls into appropriate bins. I like to think I'm on the right track but I've been stuck for awhile now.

I left code out that didn't seem relevant to my question but if those who answer need further details I can provide them. Basically, I have a world of 200 moving balls. They have an X and Y coordinate. I want to divide the world into square bins of width 256 and place the balls in the appropriate bin.

My approach to this was to put them into a dictionary. It looked like this:

dict_of_balls = {}
for i in range(len(balls)):
    xb = int(balls[i].x/256)
    yb = int(balls[i].y/256)

and I wanted to make the keys a tuple of the (xb, yb) pairs and then place the appropriate balls in that bin but I don't think you can use tuples as keys...

The code is below:

import math
import random
import time
import sys


ball_min_radius = 16.0 #world coordinates         
ball_max_radius = 128.0  #world coordniates
number_balls = 200

class Ball:
    """ 
    Implements a point/ball
    """

    def __init__(self):
          self.x = random.uniform(world_min_x,world_max_x)
          self.y = random.uniform(world_min_y,world_max_y)
          self.radius = int(random.uniform(ball_min_radius,ball_max_radius))
    def __lt__(self, other):
        return self.id < other.id

def main():
    world_min_x = -200.0*number_balls**.5  # minimum x in world coordinates
    world_max_x = +200.0*number_balls**.5  # maximum x in world coordinates
    world_min_y = -200.0*number_balls**.5  # minimum y in world coordinates
    world_max_y = +200.0*number_balls**.5  # maximum y in world coordinates

    balls = [Ball() for i in range(number_balls)]

so does anyone have any ideas for how to divide the world into bins based on the given world coordinates? I am unsure of which data structure to use since I can't use tuples for keys. Thanks in advance for any feedback.

Upvotes: 1

Views: 326

Answers (2)

chrigolex
chrigolex

Reputation: 1

You can use tuple for keys in a dictionary, since tuple is immutable. The only data type you can't use for a dictionary key is a list [] or set {} 

**a = {(1,2):'example1', (2,3):'example2'}
>>> a[(1,2)]
'example1'**

So I believe this should make it much easier to solve your problem.

Upvotes: 0

enderland
enderland

Reputation: 14135

Why do you want a dictionary? Here's how you would do this, but keep in mind you will only get one ball per bin because you are specifically casting their key to be (int, int) and keys are unique.

If you use a collection, you can also sort (in my example I sort by the region identifiers):

I am not sure what you are doing that for, but you can do it:

import math
import random
import time
import sys


ball_min_radius = 16.0 #world coordinates         
ball_max_radius = 128.0  #world coordniates
number_balls = 200

world_min_x = -200.0*number_balls**.5  # minimum x in world coordinates
world_max_x = +200.0*number_balls**.5  # maximum x in world coordinates
world_min_y = -200.0*number_balls**.5  # minimum y in world coordinates
world_max_y = +200.0*number_balls**.5  # maximum y in world coordinates


class Ball:
    """ 
    Implements a point/ball
    """

    def __init__(self):
          self.x = random.uniform(world_min_x,world_max_x)
          self.y = random.uniform(world_min_y,world_max_y)
          self.radius = int(random.uniform(ball_min_radius,ball_max_radius))
    def __lt__(self, other):
        return self.id < other.id

    def __str__(self):
        return 'x={x} y={y} r={r}'.format(x=self.x, y=self.y, r=self.radius)

def main():

    balls = [Ball() for i in range(number_balls)]

    dict_of_balls = {}
    ball_collection = []
    for b in balls:
        xb = int(b.x/256)
        yb = int(b.y/256)
        key = (xb, yb)
        dict_of_balls[key] = b

        ball_collection.append((key, b))

    print 'length of dictionary:{}'.format(len(dict_of_balls.keys()))
    print 'length of collection:{}'.format(len(ball_collection))

Notice that the dictionary has fewer items than the collection.

You can also print each item this way pretty trivially:

    for b in ball_collection:
        print 'ball region: {r}   with coords: {c}'.format(r=b[0], c=b[1])

Or, sort them if you want:

    print 'Collections also let you sort the collection by region(s)...'
    sorted_list = sorted(ball_collection, key= lambda x: (x[0][0], x[0][1]))


    for b in sorted_list:
        print 'ball region: {r}   with coords: {c}'.format(r=b[0], c=b[1])

You can also pretty simply get balls in a specific region too:

    print '... or get only ones in a specific region'
    subset =  [b for b in ball_collection if b[0][0] == 1]

    for b in subset:
        print 'ball region: {r}   with coords: {c}'.format(r=b[0], c=b[1])


main()

A collection seems to do what you are actually wanting.

Upvotes: 1

Related Questions