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

Subject: [Boost-commit] svn:boost r75682 - in trunk/boost/geometry: algorithms/detail/overlay multi/algorithms
From: barend.gehrels_at_[hidden]
Date: 2011-11-27 05:23:08

Author: barendgehrels
Date: 2011-11-27 05:23:05 EST (Sun, 27 Nov 2011)
New Revision: 75682
URL: http://svn.boost.org/trac/boost/changeset/75682

Log:
Linestring/polygon overlay, phase 8 (difference)
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/follow.hpp              |   115 +++++++++++++++++++++++++++++++++------ 
   trunk/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp |    29 ++++++---                               
   trunk/boost/geometry/multi/algorithms/intersection.hpp                 |     9 ++                                      
   3 files changed, 125 insertions(+), 28 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	2011-11-27 05:23:05 EST (Sun, 27 Nov 2011)
@@ -12,6 +12,7 @@
 #include <cstddef>
 
 #include <boost/range.hpp>
+#include <boost/mpl/assert.hpp>
 
 #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
@@ -28,7 +29,7 @@
 namespace detail { namespace overlay
 {
 
-
+    
 
 /*!
 \brief Follows a linestring from intersection point to intersection point, outputting which
@@ -39,7 +40,8 @@
 <
     typename LineStringOut,
     typename LineString,
-    typename Polygon
+    typename Polygon,
+    overlay_type OverlayType
 >
 class follow
 {
@@ -119,7 +121,94 @@
         return false;
     }
 
+    // Template specialization structure to call the right actions for the right type
+    template<overlay_type OverlayType>
+    struct action_selector
+    {
+        // If you get here the overlay type is not intersection or difference
+        BOOST_MPL_ASSERT(false);
+    };
+
+    // Specialization for intersection, containing the implementation
+    template<>
+    struct action_selector<overlay_intersection>
+    {
+        template<typename OutputIterator, typename Point, typename Operation>
+        static inline void enter(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, int index, Point const& point, Operation const& operation, OutputIterator& out)
+        {
+            // On enter, append the intersection point and remember starting point
+            detail::overlay::append_no_duplicates(current_piece, point);
+            segment_id = operation.seg_id;
+        }
+
+        template<typename OutputIterator, typename Point, typename Operation>
+        static inline void leave(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, int index, Point const& point, Operation const& operation, OutputIterator& out)
+        {
+            // On leave, copy all segments from starting point, append the intersection point
+            // 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())
+            {
+                *out++ = current_piece;
+                current_piece.clear();
+            }
+        }
+
+        static inline bool is_entered(bool entered)
+        {
+            return entered;
+        }
+
+        template <typename Point, typename Geometry>
+        static inline bool included(Point const& point, Geometry const& geometry)
+        {
+            return geometry::within(point, geometry);
+        }
+
+    };
+
+    // Specialization for difference, which reverses these actions
+    template<>
+    struct action_selector<overlay_difference>
+    {
+        typedef action_selector<overlay_intersection> normal_action;
+
+        template<typename OutputIterator, typename Point, typename Operation>
+        static inline void enter(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, int index, Point const& point, Operation const& operation, OutputIterator& out)
+        {
+            normal_action::leave(current_piece, linestring, segment_id, index, point, operation, out);
+        }
+
+        template<typename OutputIterator, typename Point, typename Operation>
+        static inline void leave(LineStringOut& current_piece, LineString const& linestring, segment_identifier& segment_id, int index, Point const& point, Operation const& operation, OutputIterator& out)
+        {
+            normal_action::enter(current_piece, linestring, segment_id, index, point, operation, out);
+        }
+
+        static inline bool is_entered(bool entered)
+        {
+            return ! normal_action::is_entered(entered);
+        }
+
+        template <typename Point, typename Geometry>
+        static inline bool included(Point const& point, Geometry const& geometry)
+        {
+            return ! normal_action::included(point, geometry);
+        }
+
+    };
+
+
+
 public :
+
+    template <typename Point, typename Geometry>
+    static inline bool included(Point const& point, Geometry const& geometry)
+    {
+        return action_selector<OverlayType>::included(point, geometry);
+    }
+
     template<typename Turns, typename OutputIterator>
     static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
                 detail::overlay::operation_type operation,
@@ -132,7 +221,6 @@
                 typename turn_type::container_type
             >::type turn_operation_iterator_type;
 
-
         // Sort intersection points on segments-along-linestring, and distance
         // (like in enrich is done for poly/poly)
         std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>());
@@ -164,42 +252,33 @@
                 debug_traverse(*it, *iit, "-> Entering");
 
                 entered = true;
-                detail::overlay::append_no_duplicates(current_piece, it->point);
-                current_segment_id = iit->seg_id;
+                action_selector<OverlayType>::enter(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, out);
             }
             else if (is_leaving(*it, *iit, entered, first, linestring, polygon))
             {
                 debug_traverse(*it, *iit, "-> Leaving");
 
                 entered = false;
-                geometry::copy_segments<false>(linestring, current_segment_id,
-                        iit->seg_id.segment_index,
-                        current_piece);
-                detail::overlay::append_no_duplicates(current_piece, it->point);
-
-                if (! current_piece.empty())
-                {
-                    *out++ = current_piece;
-                    current_piece.clear();
-                }
+                action_selector<OverlayType>::leave(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, out);
             }
             first = false;
         }
 
-        if (entered)
+        if (action_selector<OverlayType>::is_entered(entered))
         {
-            geometry::copy_segments<false>(linestring, current_segment_id, 
+            geometry::copy_segments<false>(linestring, current_segment_id,
                     boost::size(linestring) - 1,
                     current_piece);
         }
 
-        // Add the last one, if applicable
+        // Output the last one, if applicable
         if (! current_piece.empty())
         {
             *out++ = current_piece;
         }
         return out;
     }
+
 };
 
 

Modified: trunk/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp	2011-11-27 05:23:05 EST (Sun, 27 Nov 2011)
@@ -29,6 +29,9 @@
 #include <boost/geometry/algorithms/detail/overlay/follow.hpp>
 #include <boost/geometry/views/segment_view.hpp>
 
+#if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
+#include <boost/foreach.hpp>
+#endif
 
 namespace boost { namespace geometry
 {
@@ -111,10 +114,18 @@
     typename LineString, typename Areal,
     bool ReverseAreal,
     typename OutputIterator, typename LineStringOut,
+    overlay_type OverlayType,
     typename Strategy
 >
 struct intersection_of_linestring_with_areal
 {
+    typedef detail::overlay::follow
+            <
+                LineStringOut,
+                LineString,
+                Areal,
+                OverlayType
+            > follower;
 
 #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
         template <typename Turn, typename Operation>
@@ -150,14 +161,17 @@
         detail::get_turns::no_interrupt_policy policy;
         geometry::get_turns
             <
-                false, ReverseAreal, detail::overlay::calculate_distance_policy
+                false,
+                (OverlayType == overlay_intersection ? ReverseAreal : !ReverseAreal),
+                detail::overlay::calculate_distance_policy
             >(linestring, areal, turns, policy);
 
         if (turns.empty())
         {
-            // No intersection points, it is either completely inside 
+            // No intersection points, it is either completely 
+            // inside (interior + borders)
             // or completely outside
-            if (geometry::within(linestring[0], areal))
+            if (follower::included(*boost::begin(linestring), areal))
             {
                 LineStringOut copy;
                 geometry::convert(linestring, copy);
@@ -174,12 +188,7 @@
         }
 #endif
 
-        return detail::overlay::follow
-            <
-                LineStringOut,
-                LineString,
-                Areal
-            >::apply
+        return follower::apply
                 (
                     linestring, areal,
                     geometry::detail::overlay::operation_intersection,
@@ -374,6 +383,7 @@
                 Linestring, Polygon,
                 ReversePolygon,
                 OutputIterator, GeometryOut,
+                OverlayType,
                 Strategy
             >
 {};
@@ -401,6 +411,7 @@
                 Linestring, Ring,
                 ReverseRing,
                 OutputIterator, GeometryOut,
+                OverlayType,
                 Strategy
             >
 {};

Modified: trunk/boost/geometry/multi/algorithms/intersection.hpp
==============================================================================
--- trunk/boost/geometry/multi/algorithms/intersection.hpp	(original)
+++ trunk/boost/geometry/multi/algorithms/intersection.hpp	2011-11-27 05:23:05 EST (Sun, 27 Nov 2011)
@@ -116,6 +116,7 @@
     typename MultiLinestring, typename Areal,
     bool ReverseAreal,
     typename OutputIterator, typename LineStringOut,
+    overlay_type OverlayType,
     typename Strategy
 >
 struct intersection_of_multi_linestring_with_areal
@@ -135,7 +136,7 @@
                 <
                     typename boost::range_value<MultiLinestring>::type,
                     Areal, ReverseAreal,
-                    OutputIterator, LineStringOut, Strategy
+                    OutputIterator, LineStringOut, OverlayType, Strategy
                 >::apply(*it, areal, out, strategy);
         }
 
@@ -150,6 +151,7 @@
     typename Areal, typename MultiLinestring,
     bool ReverseAreal,
     typename OutputIterator, typename LineStringOut,
+    overlay_type OverlayType,
     typename Strategy
 >
 struct intersection_of_areal_with_multi_linestring
@@ -162,6 +164,7 @@
             <
                 MultiLinestring, Areal, ReverseAreal,
                 OutputIterator, LineStringOut,
+                OverlayType,
                 Strategy
             >::apply(ml, areal, out, strategy);
     }
@@ -304,6 +307,7 @@
                 Linestring, MultiPolygon,
                 ReverseMultiPolygon,
                 OutputIterator, GeometryOut,
+                OverlayType,
                 Strategy
             >
 {};
@@ -333,6 +337,7 @@
                 Polygon, MultiLinestring,
                 ReversePolygon,
                 OutputIterator, GeometryOut,
+                OverlayType,
                 Strategy
             >
 {};
@@ -360,6 +365,7 @@
                 MultiLinestring, Ring,
                 ReverseRing,
                 OutputIterator, GeometryOut,
+                OverlayType,
                 Strategy
             >
 {};
@@ -389,6 +395,7 @@
                 MultiLinestring, MultiPolygon,
                 ReverseMultiPolygon,
                 OutputIterator, GeometryOut,
+                OverlayType,
                 Strategy
             >
 {};