Collision Detecting Involving HashTable

[CooKieLord]

For my CSI assignment, I need to detect collisions between a rectangle and a bunch of lines.

The way it's done is that there are Line2D objects stored in a HashTable, which in turn is stored in a HashTable.

My problem is finding an appropriate hash function in order to speed up collision detecting. The skeleton that was given had the Line2D objects stored in an ArrayList and then when we run the algorithm to detect collision, it would iterate through the entire data structure, which as we all know, is not very efficient.

Attached is the PDF with the assignment guidelines, the original skeleton, and my current implementation.

Here is my question: Can you guide me to finding an appropriate hash function to store my Line2D objects?

Note: The implementation is in LineSet, and you run the applet in LineIntersection.

[DemonWasp]

Unfortunately, there is no "hash" function to determine whether collisions occur or not. The example provided (iteration over an ArrayList) is actually the only method available. EDIT: You can iterate over whatever you want, ArrayList is just one of the better options.

To speed up collision detection, you could use something called "bounding boxes", where you make a box (x1..x2, y1..y2) around each line segment. If the boxes for any two line segments do not overlap, then you can safely say that no collision occurs; if they overlap, then you have to do additional computation (find the actual collision). To be honest, though, you'll need millions of lines before you notice any realistic slowdown in your given problem (lines intersecting a single rectangle)

HashTables are actually a means of storing key-value data pairs such that you can easily retrieve the value corresponding to a given key in more-or-less constant time (very fast). They will not help your collision-detection go faster.

[CooKieLord]

[Edit] I wrote HashTable in the first post, I meant HashMap...sorry![/edit]

Essentially, what I needed to do was use a HashMap to store a Line2D along with a key. I was supposed to use a key such that by using the position of the rectangle, I would be able to quickly determine in which gridMap I would look for an intersection.

Another thing was that a Line2D could span over many gridMaps, and I would need to add it in every one. I needed to use the slope of the line in order to find this out.

However, the assignment was due yesterday, I managed to pull up a functional program, although not optimal (I am iterating through all the HashMaps to see if a line intersects orz).

It also eats lines I will post what I have later (when I'm at home) for anyone who is curious, although it's very messy because I comment out lines rather than deleting them when I implement things.