[Boost-commit] svn:boost r75684 - trunk/boost/geometry/algorithms/detail/overlay

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

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

Log:
Linestring/polygon overlay, fix for gcc (and probably more): extracted subclass
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/follow.hpp |   336 +++++++++++++++++++++++---------------- 
   1 files changed, 200 insertions(+), 136 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:44:22 EST (Sun, 27 Nov 2011)
@@ -29,174 +29,236 @@
 namespace detail { namespace overlay
 {
 
+namespace following
+{
     
+template <typename Turn, typename Operation>
+static inline bool is_entering(Turn const& turn, Operation const& op)
+{
+    // (Blocked means: blocked for polygon/polygon intersection, because
+    // they are reversed. But for polygon/line it is similar to continue)
+    return op.operation == operation_intersection
+        || op.operation == operation_continue
+        || op.operation == operation_blocked
+        ;
+}
 
-/*!
-\brief Follows a linestring from intersection point to intersection point, outputting which
-    is inside, or outside, a ring or polygon
-\ingroup overlay
- */
-template
+template 
 <
-    typename LineStringOut,
-    typename LineString,
-    typename Polygon,
-    overlay_type OverlayType
+    typename Turn, 
+    typename Operation, 
+    typename LineString, 
+    typename Polygon
 >
-class follow
+static inline bool is_leaving(Turn const& turn, Operation const& op, 
+                bool entered, bool first, 
+                LineString const& linestring, Polygon const& polygon)
 {
-
-    template<typename Turn>
-    struct sort_on_segment
+    if (op.operation == operation_union)
     {
-        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;
+        return entered 
+            || turn.method == method_crosses
+            || (first && geometry::within(linestring[0], polygon))
+            ;
+    }
+    return false;
+}
 
-        }
-    };
 
-    template <typename Turn, typename Operation>
-    static inline bool is_entering(Turn const& turn, Operation const& op)
+template 
+<
+    typename Turn, 
+    typename Operation, 
+    typename LineString, 
+    typename Polygon
+>
+static inline bool is_staying_inside(Turn const& turn, Operation const& op, 
+                bool entered, bool first, 
+                LineString const& linestring, Polygon const& polygon)
+{
+    if (turn.method == method_crosses)
     {
-        // (Blocked means: blocked for polygon/polygon intersection, because
-        // they are reversed. But for polygon/line it is similar to continue)
-        return op.operation == operation_intersection
-            || op.operation == operation_continue
-            || op.operation == operation_blocked
-            ;
+        // The normal case, this is completely covered with entering/leaving 
+        // so stay out of this time consuming "within"
+        return false;
     }
 
-    template <typename Turn, typename Operation>
-    static inline bool is_leaving(Turn const& turn, Operation const& op, 
-                    bool entered, bool first, 
-                    LineString const& linestring, Polygon const& polygon)
+    if (is_entering(turn, op))
     {
-        if (op.operation == operation_union)
-        {
-            return entered 
-                || turn.method == method_crosses
-                || (first && geometry::within(linestring[0], polygon))
-                ;
-        }
-        return false;
+        return entered || (first && geometry::within(linestring[0], polygon));
     }
 
+    return false;
+}
 
-    template <typename Turn, typename Operation>
-    static inline bool is_staying_inside(Turn const& turn, Operation const& op, 
-                    bool entered, bool first, 
-                    LineString const& linestring, Polygon const& polygon)
+template <typename Turn>
+static inline bool was_entered(Turn const& turn, bool first)
+{
+    if (first && (turn.method == method_collinear || turn.method == method_equal))
     {
-        if (turn.method == method_crosses)
-        {
-            // The normal case, this is completely covered with entering/leaving 
-            // so stay out of this time consuming "within"
-            return false;
-        }
+        // If it is the very first point, and either equal or collinear, there is only one
+        // IP generated (on purpose). So consider this as having entered. 
+        // Maybe it will leave immediately after that (u/i) but that is checked later.
+        return true;
+    }
+    return false;
+}
 
-        if (is_entering(turn, op))
-        {
-            return entered || (first && geometry::within(linestring[0], polygon));
-        }
 
-        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 LineStringOut, 
+        typename LineString, 
+        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 Turn>
-    static inline bool was_entered(Turn const& turn, bool first)
+    template
+    <
+        typename OutputIterator, 
+        typename LineStringOut, 
+        typename LineString, 
+        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)
     {
-        if (first && (turn.method == method_collinear || turn.method == method_equal))
+        // 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())
         {
-            // If it is the very first point, and either equal or collinear, there is only one
-            // IP generated (on purpose). So consider this as having entered. 
-            // Maybe it will leave immediately after that (u/i) but that is checked later.
-            return true;
+            *out++ = current_piece;
+            current_piece.clear();
         }
-        return false;
     }
 
-    // Template specialization structure to call the right actions for the right type
-    template<overlay_type OverlayType>
-    struct action_selector
+    static inline bool is_entered(bool entered)
     {
-        // If you get here the overlay type is not intersection or difference
-        BOOST_MPL_ASSERT(false);
-    };
+        return entered;
+    }
 
-    // Specialization for intersection, containing the implementation
-    template<>
-    struct action_selector<overlay_intersection>
+    template <typename Point, typename Geometry>
+    static inline bool included(Point const& point, Geometry const& geometry)
     {
-        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;
-        }
+        return geometry::within(point, geometry);
+    }
 
-        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;
-        }
+// Specialization for difference, which reverses these actions
+template<>
+struct action_selector<overlay_difference>
+{
+    typedef action_selector<overlay_intersection> normal_action;
 
-        template <typename Point, typename Geometry>
-        static inline bool included(Point const& point, Geometry const& geometry)
-        {
-            return geometry::within(point, geometry);
-        }
+    template
+    <
+        typename OutputIterator, 
+        typename LineStringOut, 
+        typename LineString, 
+        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 LineStringOut, 
+        typename LineString, 
+        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);
+    }
 
-    // Specialization for difference, which reverses these actions
-    template<>
-    struct action_selector<overlay_difference>
+    static inline bool is_entered(bool entered)
     {
-        typedef action_selector<overlay_intersection> normal_action;
+        return ! normal_action::is_entered(entered);
+    }
 
-        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 Point, typename Geometry>
+    static inline bool included(Point const& point, Geometry const& geometry)
+    {
+        return ! normal_action::included(point, geometry);
+    }
 
-        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)
+/*!
+\brief Follows a linestring from intersection point to intersection point, outputting which
+    is inside, or outside, a ring or polygon
+\ingroup overlay
+ */
+template
+<
+    typename LineStringOut,
+    typename LineString,
+    typename Polygon,
+    overlay_type OverlayType
+>
+class follow
+{
+
+    template<typename Turn>
+    struct sort_on_segment
+    {
+        inline bool operator()(Turn const& left, Turn const& right) const
         {
-            return ! normal_action::included(point, geometry);
-        }
+            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;
+
+        }
     };
 
 
@@ -206,7 +268,7 @@
     template <typename Point, typename Geometry>
     static inline bool included(Point const& point, Geometry const& geometry)
     {
-        return action_selector<OverlayType>::included(point, geometry);
+        return following::action_selector<OverlayType>::included(point, geometry);
     }
 
     template<typename Turns, typename OutputIterator>
@@ -221,6 +283,8 @@
                 typename turn_type::container_type
             >::type turn_operation_iterator_type;
 
+        typedef following::action_selector<OverlayType> action;
+
         // 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>());
@@ -235,36 +299,36 @@
         {
             turn_operation_iterator_type iit = boost::begin(it->operations);
 
-            if (was_entered(*it, first))
+            if (following::was_entered(*it, first))
             {
                 debug_traverse(*it, *iit, "-> Was entered");
                 entered = true;
             }
 
-            if (is_staying_inside(*it, *iit, entered, first, linestring, polygon))
+            if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon))
             {
                 debug_traverse(*it, *iit, "-> Staying inside");
 
                 entered = true;
             }
-            else if (is_entering(*it, *iit))
+            else if (following::is_entering(*it, *iit))
             {
                 debug_traverse(*it, *iit, "-> Entering");
 
                 entered = true;
-                action_selector<OverlayType>::enter(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, out);
+                action::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))
+            else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon))
             {
                 debug_traverse(*it, *iit, "-> Leaving");
 
                 entered = false;
-                action_selector<OverlayType>::leave(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, out);
+                action::leave(current_piece, linestring, current_segment_id, iit->seg_id.segment_index, it->point, *iit, out);
             }
             first = false;
         }
 
-        if (action_selector<OverlayType>::is_entered(entered))
+        if (action::is_entered(entered))
         {
             geometry::copy_segments<false>(linestring, current_segment_id,
                     boost::size(linestring) - 1,