[Boost-commit] svn:boost r76899 - trunk/boost/geometry/strategies/agnostic

Subject: [Boost-commit] svn:boost r76899 - trunk/boost/geometry/strategies/agnostic
From: barend.gehrels_at_[hidden]
Date: 2012-02-05 11:19:25

Author: barendgehrels
Date: 2012-02-05 11:19:23 EST (Sun, 05 Feb 2012)
New Revision: 76899
URL: http://svn.boost.org/trac/boost/changeset/76899

Log:
Fixed ticket #6019, when multiple points were on the left, the points below the point taken were popped out by the algorithm, because they were sorted from top to bottom. We therefore take the lower-left point such that there are no points below. This problem was not present at the right side but we now take there the upper right point.
Text files modified: 
   trunk/boost/geometry/strategies/agnostic/hull_graham_andrew.hpp |    15 +++++++++++----                         
   1 files changed, 11 insertions(+), 4 deletions(-)

Modified: trunk/boost/geometry/strategies/agnostic/hull_graham_andrew.hpp
==============================================================================
--- trunk/boost/geometry/strategies/agnostic/hull_graham_andrew.hpp	(original)
+++ trunk/boost/geometry/strategies/agnostic/hull_graham_andrew.hpp	2012-02-05 11:19:23 EST (Sun, 05 Feb 2012)
@@ -225,8 +225,15 @@
     {
         // First pass.
         // Get min/max (in most cases left / right) points
-        // This makes use of the geometry::less/greater predicates with the optional
-        // direction template parameter to indicate x direction
+        // This makes use of the geometry::less/greater predicates
+
+        // For the left boundary it is important that multiple points
+        // are sorted from bottom to top. Therefore the less predicate
+        // does not take the x-only template parameter (this fixes ticket #6019.
+        // For the right boundary it is not necessary (though also not harmful), 
+        // because points are sorted from bottom to top in a later stage.
+        // For symmetry and to get often more balanced lower/upper halves
+        // we keep it.
 
         typedef typename geometry::detail::range_type<InputGeometry>::type range_type;
 
@@ -239,8 +246,8 @@
             <
                 range_type,
                 range_iterator,
-                geometry::less<point_type, 0>,
-                geometry::greater<point_type, 0>
+                geometry::less<point_type>,
+                geometry::greater<point_type>
             > extremes;
         geometry::detail::for_each_range(geometry, extremes);