hashing and collision detection

[Aaron Brady]

Hi group,

You are making good on your promise from a year ago: "This is a
helpful group. Give us more to go on, and you are likely to receive
thousands of dollars worth of consulting for free."
http://groups.google.com/group/comp.lang.python/msg/2e2906eaa804812c
- Bryan Olson

I have an idea, which has probably been invented a thousand times, and
is probably a nice smooth round wheel by now, but I didn't know how to
websearch for it, and didn't try.

I am trying to floating-point collide rectangles, axis-oriented, on a
large board.  I thought about having every rectangle participate in a
hash, several units big, and merely testing collisions within high
population hashes.  The pathological case is where rectangles are very
small, and thus will be able to fit too many in a bucket.  I'm willing
to rule it out for now... for-ever.  </cackle>

Most hash slots will only have zero or one members; therefore, I only
need to check collision in a small fraction of slots: those that have
two or more members.

If slots are too small, moving an object is an expensive operation,
because it will need to add and remove itself from many buckets.  If
slots are too large, too many objects can fit in them, and a simple
rectangle collision will check too many.  But for my purposes, the
balance should be a fairly large plateau.

I am thinking of a simple dictionary, which maps tuples to a list of
members in that slot: { ( 0, 0 ), ( 0, 3 ), ( 0, 6 ), ( 3,
0 ), ... }.  Where space becomes a concern, empty slots can be removed
and re-added to and from the dictionary.

Last note: the entire rectangles participate in the list of members of
a slot, not just their subsegments which reside in the particular
slot.

What are your thoughts?