[Boost-commit] svn:boost r76771 - trunk/boost/geometry/extensions/algorithms/buffer

Subject: [Boost-commit] svn:boost r76771 - trunk/boost/geometry/extensions/algorithms/buffer
From: barend.gehrels_at_[hidden]
Date: 2012-01-29 05:58:36

Author: barendgehrels
Date: 2012-01-29 05:58:35 EST (Sun, 29 Jan 2012)
New Revision: 76771
URL: http://svn.boost.org/trac/boost/changeset/76771

Log:
Check on positive area of split off rings, further moved/renamed things and prepared for next phase
Text files modified: 
   trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp |   141 ++++++++++++++++++++++----------------- 
   1 files changed, 80 insertions(+), 61 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-29 05:58:35 EST (Sun, 29 Jan 2012)
@@ -36,23 +36,11 @@
         , typename Mapper
 #endif
     >
-struct buffer_appender
+class buffer_appender
 {
+public :
     typedef Range range_type;
-
     typedef typename geometry::point_type<Range>::type point_type;
-    typedef model::referring_segment<const point_type> segment_type;
-    typedef strategy::intersection::relate_cartesian_segments
-                <
-                    policies::relate::segments_intersection_points
-                        <
-                            segment_type,
-                            segment_type,
-                            segment_intersection_points<point_type>
-                        >
-                > policy;
-
-
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
     Mapper const& m_mapper;
@@ -77,12 +65,7 @@
 
     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,255,0);", 5);
-#endif
-        }
+        check(point);
 
         cleanup();
 
@@ -122,11 +105,24 @@
 
 private :
 
+    typedef model::referring_segment<const point_type> segment_type;
+    typedef strategy::intersection::relate_cartesian_segments
+                <
+                    policies::relate::segments_intersection_points
+                        <
+                            segment_type,
+                            segment_type,
+                            segment_intersection_points<point_type>
+                        >
+                > policy;
+
     struct piece
     {
         char type; // For DEBUG, this will either go or changed into enum
         int begin, end;
 
+        Range split_off;
+
         inline piece(char t = '\0', int b = -1, int e = -1)
             : type(t)
             , begin(b)
@@ -147,29 +143,34 @@
         return result;
     }
 
-    inline bool check(point_type const& point)
+    inline void check(point_type const& point)
     {
         for (typename std::deque<piece>::const_reverse_iterator rit 
                     = m_pieces.rbegin();
             rit != m_pieces.rend();
             ++rit)
         {
-            if (rit->end >= rit->begin)
+            if (rit->end >= rit->begin
+                && calculate_ip(point, *rit))
             {
-                if (calculate(point, *rit))
-                {
-                    // We HAVE to leave here 
-                    // because the deque is cleared in between
-                    return true;
-                }
+                // We HAVE to leave here 
+                // because the deque is cleared in between
+                return;
             }
+
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+            const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(0,255,0);", 5);
+#endif
         }
-        return false;
     }
 
-    inline bool calculate(point_type const& point, piece const& the_piece)
+    inline bool calculate_ip(point_type const& point, piece const& the_piece)
     {
         int const n = boost::size(m_range);
+        if (the_piece.end >= n)
+        {
+            return false;
+        }
 
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
         const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(255,0,0);", 4);
@@ -181,44 +182,24 @@
 
         segment_type segment1(m_previous_point, point);
 
-        for (int i = the_piece.begin;
-            i < the_piece.end && i + 1 < n;
-            i++)
+        // Walk backwards through list (chance is higher to have IP at the end)
+        for (int i = the_piece.end - 1; i >= the_piece.begin; i--)
         {
             segment_type segment2(m_range[i], m_range[i + 1]);
             segment_intersection_points<point_type> is 
-                = policy::apply(segment1, segment2);
+                                    = 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++)
+                Range split_off;
+                if (get_valid_split(is.intersections[0], i + 1, split_off))
                 {
-                    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");
+                    add_ip(is.intersections[0], i + 1, the_piece, split_off);
 
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+                    const_cast<Mapper&>(m_mapper).map(is.intersections[0], "fill:rgb(255,0,255);", 4);
+                    const_cast<Mapper&>(m_mapper).map(split_off, "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);
-
-                // Add this IP also as first point on the deque.
-                // We clear the deque - the indexes might be invalidated anyway
-                int is_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:
-                int begin_index = the_piece.begin;
-
-                m_pieces.resize(0);
-                m_pieces.push_back(piece('F', begin_index, is_index));
-                m_pieces.push_back(piece('I', is_index));
+                }
 
                 return true;
             }
@@ -226,7 +207,45 @@
         return false;
     }
 
-    void cleanup()
+    inline bool get_valid_split(point_type const& ip, int index, Range& split_off)
+    {
+        int const n = boost::size(m_range);
+        split_off.push_back(ip);
+        for (int j = index; j < n; j++)
+        {
+            split_off.push_back(m_range[j]);
+        }
+        split_off.push_back(ip);
+
+        typename default_area_result<Range>::type area = geometry::area(split_off);
+        if (area <= 0)
+        {
+            m_pieces.resize(0);
+            return false;
+        }
+        return true;
+    }
+
+    inline void add_ip(point_type const& ip, int index,
+                piece const& the_piece, Range const& split_off)
+    {
+        // Remove all points until this point, and add intersection point.
+        m_range.resize(index);
+        int ip_index = do_append(ip);
+
+        // We first clear the piece list
+        m_pieces.resize(0);
+
+        // Add piece-with-intersection again (e.g. for #bowls >= 6 in unit tests)
+        m_pieces.push_back(piece('F', the_piece.begin, ip_index));
+
+        // Add IP as new starting point and include the cut-off piece
+        // (we might intersect with that as well)
+        m_pieces.push_back(piece('I', ip_index));
+        m_pieces.back().split_off = split_off;
+    }
+
+    inline void cleanup()
     {
         if (m_pieces.size() > 0 && m_pieces.back().end == -1)
         {