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

From: Barend Gehrels (barend_at_[hidden])
Date: 2008-03-27 15:30:19

> 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); }
> };
>   
Hi Phil,

Thanks for this.

I did all "distance strategies" let return the same type. The "simplify" 
algorithm, for example, uses this to compare distances without taking 
the square. This works both for latlong and for xy-points, and will work 
for other points. This is the reason for this design. The difference 
with your approach, until here, is not so large.

> 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; }
>   
Good idea.
> 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....
>   
It is an interesting alternative. Somewhat directed to the xy-case.

Searching the nearest (or farrest) can be done like this, but also with 
the "distance_result" variant. In fact I do that in the simplify 
routine. There I also avoid the square, and therefore I introduced the 
"squared()" requirement in the concept of the distance strategy. This 
"squared()" can be avoided, because the tolerance can be squared at 
comparison, but then it has to be squared each time... or the previous 
choice has to be rememberd (not so good).

Besides this "distance_result" (another name is also OK if that is the 
problem, or maybe I shouldn't have derived it from std::pair) I also 
have an "intersection_result" somewhere.

Barend Gehrels
Geodan, Amsterdam

> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>
>
>
>