views:

2359

answers:

6

I'm trying to write a method that will calculate if two circles are overlapping. I've come up with the following and I'm just curious to know if there is anyway it could be optimised further.

private static boolean isCollision(Point2D p1, float r1, Point2D p2, float r2)
{
 float a,dx, dy;
 a = (r1+r2) * (r1+r2);
 dx = (float) (p1.getX() - p2.getX());
 dy = (float) (p1.getY() - p2.getY());

 if (a > (dx*dx) + (dy*dy))
 {
  return true;
 }
 return false;
}
+9  A: 

Overlap or intersect?

If intersect, don't forget about the case where the circles don't intersect because they are inside each other.

If it's overlap, I don't really see how you could optimize further; you're comparing the point distances to the sum of the radii, using distance squared to avoid taking a square root. Doesn't seem like there's any fat left to trim.

Jason S
+10  A: 

Hmm. That looks pretty good as far as the math goes. Some minor points on how to make the Java side of it faster and terser:

  • If you used doubles instead of floats for the radii, you wouldn't have to down-cast the doubles to floats.
  • If you specifically ask for Point2D.Double parameters, you can use their x and y public fields instead of using the getters.
  • Also, why the if (foo) { return true; } else { return false; }? Just do return foo;!

An improved version, then:

private static boolean isCollision(Point2D.Double p1, double r1, Point2D.Double p2, double r2)
{
    final double a = r1 + r2;
    final double dx = p1.x - p2.x;
    final double dy = p1.y - p2.y;
    return a * a > (dx * dx + dy * dy);
}

(Note that if your code is entirely float-based, you can do the same thing with Point2D.Float and floats.)

Zarkonnen
You might also consider early termination if the bounding rectangles don't overlap. Whether this is actually worth implementing will depend in part on how many of circles and rectangles actually overlap.
Bill Michell
I've been thinking about that. My gut feeling (to be verified when I have a bit more time) is that having branches is going to be more time-consuming for the CPU than having to do a few more floating point multiplications.
Zarkonnen
While I understand it would be faster not to cast to a float, would it be more efficient if you just used floats instead of doubles?
Peter Nore
Probably, actually. It's just that nearly nothing else in Java seems to use floats. Another thing that it's worth testing.
Zarkonnen
+1  A: 

It doesn't make your code faster, but I'd prefer:

return a > (dx*dx + dy*dy);
Peter
+4  A: 

Do you really need to cater for any possible Point2D implementation? If you don't have to, it will save a virtual call:

private static boolean isCollisionFloat (Point2D.Float p1, float r1, Point2D.Float p2, float r2)
{
    final float r = r1+r2;
    final float dx = p1.x - p2.x;
    final float dy = p1.y - p2.y;

    return (r*r) > (dx*dx) + (dy*dy);
}
testing 1000x1000 points:
Doing nothing took 6 ms
Doing isCollision passing Point2D.Float took 128 ms
Doing isCollision passing Point2D.Double took 127 ms
Doing isCollisionFloat took 71 ms
Doing isCollisionDouble took 72 ms

If you can, choose one or the other, rather than catering for both.


The problem with perf questions is that you really do have to measure the effects, by which time someone has posted the same answer as unsupported opinion.

Pete Kirkham
Hmm, now *I*'m curious whether making r, dx and dy final makes a performance difference. It certainly can't hurt. *copies shamelessly into own answer*
Zarkonnen
Probably not, but I am in the habit of making anything which isn't changing final.
Pete Kirkham
And that in itself is a very good thing to do. I've recently been nudging towards the (slightly mad) viewpoint that the default in Java should be final, and you have to use a "var" keyword if you want a variable...
Zarkonnen
+1  A: 

Your algorithm can be further optimized by calculating the rectangular bounds of each circle and seeing if they overlap. If they don't overlap then just return false. This avoids multiplication for those circles who's rectangular bounds don't overlap (ie, they aren't close to each other). Addition/subtraction for the rectangular bound calculation is cheaper than multiplication.

Steve Kuo
I would think that the bounds calculation would lose most of the winnings, though. But why don't you try it and post the results?
Michael Myers
+1  A: 

I don't know if its relevant in your case, but if you want to check for overlaps between your circle and many other circles (let's say thousands of circles), you can try to organize your circles in quad-trees (see http://en.wikipedia.org/wiki/Quadtree) and do a tree look-up (based on the bounding rectangle of your circle) in the quad-tree.

Patrick