Redundant Math.sqrt when comparing distances

[Michael Ellis]

I've been looking through the ImageJ source code and noticed several  
places where rectilinear distances are being compared. Here's once  
example from the PolygonROI. Isn't the Math.sqrt() redundant since  
only the nearest point is being sought and not the actual distance?

        int getClosestPoint(int x, int y, Polygon points) {
                int index = 0;
                double distance = Double.MAX_VALUE;
                for (int i=0; i<points.npoints; i++) {
                        double dx = points.xpoints[i] - x;
                        double dy = points.ypoints[i] - y;
                        double distance2 = Math.sqrt(dx*dx+dy*dy);
                        if (distance2<distance) {
                                distance = distance2;
                                index = i;
                        }
                }
                return index;
        }

Wouldn't deleting the Math.sqrt() just improve performance? Or am I  
missing something?


Michael Ellis
Managing Director
Digital Scientific UK Ltd.
http://www.digitalscientific.co.uk
[hidden email]
tel: [phone]
fax: [phone]

Sheraton House
Castle Park
Cambridge
CB3 0AX


The contents of this e-mail may be privileged and are confidential.  
It may not be disclosed to or used by anyone other than the  
addressee(s), nor copied in any way.  If received in error, please  
advise the sender and delete it from your system.

[Joachim Wesner]

Hi, I think you are totally right, if you are not interested in the actual
distance it is OK to compare and keep the sum of squares.

Even in that case, you could put the Math.sqrt at the end outside the loop.

If have a related case where I need to scan x- and y-coordinates in two
nested loops and find what´s inside a
inner circle or related. If it turns out that, say dy^2 is already outside,
it will skip the inner x-loop to optimize
performance.

Mit freundlichen Grüßen / Best regards

Joachim Wesner

Leica Microsystems CMS GmbH | GmbH mit Sitz in Wetzlar | Amtsgericht
Wetzlar  HRB 2432
Geschäftsführer:  Dr. Stefan Traeger | Dr. David Roy Martyr | Colin Davis
www.leica-microsystems.com



                                                                           
             Michael Ellis                                                
             <michael.ellis@DI                                            
             GITALSCIENTIFIC.C                                          An
             O.UK>                      [hidden email]                
             Gesendet von:                                           Kopie
             ImageJ Interest                                              
             Group                                                   Thema
             <[hidden email].          Redundant Math.sqrt when comparing
             GOV>                       distances                          
                                                                           
                                                                           
             20.05.2010 12:14                                              
                                                                           
                                                                           
              Bitte antworten                                              
                    an                                                    
              ImageJ Interest                                              
                   Group                                                  
             <[hidden email].                                            
                   GOV>                                                    
                                                                           
                                                                           




I've been looking through the ImageJ source code and noticed several
places where rectilinear distances are being compared. Here's once
example from the PolygonROI. Isn't the Math.sqrt() redundant since
only the nearest point is being sought and not the actual distance?

             int getClosestPoint(int x, int y, Polygon points) {
                         int index = 0;
                         double distance = Double.MAX_VALUE;
                         for (int i=0; i<points.npoints; i++) {
                                     double dx = points.xpoints[i] - x;
                                     double dy = points.ypoints[i] - y;
                                     double distance2 =
Math.sqrt(dx*dx+dy*dy);
                                     if (distance2<distance) {
                                                 distance = distance2;
                                                 index = i;
                                     }
                         }
                         return index;
             }

Wouldn't deleting the Math.sqrt() just improve performance? Or am I
missing something?


Michael Ellis
Managing Director
Digital Scientific UK Ltd.
http://www.digitalscientific.co.uk
[hidden email]
tel: [phone]
fax: [phone]

Sheraton House
Castle Park
Cambridge
CB3 0AX


The contents of this e-mail may be privileged and are confidential.
It may not be disclosed to or used by anyone other than the
addressee(s), nor copied in any way.  If received in error, please
advise the sender and delete it from your system.



______________________________________________________________________
This email has been scanned by the MessageLabs Email Security System.
For more information please visit http://www.messagelabs.com/email 
______________________________________________________________________