# 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

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.