I *just* came across this (look for PhiLo's comment at the bottom)

It depends on your needs. My remark is still valid, but if you need a real distance computation, dist() algorithm is still needed. But in general, you improve speed by reducing the number of computations you need. For example with quad trees, to avoid comparing points that you know they are distant enough.

If you want to compare two distances to see if circles intersect, you can simply just remove the square root function.

The dist() function is within two for loops that span the width and height of the processing sketch and within those two for loops , it is with a for loop that loops three (3) times.

You can imagine when you get a screen bigger than 200x200 and the dist() is executed three times each pixel. This affects frameRate.

I will try

 sq(A.x + B.x) + sq(A.y + B.y) <= sq(A.radius + B.radius) 

and see if that helps the framerate.


Basically I want a function that is faster than dist but still as accurate.

If you can do with a bit less accuracy you can also try using something like the Newton method to find the square root... I've implemented such an approach in my fvlib library and it's faster than the dist() or Java's Math.sqrt(). And depending on the number of Newton iterations you can also tune your accuracy.. 

Could you show the code, maybe there is another way to optimize it.

Here is an excerpt of the awesome piece of code from harukit

1. void loopx(){
     for(int i=0;i<pNum;i++){
       p[i].update();
     }
     for(int y=0;y<height;y++){
       for(int x=0;x<width;x++){
           int pos=y*width+x;
           color col = pixels[pos];
           rr = col >> 16 & 0xff;
           gg = col >> 8 & 0xff;
           bb = col  & 0xff;
           for(int i=0;i<pNum;i++){
             dis =dist(p[i].xpos,p[i].ypos,x,y)/2;
             rr += cc[0]/dis-gain;
             gg += cc[1]/dis-gain;
             bb += cc[2]/dis-gain;
           }
           pixels[pos]=color(rr,gg,bb);
       }
     }
   }

I can post the entire code if you like but above is the main procedure loopx() as you can see highlighted in red is the dis variable which is set by the dist() function but it affects the framerate when the sketch size increases. The dist() function is execute three time for every pixel on screen.

I would like a better function that does not require square root.

If you need the entire applet I can post it.

And since 1/dis is a radial function and hence symmetric, you could even save more, because (assume that p.x = p.y = 0, otherwise you do a translation):

Take a look at this article.  It says it can generally approximate the distance within 2.5% average error, and with about a 5% maximum error with a small number of linear components and is therefore very fast to run.

http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml

Here is a quick implementation, would love it if someone could covert it to 3d. (Also not sure how to convert to float, since it uses "<<", which I'm unfamiliar with.)

1. int fastDist( int dx, int dy )
2. {
3.    int min, max, approx;
4.    if ( dx < 0 ) dx = -dx;
5.    if ( dy < 0 ) dy = -dy;
6.    if ( dx < dy )
7.    {
8.       min = dx;
9.       max = dy;
10.    } else {
11.       min = dy;
12.       max = dx;
13.    }
14.    approx = ( max * 1007 ) + ( min * 441 );
15.    if ( max < ( min << 4 ))
16.       approx -= ( max * 40 );
17.    // add 512 for proper rounding
18.    return (( approx + 512 ) >> 10 );
19. }

Thanks!

This is indeed faster than dist()

It can be even faster if you calculate it in 2D.

It doesn't compute a dist, the name is a bit misleading. This function is OK to compare distances, though.

It saves about 10 frames per second at 255x255 and even more when you reduce the height which is great in my book.