Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > hashing and collision detection

Thread Tools

hashing and collision detection

Aaron Brady
Posts: n/a
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."
- 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

What are your thoughts?
Reply With Quote

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
a pipeline with collision detection VHDL 3 08-02-2005 05:47 PM
Jam signal and collision detection Cisco 14 04-28-2005 07:22 PM
collision detection and penetration depth Thorsten Reichelt Python 3 10-25-2004 02:09 PM
Collision detection with Rectangles Abs Java 4 05-14-2004 07:56 AM
Collision detection Stephen Wolfe Java 1 02-20-2004 12:20 PM