Imported Upstream version 1.72.0

[platform/upstream/boost.git] / boost / geometry / algorithms / remove_spikes.hpp

diff --git a/boost/geometry/algorithms/remove_spikes.hpp b/boost/geometry/algorithms/remove_spikes.hpp
index ffc7f7c..307bd2d 100644 (file)
--- a/boost/geometry/algorithms/remove_spikes.hpp
+++ b/boost/geometry/algorithms/remove_spikes.hpp
@@ -84,7 +84,9 @@ struct range_remove_spikes
             return;
         }
 
-        std::deque<point_type> cleaned;
+        std::vector<point_type> cleaned;
+        cleaned.reserve(n);
+
         for (typename boost::range_iterator<Range const>::type it = boost::begin(range);
             it != boost::end(range); ++it)
         {
@@ -102,10 +104,16 @@ struct range_remove_spikes
             }
         }
 
+        typedef typename std::vector<point_type>::iterator cleaned_iterator;
+        cleaned_iterator cleaned_b = cleaned.begin();
+        cleaned_iterator cleaned_e = cleaned.end();
+        std::size_t cleaned_count = cleaned.size();
+
         // For a closed-polygon, remove closing point, this makes checking first point(s) easier and consistent
         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
         {
-            cleaned.pop_back();
+            --cleaned_e;
+            --cleaned_count;
         }
 
         bool found = false;
@@ -113,45 +121,50 @@ struct range_remove_spikes
         {
             found = false;
             // Check for spike in first point
-            int const penultimate = 2;
-            while(cleaned.size() >= 3
-                  && detail::is_spike_or_equal(range::at(cleaned, cleaned.size() - penultimate),
-                                               range::back(cleaned),
-                                               range::front(cleaned),
+            while(cleaned_count >= 3
+                  && detail::is_spike_or_equal(*(cleaned_e - 2), // prev
+                                               *(cleaned_e - 1), // back
+                                               *(cleaned_b),     // front
                                                strategy))
             {
-                cleaned.pop_back();
+                --cleaned_e;
+                --cleaned_count;
                 found = true;
             }
             // Check for spike in second point
-            while(cleaned.size() >= 3
-                  && detail::is_spike_or_equal(range::back(cleaned),
-                                               range::front(cleaned),
-                                               range::at(cleaned, 1),
+            while(cleaned_count >= 3
+                  && detail::is_spike_or_equal(*(cleaned_e - 1), // back
+                                               *(cleaned_b),     // front
+                                               *(cleaned_b + 1), // next
                                                strategy))
             {
-                cleaned.pop_front();
+                ++cleaned_b;
+                --cleaned_count;
                 found = true;
             }
         }
         while (found);
 
-        if (cleaned.size() == 2)
+        if (cleaned_count == 2)
         {
             // Ticket #9871: open polygon with only two points.
             // the second point forms, by definition, a spike
-            cleaned.pop_back();
+            --cleaned_e;
+            //--cleaned_count;
         }
 
         // Close if necessary
         if ( BOOST_GEOMETRY_CONDITION(geometry::closure<Range>::value == geometry::closed) )
         {
-            cleaned.push_back(cleaned.front());
+            BOOST_GEOMETRY_ASSERT(cleaned_e != cleaned.end());
+            *cleaned_e = *cleaned_b;
+            ++cleaned_e;
+            //++cleaned_count;
         }
 
         // Copy output
         geometry::clear(range);
-        std::copy(cleaned.begin(), cleaned.end(), range::back_inserter(range));
+        std::copy(cleaned_b, cleaned_e, range::back_inserter(range));
     }
 };