[Boost-commit] svn:boost r76978 - in trunk: boost/geometry/algorithms/detail/overlay libs/geometry/test/multi/algorithms

Subject: [Boost-commit] svn:boost r76978 - in trunk: boost/geometry/algorithms/detail/overlay libs/geometry/test/multi/algorithms
From: barend.gehrels_at_[hidden]
Date: 2012-02-11 12:10:18

Author: barendgehrels
Date: 2012-02-11 12:10:17 EST (Sat, 11 Feb 2012)
New Revision: 76978
URL: http://svn.boost.org/trac/boost/changeset/76978

Log:
Boost.Geometry line/poly overlay (new for 1.49), bugfix (avoid degenerate lines with only one point, and sub-sort on operation in case of duplicate intersection points). Including unit test update.
Note, this also fixes two earlier unit tests with degenerate outputs.
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/follow.hpp      |    42 +++++++++++++++++++++++++++++++++++---- 
   trunk/libs/geometry/test/multi/algorithms/multi_difference.cpp |    12 +++++++++-                              
   2 files changed, 47 insertions(+), 7 deletions(-)

Modified: trunk/boost/geometry/algorithms/detail/overlay/follow.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/follow.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/follow.hpp	2012-02-11 12:10:17 EST (Sat, 11 Feb 2012)
@@ -182,11 +182,11 @@
         // and add the output piece
         geometry::copy_segments<false>(linestring, segment_id, index, current_piece);
         detail::overlay::append_no_duplicates(current_piece, point);
-        if (! current_piece.empty())
+        if (current_piece.size() > 1)
         {
             *out++ = current_piece;
-            current_piece.clear();
         }
+        current_piece.clear();
     }
 
     static inline bool is_entered(bool entered)
@@ -277,14 +277,46 @@
     template<typename Turn>
     struct sort_on_segment
     {
+        // In case of turn point at the same location, we want to have continue/blocked LAST
+        // because that should be followed (intersection) or skipped (difference).
+        // By chance the enumeration is ordered like that but we keep the safe way here.
+        inline int operation_order(Turn const& turn) const
+        {
+            operation_type const& operation = turn.operations[0].operation;
+            switch(operation)
+            {
+                case operation_none : return 0;
+                case operation_union : return 1;
+                case operation_intersection : return 2;
+                case operation_blocked : return 3;
+                case operation_continue : return 4;
+            }
+            return -1;
+        };
+
+        inline bool use_operation(Turn const& left, Turn const& right) const
+        {
+            // If they are the same, OK. 
+            return operation_order(left) < operation_order(right);
+        }
+
+        inline bool use_distance(Turn const& left, Turn const& right) const
+        {
+            return geometry::math::equals(left.operations[0].enriched.distance, right.operations[0].enriched.distance)
+                ? use_operation(left, right)
+                : left.operations[0].enriched.distance < right.operations[0].enriched.distance
+                ;
+        }
+
         inline bool operator()(Turn const& left, Turn const& right) const
         {
             segment_identifier const& sl = left.operations[0].seg_id;
             segment_identifier const& sr = right.operations[0].seg_id;
 
             return sl == sr
-                ? left.operations[0].enriched.distance < right.operations[0].enriched.distance
-                : sl < sr;
+                ? use_distance(left, right)
+                : sl < sr
+                ;
 
         }
     };
@@ -364,7 +396,7 @@
         }
 
         // Output the last one, if applicable
-        if (! current_piece.empty())
+        if (current_piece.size() > 1)
         {
             *out++ = current_piece;
         }

Modified: trunk/libs/geometry/test/multi/algorithms/multi_difference.cpp
==============================================================================
--- trunk/libs/geometry/test/multi/algorithms/multi_difference.cpp	(original)
+++ trunk/libs/geometry/test/multi/algorithms/multi_difference.cpp	2012-02-11 12:10:17 EST (Sat, 11 Feb 2012)
@@ -151,10 +151,18 @@
     typedef typename bg::point_type<Polygon>::type Point;
     typedef bg::model::ring<Point> Ring;
 
-    test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_1", "LINESTRING(2 0,2 5)", case_multi_simplex[0], 3, 5, 1.30);
+    test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_1", "LINESTRING(2 0,2 5)", case_multi_simplex[0], 2, 4, 1.30);
     test_one_lp<LineString, MultiLineString, Polygon>("case_p_mls_1", "MULTILINESTRING((2 0,2 5),(3 0,3 5))", case_single_simplex, 3, 6, 2.5);
-    test_one_lp<LineString, MultiLineString, MultiPolygon>("case_mp_mls_1", "MULTILINESTRING((2 0,2 5),(3 0,3 5))", case_multi_simplex[0], 6, 11, 3.1666667);
+    test_one_lp<LineString, MultiLineString, MultiPolygon>("case_mp_mls_1", "MULTILINESTRING((2 0,2 5),(3 0,3 5))", case_multi_simplex[0], 5, 10, 3.1666667);
     test_one_lp<LineString, MultiLineString, Ring>("case_r_mls_1", "MULTILINESTRING((2 0,2 5),(3 0,3 5))", case_single_simplex, 3, 6, 2.5);
+
+    // Collinear cases, with multiple turn points at the same location
+    test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_2a", "LINESTRING(1 0,1 1,2 1,2 0)", "MULTIPOLYGON(((0 0,0 1,1 1,1 0,0 0)),((1 1,1 2,2 2,2 1,1 1)))", 1, 2, 1.0);
+    test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_2b", "LINESTRING(1 0,1 1,2 1,2 0)", "MULTIPOLYGON(((1 1,1 2,2 2,2 1,1 1)),((0 0,0 1,1 1,1 0,0 0)))", 1, 2, 1.0);
+
+    test_one_lp<LineString, LineString, MultiPolygon>("case_mp_ls_3", 
+            "LINESTRING(6 6,6 7,7 7,7 6,8 6,8 7,9 7,9 6)", 
+            "MULTIPOLYGON(((5 7,5 8,6 8,6 7,5 7)),((6 6,6 7,7 7,7 6,6 6)),((8 8,9 8,9 7,8 7,7 7,7 8,8 8)))", 2, 5, 3.0);
 }