[boost] operator< for points (geometry classes)

From: Aleksey Gurtovoy (alexy_at_[hidden])
Date: 2000-01-09 03:29:57

I've just realized that current implementation of 'operator<' for 'point'
and 'delta' classes, i.e.

template<class T1, class T2>
bool operator <( const point<T1, T2>& p1,   const point<T1, T2>& p2 ) {
  return p1.x() < p2.x() && p1.y() < p2.y();
  }

doesn't conform to requirements of std associative containers for a keys'
ordering relation, and also to sorting algorithms' requirements for
operator<. The ordering relation (or operator<)  must to induce a strict
weak ordering on the values, and the above version of operator< fails to
meet this requirement. From the standard (section 25.3 [lib.alg.sorting],
para 4):

... "If we define equiv(a, b) as !comp(a, b) && !comp(b, a), then the
requirements are that comp and equiv both be transitive relations:
- comp(a, b) && comp(b, c) implies comp(a, c)
-equiv(a, b) && equiv(b, c) implies equiv(a, c)"

The first assertion is true for the point::operator <, but the second one is
not. E.g. if
a = point( 10, 15 ),
b = point( 15, 5 ) and
c = point( 5,  10 )
then equiv( a, b ) == true, equiv( b, c ) == true, but equiv(a, c) ==
false!!!

This is because in fact the current implementation of operator < allows the
following assertion to be true:
assert( !( p1 < p2) && !( p2 < p1 ) && !( p1 == p2 ) );

This is clearly a problem, and probably we must change definition of the
points and deltas ordering, but...
the current version is very simple and understandable - a point p1 is less
than another point p2 if and only if it is located inside a rectangle
(0,0) - (p2.x, p2.y). If we change this definition to any other one which
really induces a strict weak ordering on the points, we probably will have
much more unclear definition. For example this implementation:

template<class T1, class T2>
bool operator <( const point<T1, T2>& p1,   const point<T1, T2>& p2 ) {
  return p1.x() < p2.x() || ( p1.x() == p2.x() && p1.y() < p2.y() );
  }

do induce a strict weak ordering on the points, but does it have a much
sense besides a fact that it give us a correct behavior of sorting
algorithms and some of std containers? I'm not sure.

So my question - do we need to change the definition of operator> for point
and delta classes, or we want to introduce a special comparison function for
situations I've described above?
Your thoughts?

-Alexy