#This is a spatial hash.
#A simple way of putting it is: "we store these points in a grid,
# and you can retrieve an entire grid cell with its points."
import random
import time
import math
def from_points(cell_size, points):
"""
Build a HashMap from a list of points.
"""
hashmap = HashMap(cell_size)
#setdefault = hashmap.grid.setdefault
#key = hashmap.key
for point in points:
#setdefault(key(point),[]).append(point)
dict_setdefault(hashmap.grid, hashmap.key(point),[]).append(point)
return hashmap
# this is because dict.setdefault does not work.
def dict_setdefault(D, k, d):
#D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D
r = D.get(k,d)
if k not in D:
D[k] = d
return r
class HashMap(object):
"""
Hashmap is a a spatial index which can be used for a broad-phase
collision detection strategy.
"""
def __init__(self, cell_size):
self.cell_size = cell_size
self.grid = {}
def key(self, point):
cell_size = self.cell_size
return (
int((math.floor(point[0]/cell_size))*cell_size),
int((math.floor(point[1]/cell_size))*cell_size),
int((math.floor(point[2]/cell_size))*cell_size)
)
def insert(self, point):
"""
Insert point into the hashmap.
"""
#self.grid.setdefault(self.key(point), []).append(point)
dict_setdefault( self.grid, self.key(point), []).append(point)
def query(self, point):
"""
Return all objects in the cell specified by point.
"""
#return self.grid.setdefault(self.key(point), [])
return dict_setdefault( self.grid, self.key(point), [])
if __name__ == '__main__':
#NUM_POINTS = 100000
#NUM_POINTS = 6000
NUM_POINTS = 1000000
#new_point = lambda: (
# #random.uniform(-100,100),random.uniform(-100,100),random.uniform(-100,100)
# (random.random() * 200) - 100, (random.random() * 200) - 100, (random.random() * 200) - 100
#)
#points = [new_point() for i in xrange(NUM_POINTS)]
points = []
for i in range(NUM_POINTS):
points.append( ((random.random() * 200) - 100,
(random.random() * 200) - 100,
(random.random() * 200) - 100 ) )
T = time.time()
hashmap = from_points(10, points)
print 1.0 / (time.time() - T), '%d point builds per second.' % NUM_POINTS
T = time.time()
# if this is using ints, then the thing fails to compile with shedskin.
#hashmap.query((0,0,0))
hashmap.query((0.0,0.0,0.0))
print 1.0 / (time.time() - T), '%d point queries per second.' % NUM_POINTS
#hashmap.insert([22,33,33])
hashmap.insert((22.0,33.0,33.0))