Re: [boost] Preview 2 of a template Geometry Library

From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2008-03-26 19:31:37

Hi Barend,

I see that your distance functions now return a (double,bool) pair, 
with the bool indicating whether the double is the actual distance or 
the square of the distance.  This does solve the problem of avoiding 
expensive sqrt()s, but it doesn't look very appealing.  How about this instead:

double greatcircle_distance(point a, point b) {
   // return the actual distance
   return some-tirgonometry(a,b);
}

squared<double> pythag_distance(point a, point b) {
   // return the squared distance, to avoid the sqrt() when it's not needed:
   double dx = a.x-b.x;
   double dy = a.y-b.y;
   return squared<double>(dx*dx + dy*dy);
}

where squared<double> is convertible to double:

template<typename T>
class squared {
   T sq;
public:
   explicit squared(T sq_): sq(sq_) {}
   operator T() { return sqrt(sq); }
};

so if I write
   double d = pythag_distance(p1,p2);
I get the actual distance, with the sqrt() done in the conversion from 
squared<double> to double.

Then, if I want to be efficient in code like this:

   if (pythag_distance(p1,p2) > pythag_distance(p3,p4)) { ... }

I just need to define operator> on squared<T>, and the comparison is 
done without the expensive sqrt():

   bool operator>(squared other) { return sq > other.sq; }

You can go further.  If I'm searching through a long list of points to 
find the closest to P then I'll avoid the squaring (and conversion to 
double if my co-ordinates are integers) whenever possible.  You can 
achieve this with a more complex distance proxy:

class distance_proxy {
   double dx;
   double dy;
   distance_proxy(double dx_, double dy_): dx(dx_), dy(dy_) {}
   friend pythag_distance(point,point);
public:
   operator double() { return sqrt(dx*dx+dy*dy); }
   bool operator>(double d) {
     return dx>d
         || dy>d
         || (dx*dx+dy*dy > d*d);
   }
};

So this is convertible to double, but can be compared to a distance 
without any need for sqrt() and only multiplication in some cases.  
Further refinement is possible.

I hope this is interesting, and invite readers to find the no-doubt 
numerous errors in my code....

Phil.