Fast method to find point in circle using java2D

Question

To find if a point P(x,y) lies inside the circle with center (x1,y1), there are two possible methods:

1. By using distance() function in Point2D class. This one is equivalent to the distance formula method.

   if (new Point(x1, y1).distance(x, y) < Diam/2)

2. By using contains() function in Ellipse2D.Double. This one checks if the point lies inside the circle.

   if (new Ellipse2D.Double(x1, y1, Diam, Diam).contains(new Point(x, y)));

Both of these functions are built into java2D. Out of curiosity, though, I want to know which one will be faster/better in terms of performance. Any idea?

Answer 1

From the java sources:

Point2D:

public static double distance(double x1, double y1,
                              double x2, double y2)
{
    x1 -= x2;
    y1 -= y2;
    return Math.sqrt(x1 * x1 + y1 * y1);
}

Ellipse2D:

public boolean contains(double x, double y) {
    // Normalize the coordinates compared to the ellipse
    // having a center at 0,0 and a radius of 0.5.
    double ellw = getWidth();
    if (ellw <= 0.0) {
        return false;
    }
    double normx = (x - getX()) / ellw - 0.5;
    double ellh = getHeight();
    if (ellh <= 0.0) {
        return false;
    }
    double normy = (y - getY()) / ellh - 0.5;
    return (normx * normx + normy * normy) < 0.25;
}

So the ellipse has little more to do but no sqrt().

But why don't you put a loop around it and let us know? ;)

EDIT:

So let me do this complex stuff of informational technology for you: (I'm young and need the Points)

    Point2D A = new Point2D.Double( 1.0, 2.0 );
    Point2D B = new Point2D.Double( 2.0, 1.0 );

    Ellipse2D E = new Ellipse2D.Double( 1.0, 2.0, 2.0, 1.0 );

    double x = 1.0;
    double c=0; // Keep compiler from optimizing
    boolean y = false;

    long start = System.currentTimeMillis();
    for( long i=0; i<1000000000L; i++ ){
        y |= E.contains( B );
    }
    long durA = System.currentTimeMillis() - start;

    start = System.currentTimeMillis();
    for( long i=0; i<1000000000L; i++ ){
        c += A.distance( B ) - x/2.0;
    }
    long durB = System.currentTimeMillis() - start;

    System.out.println( y ); // Keep compiler from optimizing
    System.out.println( c );
    System.out.printf( "%d / %d", durA, durB );

Will result on my system in:

324 / 946

As others have pointed out: The main difference in speed would be because of the usage of sqrt() which is needed to return the distance. The comparison in Ellipse2D don't need to return the distance and can use a faster method.

So the second method is faster. Note that this are 1,000,000,000 runs. So in reality this difference would hardly be noticeable. And of cause this is way no "real" benchmark. There are many effects which can lead to noticeable different results.

Answer 2

The best way is definitely the one where you don't have to take the square root in order to apply Pythagoras. This means that you don't test:

distance <= radius

But instead, you do:

distance^2 <= radius^2

Here is a method that does that:

/**
 * @param x  The x coordinate of the point to test.
 * @param y  The y coordinate of the point to test.
 * @param cX The x coordinate of the center of the circle.
 * @param cY The y coordinate of the center of the circle.
 * @param r  The radius of the circle.
 */
public static boolean liesInCircle(double x, double y, double cX, double cY, double r)
{
   double dx = x - cX;
   double dy = y - cY;
   return dx * dx + dy * dy <= r * r;
} 

Answer 3

the faster method is actually

double dx = x1-x;
double dy = y1-y;
if(dx*dx+dy*dy< Diam*Diam/4)

As it will avoid having to do the sqrt() in the first method, and is more optimized for a circle than the second method. Additionally, you avoid having to create objects that you aren't going to use again.

Answer 4

Looking at the source code it looks like the Point method uses the standard distance function:

sqrt((x1 - x2)^2 + (y1 - y2)^2)

The Ellipse method uses some approximation of the Pythagorean theorem:

((x - Cx) / (Dx - 0.5))^2 + ((y - Cy) / (Dy - 0.5))^2 < 0.25

As already pointed out, the Ellipse method should be faster since it does not have to use the square root.