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? -- http://mail.python.org/mailman/listinfo/python-list