Collision detection of 2 lines in java (Android)

Very simple question. How do you achieve collision detection with lines drawn in Java? Just lines. No rectangles, circles or images, bitmaps.. just lines.

By the way these lines are not straight. They are built of hundreds of very small lines that represent movement of a player (their gps coords as they move), so they meander all over the place as the player moves. All the lines are connected. The end point of one line is the beginning point of the next and so on. It is an unbroken line in this respect. There are no gaps.

I tried storing the x,y values of the beginning points of the lines in an array and then iterated through this array to determine whether the point has been visited before. This is fine if the player visits the exact coords again, but what if he is in a place half way between these recorded point开发者_如何学Cs?

This is the background to the problem if it helps. But the main question is my focus here. How do you achieve collision detection of lines in Java?

---

From what I know you are doing it in the proper way. I would suggest possibly hashing the lines via coordinate location so there are fewer line checks. You could also cut down on the number of checks if an estimated larger straight line (made from an average of smaller lines) was made and used to check instead.

---

If I understand correctly, your problem is not strictly line intersection (which can be found easily on the web) but how to handle hundreds of them ?

Maybe you should think of a spatial structure for your data to limit computations. Take a look at "quadtree" for example.

You would test intersections only on a subset of all your coordinates.

---

What you call a line, you might call a List<Line2D> - a list of straight line segments. If you have List<Line2D> a and List<Line2D> b, then you want to compare every Line in a with every Line in b. I assume you can see how to find the crossing point of two straight line segments - or Line2D will even do this for you. eg:

for(Line2D line1 : a) {
   for(Line2D line2 : b) {
      if(a.intersectsLine(b)) {
         return true;
      }
   }
}
return false;

Now this code won't be fast, but might be fast enough. If it is too slow then you will have to look at optimisations - this can be done in a number of ways, quadtrees or sorting in one dimension are two obvious simple steps.