hashing and collision detection

Discussion in 'Python' started by Aaron Brady, Apr 7, 2009.

  1. Aaron Brady

    Aaron Brady Guest

    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?
     
    Aaron Brady, Apr 7, 2009
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    665
  2. Stephen Wolfe

    Collision detection

    Stephen Wolfe, Feb 19, 2004, in forum: Java
    Replies:
    1
    Views:
    617
    Alex Hunsley
    Feb 20, 2004
  3. Abs
    Replies:
    4
    Views:
    8,457
    Jesper Nordenberg
    May 14, 2004
  4. Thorsten Reichelt

    collision detection and penetration depth

    Thorsten Reichelt, Oct 25, 2004, in forum: Python
    Replies:
    3
    Views:
    642
    Thorsten Reichelt
    Oct 25, 2004
  5. Collision Detection

    , Apr 16, 2008, in forum: Java
    Replies:
    3
    Views:
    367
    Jeff Higgins
    Apr 16, 2008
Loading...

Share This Page