[Boost-commit] svn:boost r76676 - in trunk: boost/geometry/extensions/algorithms/buffer boost/geometry/extensions/strategies libs/geometry/test_extensions/algorithms/buffer

Subject: [Boost-commit] svn:boost r76676 - in trunk: boost/geometry/extensions/algorithms/buffer boost/geometry/extensions/strategies libs/geometry/test_extensions/algorithms/buffer
From: barend.gehrels_at_[hidden]
Date: 2012-01-24 18:04:31

Author: barendgehrels
Date: 2012-01-24 18:04:30 EST (Tue, 24 Jan 2012)
New Revision: 76676
URL: http://svn.boost.org/trac/boost/changeset/76676

Log:
Buffer update, merged impl's of polygon/linestring into range_buffer, and some more tidy up
Added:
   trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp
      - copied, changed from r76549, /trunk/boost/geometry/extensions/algorithms/buffer/intersecting_inserter.hpp
   trunk/boost/geometry/extensions/algorithms/buffer/range_buffer.hpp   (contents, props changed)
Removed:
   trunk/boost/geometry/extensions/algorithms/buffer/intersecting_inserter.hpp
Text files modified: 
   trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp   |    71 ++++----------                          
   trunk/boost/geometry/extensions/algorithms/buffer/linestring_buffer.hpp |   172 ++++---------------------------------   
   trunk/boost/geometry/extensions/algorithms/buffer/polygon_buffer.hpp    |   182 ++++++--------------------------------- 
   trunk/boost/geometry/extensions/strategies/buffer.hpp                   |   102 ++++++++--------------                  
   trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp   |    13 --                                      
   5 files changed, 109 insertions(+), 431 deletions(-)

Copied: trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp (from r76549, /trunk/boost/geometry/extensions/algorithms/buffer/intersecting_inserter.hpp)
==============================================================================
--- /trunk/boost/geometry/extensions/algorithms/buffer/intersecting_inserter.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp	2012-01-24 18:04:30 EST (Tue, 24 Jan 2012)
@@ -6,8 +6,8 @@
 // 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_BUFFER_INTERSECTING_INSERTER_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_INTERSECTING_INSERTER_HPP
+#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_APPENDER_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_APPENDER_HPP
 
 
 #include <cstddef>
@@ -15,7 +15,6 @@
 #include <boost/range.hpp>
 
 #include <boost/geometry/core/point_type.hpp>
-#include <boost/geometry/core/ring_type.hpp>
 
 
 namespace boost { namespace geometry
@@ -26,60 +25,32 @@
 namespace detail { namespace buffer
 {
 
-
-template
-<
-    typename Collection  // usually collection of rings
->
-struct intersecting_inserter
+// Appends points to an output range (always a ring).
+// This is only the first phase, on the way specific points will be "marked"
+// as a begin-point, and some segments will be intersected with all previous segments
+// up to the "marked" point. If there is an intersection then points in between will
+// be deleted and the intersection point will be added instead.
+
+// This file is renamed from "intersecting_inserter" but we choose "append" now
+// because that is also how the algorithm geometry::append is called. And it appends at the back (push_back)
+template<typename Range>
+struct buffer_appender
 {
-    typedef typename boost::range_value<Collection>::type item_type;
-    typedef typename geometry::ring_type<item_type>::type ring_type;
-    typedef typename geometry::point_type<ring_type>::type point_type;
-
-    intersecting_inserter(Collection& c)
-        : m_collection(c)
-        , m_index(0)
-    {}
+    typedef Range range_type;
 
-    inline void start_ring()
-    {
-        // clear current ring
-        m_ring.clear();
-        m_index = 0;
-    }
-
-    inline ring_type& get_ring()
-    {
-        return m_ring;
-    }
-
-
-    inline void insert(point_type const& point)
-    {
-        m_ring.push_back(point);
-    }
+    typedef typename geometry::point_type<Range>::type point_type;
 
+    inline buffer_appender(Range& r)
+        : m_range(r)
+    {}
 
-    inline void close_and_insert_ring()
+    inline void append(point_type const& point)
     {
-        if (boost::size(m_ring) > 0)
-        {
-            // Close the ring
-            point_type p = m_ring.front();
-            insert(p);
-
-            item_type poly;
-            poly.outer() = m_ring;
-            m_collection.push_back(poly);
-        }
+        m_range.push_back(point);
     }
 
-
 private :
-    Collection& m_collection;
-    ring_type m_ring;
-    std::size_t m_index;
+    Range& m_range;
 };
 
 
@@ -90,4 +61,4 @@
 }} // namespace boost::geometry
 
 
-#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_INTERSECTING_INSERTER_HPP
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_APPENDER_HPP

Deleted: trunk/boost/geometry/extensions/algorithms/buffer/intersecting_inserter.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/intersecting_inserter.hpp	2012-01-24 18:04:30 EST (Tue, 24 Jan 2012)
+++ (empty file)
@@ -1,93 +0,0 @@
-// Boost.Geometry (aka GGL, Generic Geometry Library)
-
-// Copyright (c) 2007-2012 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_BUFFER_INTERSECTING_INSERTER_HPP
-#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_INTERSECTING_INSERTER_HPP
-
-
-#include <cstddef>
-
-#include <boost/range.hpp>
-
-#include <boost/geometry/core/point_type.hpp>
-#include <boost/geometry/core/ring_type.hpp>
-
-
-namespace boost { namespace geometry
-{
-
-
-#ifndef DOXYGEN_NO_DETAIL
-namespace detail { namespace buffer
-{
-
-
-template
-<
-    typename Collection  // usually collection of rings
->
-struct intersecting_inserter
-{
-    typedef typename boost::range_value<Collection>::type item_type;
-    typedef typename geometry::ring_type<item_type>::type ring_type;
-    typedef typename geometry::point_type<ring_type>::type point_type;
-
-    intersecting_inserter(Collection& c)
-        : m_collection(c)
-        , m_index(0)
-    {}
-
-    inline void start_ring()
-    {
-        // clear current ring
-        m_ring.clear();
-        m_index = 0;
-    }
-
-    inline ring_type& get_ring()
-    {
-        return m_ring;
-    }
-
-
-    inline void insert(point_type const& point)
-    {
-        m_ring.push_back(point);
-    }
-
-
-    inline void close_and_insert_ring()
-    {
-        if (boost::size(m_ring) > 0)
-        {
-            // Close the ring
-            point_type p = m_ring.front();
-            insert(p);
-
-            item_type poly;
-            poly.outer() = m_ring;
-            m_collection.push_back(poly);
-        }
-    }
-
-
-private :
-    Collection& m_collection;
-    ring_type m_ring;
-    std::size_t m_index;
-};
-
-
-}} // namespace detail::buffer
-#endif // DOXYGEN_NO_DETAIL
-
-
-}} // namespace boost::geometry
-
-
-#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_INTERSECTING_INSERTER_HPP

Modified: trunk/boost/geometry/extensions/algorithms/buffer/linestring_buffer.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/linestring_buffer.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/linestring_buffer.hpp	2012-01-24 18:04:30 EST (Tue, 24 Jan 2012)
@@ -15,16 +15,10 @@
 
 #include <boost/range.hpp>
 
-#include <boost/geometry/core/point_type.hpp>
-
 #include <boost/geometry/extensions/strategies/buffer_side.hpp>
 
-#include <boost/geometry/extensions/algorithms/buffer/line_line_intersection.hpp>
-#include <boost/geometry/extensions/algorithms/buffer/intersecting_inserter.hpp>
-
-#include <boost/geometry/geometries/segment.hpp>
-
-
+#include <boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp>
+#include <boost/geometry/extensions/algorithms/buffer/range_buffer.hpp>
 
 
 namespace boost { namespace geometry
@@ -35,7 +29,6 @@
 namespace detail { namespace buffer
 {
 
-
 template
 <
     typename Linestring,
@@ -43,146 +36,23 @@
     typename DistanceStrategy,
     typename JoinStrategy
 >
-struct linestring_buffer
+struct linestring_buffer 
+    : public range_buffer
+        <
+            typename ring_type<Polygon>::type, 
+            DistanceStrategy, 
+            JoinStrategy,
+            linestring_tag
+        >
 {
-    typedef typename point_type<Polygon>::type output_point_type;
-    typedef typename coordinate_type<Polygon>::type coordinate_type;
-    typedef model::referring_segment<output_point_type const> segment_type;
-
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-    typedef typename ring_type<Polygon>::type ring_type;
-#endif
 
     template
     <
-        typename Inserter,
-        typename Iterator
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-        , typename Mapper
+        typename Mapper
 #endif
     >
-    static inline void iterate(Inserter& inserter,
-                Iterator begin, Iterator end,
-                buffer_side_selector side,
-
-                DistanceStrategy const& distance,
-                JoinStrategy const& join_strategy
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-                , Mapper& mapper
-#endif
-            )
-    {
-        output_point_type previous_p1, previous_p2;
-        output_point_type first_p1, first_p2;
-
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-        int index = 0;
-#endif
-
-        bool first = true;
-
-        Iterator it = begin;
-        for (Iterator prev = it++; it != end; ++it)
-        {
-            if (! detail::equals::equals_point_point(*prev, *it))
-            {
-                bool skip = false;
-
-                // Generate a block along (left or right of) the segment
-
-                // Simulate a vector d (dx,dy)
-                coordinate_type dx = get<0>(*it) - get<0>(*prev);
-                coordinate_type dy = get<1>(*it) - get<1>(*prev);
-
-                // For normalization [0,1] (=dot product d.d, sqrt)
-                coordinate_type length = sqrt(dx * dx + dy * dy);
-
-                // Because coordinates are not equal, length should not be zero
-                BOOST_ASSERT((! geometry::math::equals(length, 0)));
-
-                // Generate the normalized perpendicular p, to the left (ccw)
-                coordinate_type px = -dy / length;
-                coordinate_type py = dx / length;
-
-                output_point_type p1, p2;
-
-                coordinate_type d = distance.apply(*prev, *it, side);
-
-                set<0>(p2, get<0>(*it) + px * d);
-                set<1>(p2, get<1>(*it) + py * d);
-
-                set<0>(p1, get<0>(*prev) + px * d);
-                set<1>(p1, get<1>(*prev) + py * d);
-
-                {
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-                    ring_type block;
-                    block.push_back(*prev);
-                    block.push_back(*it);
-                    block.push_back(p2);
-                    block.push_back(p1);
-                    block.push_back(*prev);
-
-                    mapper.map(block, "opacity:0.4;fill:rgb(0,255,0);stroke:rgb(0,0,0);stroke-width:1");
-#endif
-                }
-
-                if (! first)
-                {
-                    output_point_type p;
-                    segment_type s1(p1, p2);
-                    segment_type s2(previous_p1, previous_p2);
-                    if (line_line_intersection<output_point_type, segment_type>::apply(s1, s2, p))
-                    {
-                        join_strategy.apply(p, *prev, previous_p2, p1,
-                                    distance.apply(*prev, *it, side),
-                                    inserter.get_ring());
-                        {
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-                            mapper.map(p, "fill:rgb(0,0,0);", 3);
-
-                            std::ostringstream out;
-                            out << index++;
-                            mapper.text(p, out.str(), "fill:rgb(0,0,0);font-family='Arial';", 5, 5);
-#endif
-                        }
-                    }
-                    else
-                    {
-                        skip = false;
-                    }
-                }
-                else
-                {
-                    first = false;
-                    first_p1 = p1;
-                    first_p2 = p2;
-
-                    inserter.insert(p1);
-                }
-
-                if (! skip)
-                {
-                    previous_p1 = p1;
-                    previous_p2 = p2;
-                    prev = it;
-                }
-            }
-        }
-
-        // Last one
-        inserter.insert(previous_p2);
-    }
-
-
-    template
-    <
-        typename Inserter
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-        , typename Mapper
-#endif
-    >
-    static inline void apply(Linestring const& linestring, Inserter& inserter,
+    static inline void apply(Linestring const& linestring, Polygon& buffered,
             DistanceStrategy const& distance,
             JoinStrategy const& join_strategy
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
@@ -190,14 +60,12 @@
 #endif
             )
     {
-        typedef typename boost::range_iterator
-            <
-                Linestring const
-            >::type iterator_type;
-
-        inserter.start_ring();
+        buffer_appender<typename geometry::ring_type<Polygon>::type> appender
+            (
+                geometry::exterior_ring(buffered)
+            );
 
-        iterate(inserter, boost::begin(linestring), boost::end(linestring),
+        iterate(appender, boost::begin(linestring), boost::end(linestring),
             buffer_side_left,
             distance, join_strategy
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
@@ -205,14 +73,14 @@
 #endif
             );
 
-        iterate(inserter, boost::rbegin(linestring), boost::rend(linestring),
-            buffer_side_right, distance, join_strategy
+        iterate(appender, boost::rbegin(linestring), boost::rend(linestring),
+            buffer_side_right,
+            distance, join_strategy
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
             , mapper
 #endif
             );
 
-        inserter.close_and_insert_ring();
     }
 };
 

Modified: trunk/boost/geometry/extensions/algorithms/buffer/polygon_buffer.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/polygon_buffer.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/polygon_buffer.hpp	2012-01-24 18:04:30 EST (Tue, 24 Jan 2012)
@@ -16,13 +16,12 @@
 #include <boost/range.hpp>
 #include <boost/typeof/typeof.hpp>
 
-#include <boost/geometry/core/point_type.hpp>
+#include <boost/geometry/core/exterior_ring.hpp>
 #include <boost/geometry/core/interior_rings.hpp>
 
 #include <boost/geometry/extensions/strategies/buffer_side.hpp>
-#include <boost/geometry/extensions/algorithms/buffer/line_line_intersection.hpp>
-
-
+#include <boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp>
+#include <boost/geometry/extensions/algorithms/buffer/range_buffer.hpp>
 
 
 namespace boost { namespace geometry
@@ -42,172 +41,38 @@
     typename JoinStrategy
 >
 struct ring_buffer
+    : public range_buffer
+        <
+            RingOutput, 
+            DistanceStrategy, 
+            JoinStrategy,
+            ring_tag
+        >
 {
-    typedef typename point_type<RingOutput>::type output_point_type;
-    typedef typename coordinate_type<output_point_type>::type coordinate_type;
-    typedef model::referring_segment<output_point_type const> segment_type;
 
     template
     <
-        typename Iterator
+        typename BufferAppender
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
         , typename Mapper
 #endif
     >
-    static inline void iterate(RingOutput& buffered,
-                Iterator begin, Iterator end,
-                buffer_side_selector side,
-                DistanceStrategy const& distance,
-                JoinStrategy const& join_strategy
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-                , Mapper& mapper
-#endif
-            )
-    {
-        output_point_type previous_p1, previous_p2;
-        output_point_type first_p1, first_p2;
-
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-        int index = 0;
-#endif
-
-        bool first = true;
-
-        Iterator it = begin;
-        for (Iterator prev = it++; it != end; ++it)
-        {
-            if (! detail::equals::equals_point_point(*prev, *it))
-            {
-                bool skip = false;
-
-                // Generate a block along (left or right of) the segment
-
-                // Simulate a vector d (dx,dy)
-                coordinate_type dx = get<0>(*it) - get<0>(*prev);
-                coordinate_type dy = get<1>(*it) - get<1>(*prev);
-
-                // For normalization [0,1] (=dot product d.d, sqrt)
-                coordinate_type length = sqrt(dx * dx + dy * dy);
-
-                // Because coordinates are not equal, length should not be zero
-                BOOST_ASSERT((! geometry::math::equals(length, 0)));
-
-                // Generate the normalized perpendicular p, to the left (ccw)
-                coordinate_type px = -dy / length;
-                coordinate_type py = dx / length;
-
-                output_point_type p1, p2;
-
-                coordinate_type d = distance.apply(*prev, *it, side);
-
-                set<0>(p2, get<0>(*it) + px * d);
-                set<1>(p2, get<1>(*it) + py * d);
-
-                set<0>(p1, get<0>(*prev) + px * d);
-                set<1>(p1, get<1>(*prev) + py * d);
-
-                {
-    #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-                    RingOutput block;
-                    block.push_back(*prev);
-                    block.push_back(*it);
-                    block.push_back(p2);
-                    block.push_back(p1);
-                    block.push_back(*prev);
-
-                    mapper.map(block, "opacity:0.4;fill:rgb(255,128,0);stroke:rgb(0,0,0);stroke-width:1");
-    #endif
-                }
-
-                if (! first)
-                {
-                    output_point_type p;
-                    segment_type s1(p1, p2);
-                    segment_type s2(previous_p1, previous_p2);
-                    if (line_line_intersection<output_point_type, segment_type>::apply(s1, s2, p))
-                    {
-                        join_strategy.apply(p, *prev, previous_p2, p1,
-                                    distance.apply(*prev, *it, side),
-                                    buffered);
-                        {
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-                            mapper.map(p, "fill:rgb(0,0,0);", 3);
-
-                            std::ostringstream out;
-                            out << index++;
-                            mapper.text(p, out.str(), "fill:rgb(0,0,0);font-family='Arial';", 5, 5);
-#endif
-                        }
-                    }
-                    else
-                    {
-                        skip = false;
-                    }
-                }
-                else
-                {
-                    first = false;
-                    first_p1 = p1;
-                    first_p2 = p2;
-                }
-
-                if (! skip)
-                {
-                    previous_p1 = p1;
-                    previous_p2 = p2;
-                    prev = it;
-                }
-            }
-        }
-
-        // Last one
-        {
-            output_point_type p;
-            segment_type s1(previous_p1, previous_p2);
-            segment_type s2(first_p1, first_p2);
-            line_line_intersection<output_point_type, segment_type>::apply(s1, s2, p);
-
-            join_strategy.apply(p, *begin, previous_p2, first_p1,
-                distance.apply(*(end - 1), *begin, side),
-                buffered);
-
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-            mapper.map(p, "fill:rgb(0,0,0);", 3);
-            std::ostringstream out;
-            out << index++;
-            mapper.text(p, out.str(), "fill:rgb(0,0,0);font-family='Arial';", 5, 5);
-#endif
-        }
-    }
-
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-    template <typename Mapper>
-#endif
     static inline void apply(RingInput const& ring,
-                RingOutput& buffered,
-
-                DistanceStrategy const& distance,
-
+            BufferAppender& appender,
+            DistanceStrategy const& distance,
             JoinStrategy const& join_strategy
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
             , Mapper& mapper
 #endif
             )
     {
-        iterate(buffered, boost::begin(ring), boost::end(ring),
+        iterate(appender, boost::begin(ring), boost::end(ring),
                 buffer_side_left,
                 distance, join_strategy
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
             , mapper
 #endif
             );
-
-
-        // Close the generated buffer
-        {
-            output_point_type p = *boost::begin(buffered);
-            buffered.push_back(p);
-        }
     }
 };
 
@@ -238,20 +103,29 @@
         typedef typename ring_type<PolygonInput>::type input_ring_type;
         typedef typename ring_type<PolygonOutput>::type output_ring_type;
 
+        typedef buffer_appender<output_ring_type> appender_type;
+
         typedef ring_buffer<input_ring_type, output_ring_type, DistanceStrategy, JoinStrategy> policy;
-        policy::apply(exterior_ring(polygon), exterior_ring(buffered),
-                distance, join_strategy
+
+        {
+            appender_type appender(geometry::exterior_ring(buffered));
+            policy::apply(exterior_ring(polygon), appender,
+                    distance, join_strategy
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-                , mapper
+                    , mapper
 #endif
-                );
+                    );
+        }
 
         typename interior_return_type<PolygonInput const>::type rings
                     = interior_rings(polygon);
         for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it)
         {
             output_ring_type ring;
-            policy::apply(*it, ring, distance, join_strategy
+
+            appender_type appender(ring);
+
+            policy::apply(*it, appender, distance, join_strategy
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
                 , mapper
 #endif

Added: trunk/boost/geometry/extensions/algorithms/buffer/range_buffer.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/extensions/algorithms/buffer/range_buffer.hpp	2012-01-24 18:04:30 EST (Tue, 24 Jan 2012)
@@ -0,0 +1,204 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2007-2012 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_BUFFER_RANGE_BUFFER_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_RANGE_BUFFER_HPP
+
+#include <cstddef>
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/coordinate_type.hpp>
+#include <boost/geometry/core/point_type.hpp>
+
+#include <boost/geometry/extensions/strategies/buffer_side.hpp>
+
+#include <boost/geometry/extensions/algorithms/buffer/line_line_intersection.hpp>
+
+#include <boost/geometry/geometries/segment.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace buffer
+{
+
+template
+<
+    typename RingOutput,
+    typename DistanceStrategy,
+    typename JoinStrategy,
+    typename Tag
+>
+struct range_buffer
+{
+    typedef typename point_type<RingOutput>::type output_point_type;
+    typedef typename coordinate_type<RingOutput>::type coordinate_type;
+    typedef model::referring_segment<output_point_type const> segment_type;
+
+    template
+    <
+        typename BufferAppender,
+        typename Iterator
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+        , typename Mapper
+#endif
+    >
+    static inline void iterate(BufferAppender& appender,
+                Iterator begin, Iterator end,
+                buffer_side_selector side,
+                DistanceStrategy const& distance,
+                JoinStrategy const& join_strategy
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+                , Mapper& mapper
+#endif
+            )
+    {
+        output_point_type previous_p1, previous_p2;
+        output_point_type first_p1, first_p2;
+
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+        int index = 0;
+#endif
+
+        bool first = true;
+
+        Iterator it = begin;
+        for (Iterator prev = it++; it != end; ++it)
+        {
+            if (! detail::equals::equals_point_point(*prev, *it))
+            {
+                // Generate a block along (left or right of) the segment
+
+                // Simulate a vector d (dx,dy)
+                coordinate_type dx = get<0>(*it) - get<0>(*prev);
+                coordinate_type dy = get<1>(*it) - get<1>(*prev);
+
+                // For normalization [0,1] (=dot product d.d, sqrt)
+                coordinate_type length = sqrt(dx * dx + dy * dy);
+
+                // Because coordinates are not equal, length should not be zero
+                BOOST_ASSERT((! geometry::math::equals(length, 0)));
+
+                // Generate the normalized perpendicular p, to the left (ccw)
+                coordinate_type px = -dy / length;
+                coordinate_type py = dx / length;
+
+                output_point_type p1, p2;
+
+                coordinate_type d = distance.apply(*prev, *it, side);
+
+                set<0>(p2, get<0>(*it) + px * d);
+                set<1>(p2, get<1>(*it) + py * d);
+
+                set<0>(p1, get<0>(*prev) + px * d);
+                set<1>(p1, get<1>(*prev) + py * d);
+
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+                {
+                    RingOutput block;
+                    block.push_back(*prev);
+                    block.push_back(*it);
+                    block.push_back(p2);
+                    block.push_back(p1);
+                    block.push_back(*prev);
+
+                    if(boost::is_same<Tag, ring_tag>::value)
+                    {
+                        mapper.map(block, "opacity:0.4;fill:rgb(255,128,0);stroke:rgb(0,0,0);stroke-width:1");
+                    }
+                    else if(boost::is_same<Tag, linestring_tag>::value)
+                    {
+                        mapper.map(block, "opacity:0.4;fill:rgb(0,255,0);stroke:rgb(0,0,0);stroke-width:1");
+                    }
+                }
+#endif
+
+                if (! first)
+                {
+                    output_point_type p;
+                    segment_type s1(p1, p2);
+                    segment_type s2(previous_p1, previous_p2);
+                    if (line_line_intersection<output_point_type, segment_type>::apply(s1, s2, p))
+                    {
+                        join_strategy.apply(p, *prev, previous_p2, p1,
+                                    distance.apply(*prev, *it, side),
+                                    appender);
+
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+                        {
+                            mapper.map(p, "fill:rgb(0,0,0);", 3);
+
+                            std::ostringstream out;
+                            out << index++;
+                            mapper.text(p, out.str(), "fill:rgb(0,0,0);font-family='Arial';", 5, 5);
+                        }
+#endif
+                    }
+                }
+                else
+                {
+                    first = false;
+                    first_p1 = p1;
+                    first_p2 = p2;
+
+                    // Might be replaced by specialization
+                    if(boost::is_same<Tag, linestring_tag>::value)
+                    {
+                        appender.append(p1);
+                    }
+                }
+
+                previous_p1 = p1;
+                previous_p2 = p2;
+                prev = it;
+            }
+        }
+
+        // Might be replaced by specialization
+        if(boost::is_same<Tag, linestring_tag>::value)
+        {
+            appender.append(previous_p2);
+        }
+        else if(boost::is_same<Tag, ring_tag>::value)
+        {
+            // Generate closing corner
+            output_point_type p;
+            segment_type s1(previous_p1, previous_p2);
+            segment_type s2(first_p1, first_p2);
+            line_line_intersection<output_point_type, segment_type>::apply(s1, s2, p);
+
+            join_strategy.apply(p, *begin, previous_p2, first_p1,
+                distance.apply(*(end - 1), *begin, side),
+                appender);
+
+            // Close the generated buffer (NOT FOR OPEN POLYGONS - TODO)
+            appender.append(first_p1);
+
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+            {
+                mapper.map(p, "fill:rgb(0,0,0);", 3);
+                std::ostringstream out;
+                out << index++;
+                mapper.text(p, out.str(), "fill:rgb(0,0,0);font-family='Arial';", 5, 5);
+            }
+#endif
+        }
+    }
+};
+
+}} // namespace detail::buffer
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_RANGE_BUFFER_HPP

Modified: trunk/boost/geometry/extensions/strategies/buffer.hpp
==============================================================================
--- trunk/boost/geometry/extensions/strategies/buffer.hpp	(original)
+++ trunk/boost/geometry/extensions/strategies/buffer.hpp	2012-01-24 18:04:30 EST (Tue, 24 Jan 2012)
@@ -25,22 +25,12 @@
 #include <boost/geometry/extensions/strategies/buffer_side.hpp>
 
 
-// This should NOT be defined, it omits essential points in concavities.
-// Code is commented now
-// #define BOOST_GEOMETRY_BUFFER_NO_HELPER_POINTS
-
-
 namespace boost { namespace geometry
 {
 
-
-
-
 namespace strategy { namespace buffer
 {
 
-
-
 /*
 
    A Buffer-join strategy gets 4 input points.
@@ -81,11 +71,11 @@
         : m_mapper(mapper)
     {}
 
-    template <typename Ring>
+    template <typename BufferAppender>
     inline void map(PointIn const& ip, PointIn const& vertex,
                 PointIn const& perp1, PointIn const& perp2) const
     {
-        Ring corner;
+        typename BufferAppender::range_type corner;
         corner.push_back(vertex);
         corner.push_back(perp1);
         corner.push_back(ip);
@@ -98,7 +88,7 @@
 };
 #endif
 
-
+// TODO: merge join_miter with join_round, lot of duplicate code
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
 // Forget this, it will go
@@ -122,35 +112,24 @@
     typedef typename coordinate_type<PointIn>::type coordinate_type;
 
 
-    template <typename Ring>
+    template <typename BufferAppender>
     inline void apply(PointIn const& ip, PointIn const& vertex,
                 PointIn const& perp1, PointIn const& perp2,
                 coordinate_type const& buffer_distance,
-                Ring& buffered) const
+                BufferAppender& appender) const
     {
         coordinate_type zero = 0;
-        int signum = buffer_distance > zero
-            ? 1
-            : buffer_distance < zero
-                ? -1
-                : 0;
+        int signum = buffer_distance > zero ? 1
+                   : buffer_distance < zero ? -1
+                   : 0;
 
         if (side::apply(perp1, ip, perp2) == signum)
         {
-
-//#ifdef BOOST_GEOMETRY_BUFFER_NO_HELPER_POINTS
-            // Because perp1 crosses perp2 at IP, it is not necessary to
-            // include IP
-            //buffered.push_back(ip);
-//#else
             // If it is concave (corner to left), add helperline
             // The helper-line IS essential for buffering holes. Without,
             // holes might be generated, while they should NOT be there.
-            // DOES NOT WORK ALWAYS buffered.push_back(ip);
-            // We might consider to make it optional (because more efficient)
-            buffered.push_back(perp1);
-            buffered.push_back(perp2);
-//#endif
+            appender.append(perp1);
+            appender.append(perp2);
         }
         else
         {
@@ -181,14 +160,13 @@
 #endif
             }
 
-            buffered.push_back(p);
+            appender.append(p);
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-            map<Ring>(ip, vertex, perp1, perp2);
+            map<BufferAppender>(ip, vertex, perp1, perp2);
 #endif
         }
 
-
     }
 };
 
@@ -214,17 +192,17 @@
 
     typedef typename coordinate_type<PointIn>::type coordinate_type;
 
-    template <typename Ring>
+    template <typename BufferAppender>
     inline void apply(PointIn const& ip, PointIn const& vertex,
                 PointIn const& perp1, PointIn const& perp2,
                 coordinate_type const& buffer_distance,
-                Ring& buffered) const
+                BufferAppender& appender) const
     {
-        buffered.push_back(perp1);
-        buffered.push_back(perp2);
+        appender.append(perp1);
+        appender.append(perp2);
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-            map<Ring>(ip, vertex, perp1, perp2);
+            map<BufferAppender>(ip, vertex, perp1, perp2);
 #endif
     }
 };
@@ -259,11 +237,11 @@
     int m_max_level;
 
 
-    template <typename Ring>
+    template <typename BufferAppender>
     inline void mid_points(PointIn const& vertex,
                 PointIn const& p1, PointIn const& p2,
                 coordinate_type const& buffer_distance,
-                Ring& buffered,
+                BufferAppender& appender,
                 int level = 1) const
     {
         // Generate 'vectors'
@@ -288,39 +266,33 @@
 
         if (level < m_max_level)
         {
-            mid_points(vertex, p1, mid_point, buffer_distance, buffered, level + 1);
+            mid_points(vertex, p1, mid_point, buffer_distance, appender, level + 1);
         }
-        buffered.push_back(mid_point);
+        appender.append(mid_point);
         if (level < m_max_level)
         {
-            mid_points(vertex, mid_point, p2, buffer_distance, buffered, level + 1);
+            mid_points(vertex, mid_point, p2, buffer_distance, appender, level + 1);
         }
 
     }
 
 
-    template <typename Ring>
+    template <typename BufferAppender>
     inline void apply(PointIn const& ip, PointIn const& vertex,
                 PointIn const& perp1, PointIn const& perp2,
                 coordinate_type const& buffer_distance,
-                Ring& buffered) const
+                BufferAppender& appender) const
     {
         coordinate_type zero = 0;
-        int signum = buffer_distance > zero
-            ? 1
-            : buffer_distance < zero
-                ? -1
-                : 0;
+        int signum = buffer_distance > zero ? 1
+                   : buffer_distance < zero ? -1
+                   : 0;
 
         if (side::apply(perp1, ip, perp2) == signum)
         {
-//#ifdef BOOST_GEOMETRY_BUFFER_NO_HELPER_POINTS
-//            buffered.push_back(ip);
-//#else
             // If it is concave (corner to left), add helperline
-            buffered.push_back(perp1);
-            buffered.push_back(perp2);
-//#endif
+            appender.append(perp1);
+            appender.append(perp2);
         }
         else
         {
@@ -340,23 +312,23 @@
 
             if (m_max_level <= 1)
             {
-                buffered.push_back(perp1);
+                appender.append(perp1);
                 if (m_max_level == 1)
                 {
-                    buffered.push_back(bp);
+                    appender.append(bp);
                 }
-                buffered.push_back(perp2);
+                appender.append(perp2);
             }
             else
             {
-                buffered.push_back(perp1);
-                mid_points(vertex, perp1, bp, bd, buffered);
-                mid_points(vertex, bp, perp2, bd, buffered);
-                buffered.push_back(perp2);
+                appender.append(perp1);
+                mid_points(vertex, perp1, bp, bd, appender);
+                mid_points(vertex, bp, perp2, bd, appender);
+                appender.append(perp2);
             }
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-            map<Ring>(bp, vertex, perp1, perp2);
+            map<BufferAppender>(bp, vertex, perp1, perp2);
 #endif
         }
     }

Modified: trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp
==============================================================================
--- trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp	(original)
+++ trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp	2012-01-24 18:04:30 EST (Tue, 24 Jan 2012)
@@ -151,9 +151,9 @@
 
     std::vector<GeometryOut> buffered;
 
+    GeometryOut buffered_step1;
 #ifdef BOOST_GEOMETRY_TEST_BUFFER_POLYGON
     {
-        GeometryOut buffered_step1;
         bg::detail::buffer::polygon_buffer
             <
                 Geometry, GeometryOut, distance_strategy_type, join_strategy_type
@@ -164,21 +164,13 @@
                             , mapper
 #endif
                                     );
-        buffered.push_back(buffered_step1);
     }
 #else
     {
-        typedef bg::detail::buffer::intersecting_inserter
-            <
-                std::vector<GeometryOut>
-            > inserter_type;
-
-        inserter_type inserter(buffered);
-
         bg::detail::buffer::linestring_buffer
             <
                 Geometry, GeometryOut, distance_strategy_type, join_strategy_type
-            >::apply(geometry, inserter, distance_strategy,
+            >::apply(geometry, buffered_step1, distance_strategy,
                             join_strategy
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
                             , mapper
@@ -186,6 +178,7 @@
                                     );
     }
 #endif
+    buffered.push_back(buffered_step1);
 
     //std::cout << caseid << std::endl;
     //std::cout << "INPUT: " << bg::wkt(geometry) << std::endl;