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

Subject: [Boost-commit] svn:boost r76717 - in trunk/boost/geometry/extensions: algorithms/buffer strategies
From: barend.gehrels_at_[hidden]
Date: 2012-01-27 12:03:00

Author: barendgehrels
Date: 2012-01-27 12:02:59 EST (Fri, 27 Jan 2012)
New Revision: 76717
URL: http://svn.boost.org/trac/boost/changeset/76717

Log:
Update in extensions: buffer. Reworked appender, now correctly buffers all saw/bowls (but not yet indentations and many others)

Text files modified: 
   trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp |   144 ++++++++++++++++++++++++++++----------- 
   trunk/boost/geometry/extensions/strategies/buffer.hpp                 |     2                                         
   2 files changed, 104 insertions(+), 42 deletions(-)

Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp	2012-01-27 12:02:59 EST (Fri, 27 Jan 2012)
@@ -11,6 +11,7 @@
 
 
 #include <cstddef>
+#include <deque>
 
 #include <boost/range.hpp>
 
@@ -52,9 +53,6 @@
                 > policy;
 
 
-    int m_index_begin_join;
-    int m_index_end_hooklet;
-    int m_index_begin_hooklet;
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
     Mapper const& m_mapper;
@@ -66,26 +64,33 @@
         : m_range(r)
 #endif
 
-        , m_index_begin_join(-1)
-        , m_index_end_hooklet(-1)
-        , m_index_begin_hooklet(-1)
     {}
 
     inline void append(point_type const& point)
     {
-        m_range.push_back(point);
-        m_index_end_hooklet = -1;
-        m_index_begin_hooklet = -1;
+        if (! m_pieces.empty())
+        {
+            check(point);
+        }
+        do_append(point);
     }
 
-    inline void append_end_hooklet(point_type const& point)
+    inline void append_begin_join(point_type const& point)
     {
+        if (! check(point))
+        {
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-        const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(0,0,255);", 4);
+            const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(0,255,0);", 5);
 #endif
+        }
 
-        m_index_end_hooklet = boost::size(m_range);
-        m_range.push_back(point);
+        int index = do_append(point);
+        m_pieces.push_back(piece(index));
+    }
+
+    inline void append_end_join(point_type const& point)
+    {
+        do_append(point);
     }
 
     inline void append_begin_hooklet(point_type const& point)
@@ -93,66 +98,123 @@
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
         const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(0,0,192);", 3);
 #endif
-        if (m_index_begin_hooklet > 0)
+
+        check(point);
+
+        int index = do_append(point);
+        if (!m_pieces.empty() && m_pieces.back().end == -1)
         {
-            calculate(point, m_index_begin_hooklet - 1, boost::size(m_range) - 1);
+            m_pieces.back().end = index;
         }
-
-        m_index_begin_hooklet = boost::size(m_range);
-        m_range.push_back(point);
     }
 
-    inline void append_begin_join(point_type const& point)
+    inline void append_end_hooklet(point_type const& point)
     {
-        if (m_index_begin_join >= 0 && m_index_end_hooklet >= 0)
-        {
-            calculate(point, m_index_begin_join, m_index_end_hooklet);
-        }
-        else
-        {
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-            const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(0,255,0);", 5);
+        const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(0,0,255);", 4);
 #endif
-        }
 
-        m_index_begin_join = boost::size(m_range);
-        m_range.push_back(point);
+        int index = do_append(point);
     }
 
 
 private :
+
+    struct piece
+    {
+        int begin, end;
+
+        inline piece(int b = -1)
+            : begin(b)
+            , end(-1)
+        {}
+    };
+
     Range& m_range;
+    point_type m_previous_point;
+    std::deque<piece> m_pieces;
 
-    inline bool calculate(point_type const& point, int begin, int end)
+    inline int do_append(point_type const& point)
     {
+        //check(point);
+        int result = boost::size(m_range);
+        m_range.push_back(point);
+        m_previous_point = point;
+        return result;
+    }
+
+    inline bool check(point_type const& point)
+    {
+        for (std::deque<piece>::reverse_iterator rit 
+                    = m_pieces.rbegin();
+            rit != m_pieces.rend();
+            ++rit)
+        {
+            if (rit->end >= rit->begin)
+            {
+                if (calculate(point, *rit))
+                {
+                    // We HAVE to leave here 
+                    // because the deque is cleared in between
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    inline bool calculate(point_type const& point, piece& the_piece)
+    {
+        int const n = boost::size(m_range);
+
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
         const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(255,0,0);", 4);
-        for (int i = begin; i < end; i++)
+        for (int i = the_piece.begin; i <= the_piece.end && i < n; i++)
         {
             //const_cast<Mapper&>(m_mapper).map(m_range[i], "fill:rgb(0,255,255);", 3);
         }
 #endif
 
-        segment_type segment1(m_range[end], point);
-
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-        //const_cast<Mapper&>(m_mapper).map(segment1, "stroke:rgb(0,255,255);stroke-width:4");
-#endif
+        segment_type segment1(m_previous_point, point);
 
-        for (int i = begin; i < end - 1; i++)
+        for (int i = the_piece.begin;
+            i < the_piece.end && i + 1 < n;
+            i++)
         {
             segment_type segment2(m_range[i], m_range[i + 1]);
-            segment_intersection_points<point_type> is = policy::apply(segment1, segment2);
-            if (is.count > 0)
+            segment_intersection_points<point_type> is 
+                = policy::apply(segment1, segment2);
+            if (is.count == 1)
             {
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
                 const_cast<Mapper&>(m_mapper).map(is.intersections[0], "fill:rgb(255,0,255);", 4);
+
+                // Draw red line of cut-off piece
+                model::linestring<point_type> temp;
+                temp.push_back(is.intersections[0]);
+                for (int j = i + 1; j < n; j++)
+                {
+                    temp.push_back(m_range[j]);
+                }
+                temp.push_back(is.intersections[0]);
+                const_cast<Mapper&>(m_mapper).map(temp, "fill:none;stroke:rgb(255,0,0);stroke-width:2");
+
 #endif
 
                 // Remove all points until this point, and add intersection point.
                 m_range.resize(i + 1);
-                m_range.push_back(is.intersections[0]);
-                m_index_end_hooklet = -1;
+
+                // Add this IP also as first point on the deque.
+                // We clear the deque - the indexes might be invalidated anyway
+                int index = do_append(is.intersections[0]);
+
+                // For many the index of intersection point is OK, but
+                // for bowls >= 6 (see test-program) we need to intersect with the same segment again:
+                index = the_piece.begin;
+
+                m_pieces.resize(0);
+                m_pieces.push_back(piece(index));
+
                 return true;
             }
         }

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-27 12:02:59 EST (Fri, 27 Jan 2012)
@@ -323,7 +323,7 @@
                 mid_points(vertex, perp1, bp, bd, appender);
                 mid_points(vertex, bp, perp2, bd, appender);
             }
-            appender.append(perp2);
+            appender.append_end_join(perp2);
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
             map<BufferAppender>(bp, vertex, perp1, perp2);