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

Subject: [Boost-commit] svn:boost r86579 - in trunk: boost/geometry/algorithms libs/geometry/doc libs/geometry/test/algorithms libs/geometry/test/algorithms/overlay
From: barend.gehrels_at_[hidden]
Date: 2013-11-06 17:42:02

Author: barendgehrels
Date: 2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)
New Revision: 86579
URL: http://svn.boost.org/trac/boost/changeset/86579

Log:
[geometry] fixed ticket 8310, disjoint did give the wrong results. Fixed using point_on_surface. Added unit test. Also tests for overlay algorithms because they might suffer from the same problem

Text files modified: 
   trunk/boost/geometry/algorithms/disjoint.hpp                  |    56 +++++++++++++-------------------------- 
   trunk/boost/geometry/algorithms/touches.hpp                   |    39 ++++++++++++++++++++++++++-             
   trunk/libs/geometry/doc/release_notes.qbk                     |     2 +                                       
   trunk/libs/geometry/test/algorithms/difference.cpp            |    15 ++++++++++                              
   trunk/libs/geometry/test/algorithms/disjoint.cpp              |     6 ++++                                    
   trunk/libs/geometry/test/algorithms/intersection.cpp          |     7 +++++                                   
   trunk/libs/geometry/test/algorithms/overlay/overlay_cases.hpp |    20 ++++++++++----                          
   trunk/libs/geometry/test/algorithms/point_on_surface.cpp      |     5 ++-                                     
   trunk/libs/geometry/test/algorithms/union.cpp                 |     7 +++++                                   
   9 files changed, 110 insertions(+), 47 deletions(-)

Modified: trunk/boost/geometry/algorithms/disjoint.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/disjoint.hpp	Wed Nov  6 17:02:18 2013	(r86578)
+++ trunk/boost/geometry/algorithms/disjoint.hpp	2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)	(r86579)
@@ -31,9 +31,8 @@
 #include <boost/geometry/core/reverse_dispatch.hpp>
 
 #include <boost/geometry/algorithms/detail/disjoint.hpp>
-#include <boost/geometry/algorithms/detail/for_each_range.hpp>
-#include <boost/geometry/algorithms/detail/point_on_border.hpp>
 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
+#include <boost/geometry/algorithms/point_on_surface.hpp>
 #include <boost/geometry/algorithms/within.hpp>
 
 #include <boost/geometry/geometries/concepts/check.hpp>
@@ -49,39 +48,6 @@
 namespace detail { namespace disjoint
 {
 
-template<typename Geometry>
-struct check_each_ring_for_within
-{
-    bool has_within;
-    Geometry const& m_geometry;
-
-    inline check_each_ring_for_within(Geometry const& g)
-        : has_within(false)
-        , m_geometry(g)
-    {}
-
-    template <typename Range>
-    inline void apply(Range const& range)
-    {
-        typename geometry::point_type<Range>::type p;
-        geometry::point_on_border(p, range);
-        if (geometry::within(p, m_geometry))
-        {
-            has_within = true;
-        }
-    }
-};
-
-template <typename FirstGeometry, typename SecondGeometry>
-inline bool rings_containing(FirstGeometry const& geometry1,
-                SecondGeometry const& geometry2)
-{
-    check_each_ring_for_within<FirstGeometry> checker(geometry1);
-    geometry::detail::for_each_range(geometry2, checker);
-    return checker.has_within;
-}
-
-
 struct assign_disjoint_policy
 {
     // We want to include all points:
@@ -166,8 +132,24 @@
 
         // If there is no intersection of segments, they might located
         // inside each other
-        if (rings_containing(geometry1, geometry2)
-            || rings_containing(geometry2, geometry1))
+
+        // We check that using a point on the surface, and see if that is inside
+        // the other geometry. And vice versa.
+
+        typedef typename geometry::point_type<Geometry1>::type point_type1;
+        typedef typename geometry::point_type<Geometry2>::type point_type2;
+
+        if (geometry::within
+                (
+                    geometry::return_point_on_surface(geometry1),
+                    geometry2
+                )
+            || geometry::within
+                (
+                    geometry::return_point_on_surface(geometry2),
+                    geometry1
+                )
+            )
         {
             return false;
         }

Modified: trunk/boost/geometry/algorithms/touches.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/touches.hpp	Wed Nov  6 17:02:18 2013	(r86578)
+++ trunk/boost/geometry/algorithms/touches.hpp	2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)	(r86579)
@@ -19,6 +19,7 @@
 #include <deque>
 
 #include <boost/geometry/geometries/concepts/check.hpp>
+#include <boost/geometry/algorithms/detail/for_each_range.hpp>
 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
 #include <boost/geometry/algorithms/disjoint.hpp>
@@ -83,6 +84,40 @@
     return has_touch;
 }
 
+template<typename Geometry>
+struct check_each_ring_for_within
+{
+    bool has_within;
+    Geometry const& m_geometry;
+
+    inline check_each_ring_for_within(Geometry const& g)
+        : has_within(false)
+        , m_geometry(g)
+    {}
+
+    template <typename Range>
+    inline void apply(Range const& range)
+    {
+        typename geometry::point_type<Range>::type p;
+        geometry::point_on_border(p, range);
+        if (geometry::within(p, m_geometry))
+        {
+            has_within = true;
+        }
+    }
+};
+
+
+template <typename FirstGeometry, typename SecondGeometry>
+inline bool rings_containing(FirstGeometry const& geometry1,
+                SecondGeometry const& geometry2)
+{
+    check_each_ring_for_within<FirstGeometry> checker(geometry1);
+    geometry::detail::for_each_range(geometry2, checker);
+    return checker.has_within;
+}
+
+
 }}
 #endif // DOXYGEN_NO_DETAIL
 
@@ -173,8 +208,8 @@
             >(geometry1, geometry2, turns, policy);
 
     return detail::touches::has_only_turns(turns)
-        && ! geometry::detail::disjoint::rings_containing(geometry1, geometry2)
-        && ! geometry::detail::disjoint::rings_containing(geometry2, geometry1)
+        && ! geometry::detail::touches::rings_containing(geometry1, geometry2)
+        && ! geometry::detail::touches::rings_containing(geometry2, geometry1)
         ;
 }
 

Modified: trunk/libs/geometry/doc/release_notes.qbk
==============================================================================
--- trunk/libs/geometry/doc/release_notes.qbk	Wed Nov  6 17:02:18 2013	(r86578)
+++ trunk/libs/geometry/doc/release_notes.qbk	2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)	(r86579)
@@ -20,11 +20,13 @@
 [*Additional functionality]
 
 * added remove_spikes, algorithm to remove spikes from a ring, polygon or multi_polygon.
+* added point_on_surface, generating a point lying on the surface (interior) of the polygon
 
 [*Solved tickets]
 
 * [@https://svn.boost.org/trac/boost/ticket/9245 9245] Check for process errors in make_qbk.py
 * [@https://svn.boost.org/trac/boost/ticket/9081 9081] Booleans create self-intersecting polygons from non-self-intersecting polygons
+* [@https://svn.boost.org/trac/boost/ticket/8310 8310] Wrong results with overlapping polygons (fixed using point_on_surface for disjoint)
 
 [/=================]
 [heading Boost 1.55]

Modified: trunk/libs/geometry/test/algorithms/difference.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/difference.cpp	Wed Nov  6 17:02:18 2013	(r86578)
+++ trunk/libs/geometry/test/algorithms/difference.cpp	2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)	(r86579)
@@ -321,6 +321,21 @@
     }
 #endif
 
+    // Ticket 8310, one should be completely subtracted from the other.
+    test_one<polygon, polygon, polygon>("ticket_8310a",
+        ticket_8310a[0], ticket_8310a[1],
+        1, 10, 10.11562724, 
+        0, 0, 0); 
+    test_one<polygon, polygon, polygon>("ticket_8310b",
+        ticket_8310b[0], ticket_8310b[1],
+        1, 10, 10.12655608,
+        0, 0, 0); 
+    test_one<polygon, polygon, polygon>("ticket_8310c",
+        ticket_8310c[0], ticket_8310c[1],
+        1, 10, 10.03103292,
+        0, 0, 0); 
+
+
     // Other combi's
     {
         test_one<polygon, polygon, ring>(

Modified: trunk/libs/geometry/test/algorithms/disjoint.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/disjoint.cpp	Wed Nov  6 17:02:18 2013	(r86578)
+++ trunk/libs/geometry/test/algorithms/disjoint.cpp	2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)	(r86579)
@@ -21,6 +21,8 @@
 
 #include <test_common/test_point.hpp>
 
+#include <algorithms/overlay/overlay_cases.hpp>
+
 #include <algorithms/test_relate.hpp>
 
 
@@ -66,6 +68,10 @@
     test_disjoint<ring, ring>("disjoint_simplex_rr", disjoint_simplex[0], disjoint_simplex[1], true);
     test_disjoint<polygon, ring>("disjoint_simplex_pr", disjoint_simplex[0], disjoint_simplex[1], true);
 
+    test_disjoint<polygon, polygon>("ticket_8310a", ticket_8310a[0], ticket_8310a[1], false);
+    test_disjoint<polygon, polygon>("ticket_8310b", ticket_8310b[0], ticket_8310b[1], false);
+    test_disjoint<polygon, polygon>("ticket_8310c", ticket_8310c[0], ticket_8310c[1], false);
+
     // Testing touch
     test_disjoint<polygon, polygon>("touch_simplex_pp", touch_simplex[0], touch_simplex[1], false);
 

Modified: trunk/libs/geometry/test/algorithms/intersection.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/intersection.cpp	Wed Nov  6 17:02:18 2013	(r86578)
+++ trunk/libs/geometry/test/algorithms/intersection.cpp	2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)	(r86579)
@@ -214,6 +214,13 @@
     test_one<Polygon, Polygon, Polygon>("ticket_8652", ticket_8652[0], ticket_8652[1],
                 1, 4, 0.0003, 0.00001);
 
+    test_one<Polygon, Polygon, Polygon>("ticket_8310a", ticket_8310a[0], ticket_8310a[1],
+                1, 5, 0.3843747, 0.00001);
+    test_one<Polygon, Polygon, Polygon>("ticket_8310b", ticket_8310b[0], ticket_8310b[1],
+                1, 5, 0.3734379, 0.00001);
+    test_one<Polygon, Polygon, Polygon>("ticket_8310c", ticket_8310c[0], ticket_8310c[1],
+                1, 5, 0.4689541, 0.00001);
+
     test_one<Polygon, Polygon, Polygon>("buffer_mp1", buffer_mp1[0], buffer_mp1[1],
                 1, 31, 2.271707796);
 

Modified: trunk/libs/geometry/test/algorithms/overlay/overlay_cases.hpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/overlay/overlay_cases.hpp	Wed Nov  6 17:02:18 2013	(r86578)
+++ trunk/libs/geometry/test/algorithms/overlay/overlay_cases.hpp	2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)	(r86579)
@@ -575,15 +575,23 @@
     "POLYGON((2.76143527 1.093332171 , 2.076887131 1.822299719 , 4.263789177 3.875944376 , 4.948337555 3.146976948 , 2.76143527 1.093332171))"
     };
 
-static std::string ticket_8180[2] =
+// Ticket 8310 https://svn.boost.org/trac/boost/ticket/8310
+// The problem was in disjoint, "point_on_border" on the smallest polygon
+// is not considered as "within" the other, though there are no further intersection points.
+static std::string ticket_8310a[2] =
     {
-    "POLYGON(( -2.559375047683716 -0.615625500679016, -2.559375047683716 0.384374797344208, 7.940625190734863 0.384374588727951, 7.940625190734863 -0.615625441074371 ))",
-    "POLYGON(( 1.000000000000000 0.384374707937241, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000, 0.000000000000000 0.384374737739563 ))"
+    "POLYGON(( -2.559375047683716 -0.615625500679016, -2.559375047683716 0.384374797344208, 7.940625190734863 0.384374588727951, 7.940625190734863 -0.615625441074371, -2.559375047683716 -0.615625500679016 ))",
+    "POLYGON(( 1.000000000000000 0.384374707937241, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000, 0.000000000000000 0.384374737739563, 1.000000000000000 0.384374707937241 ))"
     };
-static std::string ticket_8180b[2] =
+static std::string ticket_8310b[2] =
     {
-    "POLYGON(( -2.559375047683716 -0.615625500679016, -2.559375047683716 0.384374797344208, 7.940625190734863 0.384374588727951, 7.940625190734863 -0.615625441074371 ))",
-    "POLYGON(( 1 0.384374707937241, 1 1, 0 1, 0 0.384374737739563 ))"
+	"POLYGON(( -2.592187881469727 -0.626561701297760, -2.592187643051147 0.373438000679016, 7.907812595367432 0.373437851667404, 7.907812595367432 -0.626561224460602, -2.592187881469727 -0.626561701297760 ))",
+    "POLYGON(( 0.000000000000000 0.373437941074371, 1.000000000000000 0.373437792062759, 1.000000000000000 0.000000000000000, 0.000000000000000 0.000000000000000, 0.000000000000000 0.373437941074371 ))"
+    };
+static std::string ticket_8310c[2] =
+    {
+	"POLYGON(( 5.204249382019043 3.531043529510498, 5.204247951507568 2.531045675277710, -5.295750617980957 2.531046152114868, -5.295751094818115 3.531045913696289, 5.204249382019043 3.531043529510498 ))",
+    "POLYGON(( 1.000000000000000 2.531045913696289, 1.000000000000000 3.000000000000000, 2.000000000000000 3.000000000000000, 2.000000000000000 2.531045913696289, 1.000000000000000 2.531045913696289 ))"
     };
 
 static std::string ticket_8254[2] =

Modified: trunk/libs/geometry/test/algorithms/point_on_surface.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/point_on_surface.cpp	Wed Nov  6 17:02:18 2013	(r86578)
+++ trunk/libs/geometry/test/algorithms/point_on_surface.cpp	2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)	(r86579)
@@ -281,8 +281,9 @@
     test_geometry<polygon>("ticket_17", ticket_17[0],  0, 0);
     test_geometry<polygon>("ticket_5103", ticket_5103[0],  0, 0);
     test_geometry<polygon>("ticket_7462", ticket_7462[0],  0, 0);
-    test_geometry<polygon>("ticket_8180", ticket_8180[0],  0, 0);
-    test_geometry<polygon>("ticket_8180b", ticket_8180b[0],  0, 0);
+    test_geometry<polygon>("ticket_8310a", ticket_8310a[0],  0, 0);
+    test_geometry<polygon>("ticket_8310b", ticket_8310b[0],  0, 0);
+    test_geometry<polygon>("ticket_8310c", ticket_8310c[0],  0, 0);
     test_geometry<polygon>("ticket_8254", ticket_8254[0],  0, 0);
 }
 

Modified: trunk/libs/geometry/test/algorithms/union.cpp
==============================================================================
--- trunk/libs/geometry/test/algorithms/union.cpp	Wed Nov  6 17:02:18 2013	(r86578)
+++ trunk/libs/geometry/test/algorithms/union.cpp	2013-11-06 17:42:02 EST (Wed, 06 Nov 2013)	(r86579)
@@ -265,6 +265,13 @@
     test_one<Polygon, Polygon, Polygon>("ticket_5103", ticket_5103[0], ticket_5103[1],
                 1, 0, 25, 2515271327070.5);
 
+    test_one<Polygon, Polygon, Polygon>("ticket_8310a", ticket_8310a[0], ticket_8310a[1],
+            1, 0, 5, 10.5000019595);
+    test_one<Polygon, Polygon, Polygon>("ticket_8310b", ticket_8310b[0], ticket_8310b[1],
+            1, 0, 5, 10.5000019595);
+    test_one<Polygon, Polygon, Polygon>("ticket_8310c", ticket_8310c[0], ticket_8310c[1],
+            1, 0, 5, 10.5000019595);
+
     test_one<Polygon, Polygon, Polygon>("buffer_rt_a", buffer_rt_a[0], buffer_rt_a[1],
                 1, 0, 265, 19.280667);