From: Vish on
Hi,

I need to hash 3d coordinates to a grid which has been divided into
4*4*4 squares. Using python, I thought of a simple way as follows:

CELL_SIZE = 4

def key(point):

return (
int((floor(point[0]/CELL_SIZE))*CELL_SIZE),
int((floor(point[1]/CELL_SIZE))*CELL_SIZE),
int((floor(point[2]/CELL_SIZE))*CELL_SIZE)
)


Since python allows keys to be tuples, I think that this should work.
Is there a better (more efficient) way to do it?

Thank you,
Vishal
From: MRAB on
Vish wrote:
> Hi,
>
> I need to hash 3d coordinates to a grid which has been divided into
> 4*4*4 squares. Using python, I thought of a simple way as follows:
>
> CELL_SIZE = 4
>
> def key(point):
>
> return (
> int((floor(point[0]/CELL_SIZE))*CELL_SIZE),
> int((floor(point[1]/CELL_SIZE))*CELL_SIZE),
> int((floor(point[2]/CELL_SIZE))*CELL_SIZE)
> )
>
>
> Since python allows keys to be tuples, I think that this should work.
> Is there a better (more efficient) way to do it?
>
floor(x) returns an integer, so floor(x/CELL_SIZE)*CELL_SIZE is an
integer multiple of CELL_SIZE, also an integer. There's actually no
point (unintentional pun!) to multiplying by CELL_SIZE:

CELL_SIZE = 4

def key(point):
return (
floor(point[0] / CELL_SIZE),
floor(point[1] / CELL_SIZE),
floor(point[2] / CELL_SIZE)
)

From: Paul Rubin on
Vish <vahuja4(a)gmail.com> writes:
> I need to hash 3d coordinates to a grid which has been divided into
> 4*4*4 squares. Using python, I thought of a simple way as follows:

Use the built-in hash function:

>>> p = (1, 2, 3)
>>> print hash(p)
2528502973977326415

You can of course mod that by the table size:

>>> print hash(p) % (4*4*4)
15
From: Martin v. Loewis on
> floor(x) returns an integer

Why do you say that? Assuming you are talking about math.floor, it works
differently for me:

py> math.floor(10.0/3)
3.0

Regards,
Martin
From: Martin v. Loewis on
> CELL_SIZE = 4
>
> def key(point):
>
> return (
> int((floor(point[0]/CELL_SIZE))*CELL_SIZE),
> int((floor(point[1]/CELL_SIZE))*CELL_SIZE),
> int((floor(point[2]/CELL_SIZE))*CELL_SIZE)
> )
>
>
> Since python allows keys to be tuples, I think that this should work.
> Is there a better (more efficient) way to do it?

You don't say why you want to do hashing in the first place. If it is to
access elements in a lookup table, and you are now using a dictionary,
I'd suggest to replace that with a list. For 4x4x4 elements, you could
either do

table[int(point[0]/CELL_SIZE)][int(point[1]/CELL_SIZE)][int(point[2]/CELL_SIZE)]

(i.e. have nested lists), or you allocate a list of 64 elements, and use

def key(point):
return 16*int(point[0]/CELL_SIZE) + 4*int(point[1]/CELL_SIZE) +\
int(point[2]/CELL_SIZE)

table[key(point)]

You could even use that key function as a key to a dictionary, if you
can't use lists for some reason.

Regards,
Martin