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

Subject: [Boost-commit] svn:boost r73414 - in trunk: boost/geometry/algorithms/detail/overlay libs/geometry/test/algorithms
From: barend.gehrels_at_[hidden]
Date: 2011-07-28 16:57:47

Author: barendgehrels
Date: 2011-07-28 16:57:46 EDT (Thu, 28 Jul 2011)
New Revision: 73414
URL: http://svn.boost.org/trac/boost/changeset/73414

Log:
Fixed bug reported by Akira T on [Boost-users] at 27-7-2011 3:17
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp |    35 +++++++++++++++++++++++---              
   trunk/libs/geometry/test/algorithms/intersects.cpp           |    51 ++++++++++++++++++++++++++++++++++++++++
   2 files changed, 81 insertions(+), 5 deletions(-)

Modified: trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/get_turns.hpp	2011-07-28 16:57:46 EDT (Thu, 28 Jul 2011)
@@ -127,6 +127,34 @@
         >::type range2_iterator;
 
 
+    template <typename Geometry, typename Section>
+    static inline bool neighbouring(Section const& section,
+            int index1, int index2)
+    {
+        // About n-2:
+        //   (square: range_count=5, indices 0,1,2,3
+        //    -> 0-3 are adjacent, don't check on intersections)
+        // Also tested for open polygons, and/or duplicates
+        // About first condition: will be optimized by compiler (static)
+        // It checks if it is areal (box,ring,(multi)polygon
+        int const n = int(section.range_count);
+        return boost::is_same
+                    <
+                        typename tag_cast
+                            <
+                                typename geometry::point_type<Geometry1>::type, 
+                                areal_tag
+                            >::type, 
+                        areal_tag
+                    >::value
+               && 
+                (
+                    (index2 == 0 && index1 >= n - 2)
+                    || (index1 == 0 && index2 >= n - 2)
+                )
+                ;
+    }
+
 
 public :
     // Returns true if terminated, false if interrupted
@@ -196,7 +224,7 @@
                 if (skip)
                 {
                     // If sources are the same (possibly self-intersecting):
-                    // skip if it is a neighbouring sement.
+                    // skip if it is a neighbouring segment.
                     // (including first-last segment
                     //  and two segments with one or more degenerate/duplicate
                     //  (zero-length) segments in between)
@@ -204,12 +232,9 @@
                     // Also skip if index1 < index2 to avoid getting all
                     // intersections twice (only do this on same source!)
 
-                    // About n-2:
-                    //   (square: range_count=5, indices 0,1,2,3
-                    //    -> 0-3 are adjacent)
                     skip = index2 >= index1
                         || ndi1 == ndi2 + 1
-                        || (index2 == 0 && index1 >= int(sec1.range_count) - 2)
+                        || neighbouring<Geometry1>(sec1, index1, index2)
                         ;
                 }
 

Modified: trunk/libs/geometry/test/algorithms/intersects.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/intersects.cpp	(original)
+++ trunk/libs/geometry/test/algorithms/intersects.cpp	2011-07-28 16:57:46 EDT (Thu, 28 Jul 2011)
@@ -58,6 +58,57 @@
     // Hole: two intersecting holes
     test_self_intersects<polygon>(
         "POLYGON((0 0,0 4,4 4,4 0,0 0),(1 1,1 3,3 3,3 1,1 1),(2 2,2 3.5,3.5 3.5,3.5 2,2 2))", true);
+
+    // Mail Akiro T on [Boost-users] at 27-7-2011 3:17:
+    test_self_intersects<bg::model::linestring<P> >(
+        "LINESTRING(0 0,0 4,4 4,2 2,2 5)", true);
+
+    test_self_intersects<bg::model::linestring<P> >(
+        "LINESTRING(0 4,4 4,2 2,2 5)", true);
+
+    // Test self-intersections at last segment in close/open rings:
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,3 3,4 1,0 0))", false);
+
+    test_self_intersects<bg::model::ring<P, true, false> >(
+        "POLYGON((0 0,3 3,4 1))", false);
+
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,3 3,4 1,0 1,0 0))", true);
+
+    test_self_intersects<bg::model::ring<P, true, false> >(
+        "POLYGON((0 0,3 3,4 1,0 1))", true);
+
+    // Duplicates in first or last
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,3 3,4 1,0 1,0 1,0 0))", true);
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,3 3,4 1,0 1,0 0,0 0))", true);
+    test_self_intersects<bg::model::ring<P, true, false> >(
+        "POLYGON((0 0,3 3,4 1,0 1,0 1))", true);
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,0 0,3 3,4 1,0 1,0 1,0 0))", true);
+    test_self_intersects<bg::model::ring<P, true, false> >(
+        "POLYGON((0 0,0 0,3 3,4 1,0 1,0 1))", true);
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,3 3,3 3,4 1,0 1,0 1,0 0))", true);
+    test_self_intersects<bg::model::ring<P, true, false> >(
+        "POLYGON((0 0,3 3,3 3,4 1,0 1,0 1))", true);
+
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,3 3,4 1,0 0,0 0))", false);
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,3 3,4 1,4 1,0 0))", false);
+    test_self_intersects<bg::model::ring<P, true, false> >(
+        "POLYGON((0 0,3 3,4 1,4 1))", false);
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,0 0,3 3,4 1,0 0))", false);
+    test_self_intersects<bg::model::ring<P, true, false> >(
+        "POLYGON((0 0,0 0,3 3,4 1))", false);
+    test_self_intersects<bg::model::ring<P> >(
+        "POLYGON((0 0,3 3,3 3,4 1,0 0))", false);
+    test_self_intersects<bg::model::ring<P, true, false> >(
+        "POLYGON((0 0,3 3,3 3,4 1))", false);
 }