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

Subject: [Boost-commit] svn:boost r75551 - trunk/boost/geometry/algorithms/detail/overlay
From: barend.gehrels_at_[hidden]
Date: 2011-11-19 08:40:45

Author: barendgehrels
Date: 2011-11-19 08:40:44 EST (Sat, 19 Nov 2011)
New Revision: 75551
URL: http://svn.boost.org/trac/boost/changeset/75551

Log:
Linestring/polygon overlay, first phase
Added:
   trunk/boost/geometry/algorithms/detail/overlay/follow.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/copy_segments.hpp       |    50 +++++++++++++++++++++++++               
   trunk/boost/geometry/algorithms/detail/overlay/intersection_insert.hpp |    77 +++++++++++++++++++++++++++++++++++++++ 
   2 files changed, 127 insertions(+), 0 deletions(-)

Modified: trunk/boost/geometry/algorithms/detail/overlay/copy_segments.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/copy_segments.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/copy_segments.hpp	2011-11-19 08:40:44 EST (Sat, 19 Nov 2011)
@@ -98,6 +98,41 @@
     }
 };
 
+template
+<
+    typename LineString,
+    bool Reverse,
+    typename SegmentIdentifier,
+    typename RangeOut
+>
+struct copy_segments_linestring
+{
+
+    typedef typename boost::range_iterator<LineString const>::type iterator;
+
+    static inline void apply(LineString const& ls,
+            SegmentIdentifier const& seg_id, int to_index,
+            RangeOut& current_output)
+    {
+        int const from_index = seg_id.segment_index + 1;
+
+        // Sanity check
+        if (from_index > to_index || from_index < 0 || to_index >= boost::size(ls))
+        {
+            return;
+        }
+
+        typedef typename boost::range_difference<LineString>::type size_type;
+        size_type const count = to_index - from_index + 1;
+
+        typename boost::range_iterator<LineString const>::type it = boost::begin(ls) + from_index;
+
+        for (size_type i = 0; i < count; ++i, ++it)
+        {
+            detail::overlay::append_no_duplicates(current_output, *it);
+        }
+    }
+};
 
 template
 <
@@ -208,6 +243,21 @@
 {};
 
 
+
+template
+<
+    typename LineString,
+    bool Reverse,
+    typename SegmentIdentifier,
+    typename RangeOut
+>
+struct copy_segments<linestring_tag, LineString, Reverse, SegmentIdentifier, RangeOut>
+    : detail::copy_segments::copy_segments_linestring
+        <
+            LineString, Reverse, SegmentIdentifier, RangeOut
+        >
+{};
+
 template
 <
     typename Polygon,

Added: trunk/boost/geometry/algorithms/detail/overlay/follow.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/overlay/follow.hpp	2011-11-19 08:40:44 EST (Sat, 19 Nov 2011)
@@ -0,0 +1,138 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2011 Barend Gehrels, Amsterdam, the Netherlands.
+
+// Use, modification and distribution is subject to the Boost Software License,
+// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
+
+#include <cstddef>
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
+#include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+#include <boost/geometry/core/access.hpp>
+#include <boost/geometry/core/coordinate_dimension.hpp>
+#include <boost/geometry/geometries/concepts/check.hpp>
+
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+
+template<typename Turn>
+struct sort_on_segment
+{
+    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;
+
+    }
+};
+
+
+/*!
+\brief Follows a linestring from intersection to intersection, outputting which
+    is inside, or outside, a ring or polygon
+\ingroup overlay
+ */
+template
+<
+    typename LineStringOut,
+    typename LineString,
+    typename Turns,
+    typename OutputIterator
+>
+static inline OutputIterator follow(LineString const& geometry1,
+            detail::overlay::operation_type operation,
+            Turns& turns, OutputIterator out)
+{
+    typedef typename boost::range_iterator<Turns>::type turn_iterator;
+    typedef typename boost::range_value<Turns>::type turn_type;
+    typedef typename boost::range_iterator
+        <
+            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>());
+
+    LineStringOut current_piece;
+    geometry::segment_identifier current_segment_id(0, -1, -1, -1);
+
+    // Iterate through all intersection points (they are ordered along the line)
+    bool entered = false;
+    for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
+    {
+        // Skip discarded/blocked ones TODO
+        ////if (! (it->is_discarded() || it->blocked()))
+        {
+            turn_operation_iterator_type iit = boost::begin(it->operations);
+
+            if (iit->operation == operation_intersection)
+            {
+                // Entering
+                entered = true;
+                detail::overlay::append_no_duplicates(current_piece, it->point);
+                current_segment_id = iit->seg_id;
+            }
+            else if (iit->operation == operation_union)
+            {
+                // Leaving
+                entered = false;
+                geometry::copy_segments<false>(geometry1, 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();
+                }
+            }
+        }
+    }
+
+    if (entered)
+    {
+        geometry::copy_segments<false>(geometry1, current_segment_id, 
+                boost::size(geometry1) - 1,
+                current_piece);
+    }
+
+    // Add the last one, if applicable
+    if (! current_piece.empty())
+    {
+        *out++ = current_piece;
+    }
+    return out;
+}
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP

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-19 08:40:44 EST (Sat, 19 Nov 2011)
@@ -26,6 +26,7 @@
 #include <boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp>
 #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
+#include <boost/geometry/algorithms/detail/overlay/follow.hpp>
 #include <boost/geometry/views/segment_view.hpp>
 
 
@@ -102,6 +103,55 @@
     }
 };
 
+template
+<
+    typename LineString, typename Polygon,
+    typename OutputIterator, typename LineStringOut,
+    typename Strategy
+>
+struct intersection_linestring_polygon
+{
+    static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
+            OutputIterator out,
+            Strategy const& strategy)
+    {
+        if (boost::size(linestring) == 0)
+        {
+            return out;
+        }
+        typedef typename point_type<LineStringOut>::type point_type;
+
+        typedef detail::overlay::traversal_turn_info<point_type> turn_info;
+        std::deque<turn_info> turns;
+
+        detail::get_turns::no_interrupt_policy policy;
+        geometry::get_turns
+            <
+                false, false, detail::overlay::calculate_distance_policy
+            >(linestring, polygon, turns, policy);
+
+        if (turns.empty())
+        {
+            if (geometry::within(linestring[0], polygon))
+            {
+                LineStringOut copy;
+                geometry::convert(linestring, copy);
+                *out++ = copy;
+            }
+            return out;
+        }
+
+        return detail::overlay::follow<LineStringOut>
+                (
+                    linestring, 
+                    geometry::detail::overlay::operation_intersection,
+                    turns, out
+                );
+    }
+};
+
+
+
 }} // namespace detail::intersection
 #endif // DOXYGEN_NO_DETAIL
 
@@ -264,6 +314,33 @@
     }
 };
 
+
+template
+<
+    typename Linestring, typename Polygon,
+    bool Reverse1, bool Reverse2, bool ReverseOut,
+    typename OutputIterator, typename GeometryOut,
+    overlay_type OverlayType,
+    typename Strategy
+>
+struct intersection_insert
+    <
+        linestring_tag, polygon_tag, linestring_tag,
+        false, true, false,
+        Linestring, Polygon,
+        Reverse1, Reverse2, ReverseOut,
+        OutputIterator, GeometryOut,
+        OverlayType,
+        Strategy
+    > : detail::intersection::intersection_linestring_polygon
+            <
+                Linestring, Polygon,
+                OutputIterator, GeometryOut,
+                Strategy
+            >
+{};
+
+
 template
 <
     typename Segment, typename Box,