[Boost-commit] svn:boost r76859 - in trunk/boost/geometry: algorithms algorithms/detail/overlay policies/relate

Subject: [Boost-commit] svn:boost r76859 - in trunk/boost/geometry: algorithms algorithms/detail/overlay policies/relate
From: barend.gehrels_at_[hidden]
Date: 2012-02-03 16:14:14

Author: barendgehrels
Date: 2012-02-03 16:14:13 EST (Fri, 03 Feb 2012)
New Revision: 76859
URL: http://svn.boost.org/trac/boost/changeset/76859

Log:
Fixed wrong behaviour for intersects/disjoint algorithms for pair of linestrings which were degenerate, or collinear, or one starting in the middle from the other.
Also removed the never-used parallel option.
Throws an error at unexpected input (robustness errors)
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp |     3 +                                       
   trunk/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp             |    78 ++++++++++++++++++++++++++++++++++----- 
   trunk/boost/geometry/algorithms/disjoint.hpp                                 |    21 +++++++++-                              
   trunk/boost/geometry/policies/relate/de9im.hpp                               |     8 ----                                    
   trunk/boost/geometry/policies/relate/direction.hpp                           |    16 ++++----                                
   trunk/boost/geometry/policies/relate/intersection_points.hpp                 |     5 --                                      
   trunk/boost/geometry/policies/relate/tupled.hpp                              |     9 ----                                    
   7 files changed, 97 insertions(+), 43 deletions(-)

Modified: trunk/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/calculate_distance_policy.hpp	2012-02-03 16:14:13 EST (Fri, 03 Feb 2012)
@@ -30,6 +30,9 @@
  */
 struct calculate_distance_policy
 {
+    static bool const include_no_turn = false;
+    static bool const include_degenerate = false;
+
     template <typename Point1, typename Point2, typename Info>
     static inline void apply(Info& info, Point1 const& p1, Point2 const& p2)
     {

Modified: trunk/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp	2012-02-03 16:14:13 EST (Fri, 03 Feb 2012)
@@ -23,6 +23,25 @@
 namespace boost { namespace geometry
 {
 
+#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
+class turn_info_exception : public geometry::exception
+{
+    std::string message;
+public:
+
+    // NOTE: "char" will be replaced by enum in future version
+    inline turn_info_exception(char const method) 
+    {
+        message = "Boost.Geometry Turn exception: ";
+        message += method;
+    }
+
+    virtual char const* what() const throw()
+    {
+        return message.c_str();
+    }
+};
+#endif
 
 #ifndef DOXYGEN_NO_DETAIL
 namespace detail { namespace overlay
@@ -677,6 +696,18 @@
     }
 };
 
+template<typename TurnInfo>
+struct only_convert
+{
+    template<typename IntersectionInfo>
+    static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info)
+    {
+        ti.method = method_collinear;
+        geometry::convert(intersection_info.intersections[0], ti.point);
+        ti.operations[0].operation = operation_continue;
+        ti.operations[1].operation = operation_continue;
+    }
+};
 
 /*!
 \brief Policy doing nothing
@@ -686,6 +717,9 @@
  */
 struct assign_null_policy
 {
+    static bool const include_no_turn = false;
+    static bool const include_degenerate = false;
+
     template <typename Point1, typename Point2, typename Info>
     static inline void apply(Info& , Point1 const& , Point2 const& )
     {}
@@ -703,14 +737,16 @@
     \tparam TurnInfo type of class getting intersection and turn info
     \tparam AssignPolicy policy to assign extra info,
         e.g. to calculate distance from segment's first points
-        to intersection points
+        to intersection points.
+        It also defines if a certain class of points
+        (degenerate, non-turns) should be included.
  */
 template
 <
     typename Point1,
     typename Point2,
     typename TurnInfo,
-    typename AssignPolicy = assign_null_policy
+    typename AssignPolicy
 >
 struct get_turn_info
 {
@@ -749,10 +785,20 @@
         // Select method and apply
         switch(method)
         {
-            case 'a' :
-            case 'f' :
-            case 's' :
-            case 'd' :
+            case 'a' : // collinear, "at"
+            case 'f' : // collinear, "from"
+            case 's' : // starts from the middle
+                if (AssignPolicy::include_no_turn
+                    && result.template get<0>().count > 0)
+                {
+                    only_convert<TurnInfo>::apply(tp,
+                                result.template get<0>());
+                    AssignPolicy::apply(tp, pi, qi);
+                    *out++ = tp;
+                }
+                break;
+
+            case 'd' : // disjoint: never do anything
                 break;
 
             case 'm' :
@@ -873,13 +919,23 @@
             }
             break;
             case '0' :
-               // degenerate points
-               break;
+            {
+                // degenerate points
+                if (AssignPolicy::include_degenerate)
+                {
+                    only_convert<TurnInfo>::apply(tp, result.template get<0>());
+                    AssignPolicy::apply(tp, pi, qi);
+                    *out++ = tp;
+                }
+            }
+            break;
             default :
-#ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS
-                std::cout << "get_turns, nyi: " << method << std::endl;
+            {
+#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
+                throw turn_info_exception(method);
 #endif
-                break;
+            }
+            break;
         }
 
         return out;

Modified: trunk/boost/geometry/algorithms/disjoint.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/disjoint.hpp	(original)
+++ trunk/boost/geometry/algorithms/disjoint.hpp	2012-02-03 16:14:13 EST (Fri, 03 Feb 2012)
@@ -44,6 +44,19 @@
 namespace detail { namespace disjoint
 {
 
+struct assign_disjoint_policy
+{
+    // We want to include all points:
+    static bool const include_no_turn = true;
+    static bool const include_degenerate = true;
+
+    // We don't assign extra info:
+    template <typename Point1, typename Point2, typename Info>
+    static inline void apply(Info& , Point1 const& , Point2 const& )
+    {}
+};
+   
+
 template <typename Geometry1, typename Geometry2>
 struct disjoint_linear
 {
@@ -54,12 +67,14 @@
         typedef overlay::turn_info<point_type> turn_info;
         std::deque<turn_info> turns;
 
-        // Get (and stop on) any intersection
+        // Specify two policies:
+        // 1) Stop at any intersection
+        // 2) In assignment, include also degenerate points (which are normally skipped)
         disjoint_interrupt_policy policy;
         geometry::get_turns
             <
-                false, false,
-                overlay::assign_null_policy
+                false, false, 
+                assign_disjoint_policy
             >(geometry1, geometry2, turns, policy);
         if (policy.has_intersections)
         {

Modified: trunk/boost/geometry/policies/relate/de9im.hpp
==============================================================================
--- trunk/boost/geometry/policies/relate/de9im.hpp	(original)
+++ trunk/boost/geometry/policies/relate/de9im.hpp	2012-02-03 16:14:13 EST (Fri, 03 Feb 2012)
@@ -167,14 +167,6 @@
                 true);
     }
 
-
-    static inline return_type parallel()
-    {
-        return de9im_segment(0,0,
-                -1, -1, 1,
-                -1, -1, 0,
-                 1,  0, 2, false, false, true);
-    }
 };
 
 

Modified: trunk/boost/geometry/policies/relate/direction.hpp
==============================================================================
--- trunk/boost/geometry/policies/relate/direction.hpp	(original)
+++ trunk/boost/geometry/policies/relate/direction.hpp	2012-02-03 16:14:13 EST (Fri, 03 Feb 2012)
@@ -32,6 +32,8 @@
 
 struct direction_type
 {
+    // NOTE: "char" will be replaced by enum in future version
+
     inline direction_type(side_info const& s, char h,
                 int ha, int hb,
                 int da = 0, int db = 0,
@@ -61,6 +63,8 @@
     }
 
 
+    // TODO: replace this
+    // NOTE: "char" will be replaced by enum in future version
     // "How" is the intersection formed?
     char how;
 
@@ -236,16 +240,12 @@
         return return_type('d', false);
     }
 
-
-    static inline return_type parallel()
-    {
-        return return_type('p', false);
-    }
-
     static inline return_type error(std::string const&)
     {
-        // msg
-        return return_type('d', false);
+        // Return "E" to denote error
+        // This will throw an error in get_turn_info
+        // TODO: change to enum or similar
+        return return_type('E', false);
     }
 
 private :

Modified: trunk/boost/geometry/policies/relate/intersection_points.hpp
==============================================================================
--- trunk/boost/geometry/policies/relate/intersection_points.hpp	(original)
+++ trunk/boost/geometry/policies/relate/intersection_points.hpp	2012-02-03 16:14:13 EST (Fri, 03 Feb 2012)
@@ -169,10 +169,7 @@
     {
         return return_type();
     }
-    static inline return_type parallel()
-    {
-        return return_type();
-    }
+
     static inline return_type degenerate(S1 const& s, bool)
     {
         return_type result;

Modified: trunk/boost/geometry/policies/relate/tupled.hpp
==============================================================================
--- trunk/boost/geometry/policies/relate/tupled.hpp	(original)
+++ trunk/boost/geometry/policies/relate/tupled.hpp	2012-02-03 16:14:13 EST (Fri, 03 Feb 2012)
@@ -164,15 +164,6 @@
             );
     }
 
-
-    static inline return_type parallel()
-    {
-        return boost::make_tuple
-            (
-                Policy1::parallel(),
-                Policy2::parallel()
-            );
-    }
 };
 
 }} // namespace policies::relate