Boost logo

Boost :

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;
   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);
   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....


Boost list run by bdawes at, gregod at, cpdaniel at, john at