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

Subject: [Boost-commit] svn:boost r73318 - trunk/boost/geometry/algorithms/detail/overlay
From: barend.gehrels_at_[hidden]
Date: 2011-07-24 04:49:14

Author: barendgehrels
Date: 2011-07-24 04:49:13 EDT (Sun, 24 Jul 2011)
New Revision: 73318
URL: http://svn.boost.org/trac/boost/changeset/73318

Log:
Enhancement: intersection/union/difference create a unique output set now, by checking just before appending each point
Added:
   trunk/boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp |     7 ++++---                                 
   trunk/boost/geometry/algorithms/detail/overlay/copy_segments.hpp   |    11 ++++-------                             
   trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp        |    15 +++++++++++----                         
   3 files changed, 19 insertions(+), 14 deletions(-)

Added: trunk/boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp	2011-07-24 04:49:13 EDT (Sun, 24 Jul 2011)
@@ -0,0 +1,53 @@
+// 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_APPEND_NO_DUPLICATES_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_APPEND_NO_DUPLICATES_HPP
+
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/algorithms/append.hpp>
+#include <boost/geometry/algorithms/detail/disjoint.hpp>
+
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace overlay
+{
+
+template <typename Range, typename Point>
+inline void append_no_duplicates(Range& range, Point const& point, bool force = false)
+{
+    if (boost::size(range) == 0
+        || force 
+        || ! geometry::detail::equals::equals_point_point(*(boost::end(range)-1), point))
+    {
+#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
+        std::cout << "  add: ("
+            << geometry::get<0>(point) << ", " << geometry::get<1>(point) << ")"
+            << std::endl;
+#endif
+        geometry::append(range, point);
+    }
+}
+
+
+}} // namespace detail::overlay
+#endif // DOXYGEN_NO_DETAIL
+
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_APPEND_NO_DUPLICATES_HPP

Modified: trunk/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/clip_linestring.hpp	2011-07-24 04:49:13 EDT (Sun, 24 Jul 2011)
@@ -11,10 +11,11 @@
 
 #include <boost/range.hpp>
 
-#include <boost/geometry/algorithms/append.hpp>
 #include <boost/geometry/algorithms/clear.hpp>
 #include <boost/geometry/algorithms/convert.hpp>
 
+#include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
+
 #include <boost/geometry/util/select_coordinate_type.hpp>
 #include <boost/geometry/geometries/segment.hpp>
 
@@ -215,9 +216,9 @@
             // b. Add p1 only if it is the first point, then add p2
             if (boost::empty(line_out))
             {
-                geometry::append(line_out, p1);
+                detail::overlay::append_no_duplicates(line_out, p1, true);
             }
-            geometry::append(line_out, p2);
+            detail::overlay::append_no_duplicates(line_out, p2);
 
             // c. If c2 is clipped, finish the line
             if (c2)

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-07-24 04:49:13 EDT (Sun, 24 Jul 2011)
@@ -27,6 +27,7 @@
 #include <boost/geometry/views/closeable_view.hpp>
 #include <boost/geometry/views/reversible_view.hpp>
 
+#include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
 
 namespace boost { namespace geometry
 {
@@ -92,12 +93,7 @@
 
         for (size_type i = 0; i < count; ++i, ++it)
         {
-#ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
-            std::cout << "  add: ("
-                << geometry::get<0>(*it) << ", " << geometry::get<1>(*it) << ")"
-                << std::endl;
-#endif
-            geometry::append(current_output, *it);
+            detail::overlay::append_no_duplicates(current_output, *it);
         }
     }
 };
@@ -164,7 +160,8 @@
         //    (see comments in ring-version)
         for (int i = 0; i < count; i++, index++)
         {
-            geometry::append(current_output, bp[index % 5]);
+            detail::overlay::append_no_duplicates(current_output, bp[index % 5]);
+
         }
     }
 };

Modified: trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp
==============================================================================
--- trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp	(original)
+++ trunk/boost/geometry/algorithms/detail/overlay/traverse.hpp	2011-07-24 04:49:13 EDT (Sun, 24 Jul 2011)
@@ -14,6 +14,7 @@
 
 #include <boost/range.hpp>
 
+#include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
 #include <boost/geometry/core/access.hpp>
@@ -38,7 +39,8 @@
 {
 
 template <typename Turn, typename Operation>
-inline void debug_traverse(Turn const& turn, Operation op, std::string const& header)
+inline void debug_traverse(Turn const& turn, Operation op, 
+                std::string const& header)
 {
 #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
     std::cout << header
@@ -125,7 +127,11 @@
     // If there is no next IP on this segment
     if (info.enriched.next_ip_index < 0)
     {
-        if (info.enriched.travels_to_vertex_index < 0 || info.enriched.travels_to_ip_index < 0) return false;
+        if (info.enriched.travels_to_vertex_index < 0 
+            || info.enriched.travels_to_ip_index < 0)
+        {
+            return false;
+        }
 
         BOOST_ASSERT(info.enriched.travels_to_vertex_index >= 0);
         BOOST_ASSERT(info.enriched.travels_to_ip_index >= 0);
@@ -151,7 +157,7 @@
         seg_id = info.seg_id;
     }
 
-    geometry::append(current_output, ip->point);
+    detail::overlay::append_no_duplicates(current_output, ip->point);
     return true;
 }
 
@@ -348,7 +354,8 @@
                         set_visited_for_continue(*it, *iit);
 
                         typename boost::range_value<Rings>::type current_output;
-                        geometry::append(current_output, it->point);
+                        detail::overlay::append_no_duplicates(current_output, 
+                                    it->point, true);
 
                         turn_iterator current = it;
                         turn_operation_iterator_type current_iit = iit;