[Boost-commit] svn:boost r60578 - in sandbox/geometry/boost/geometry: algorithms multi/algorithms

Subject: [Boost-commit] svn:boost r60578 - in sandbox/geometry/boost/geometry: algorithms multi/algorithms
From: barend.gehrels_at_[hidden]
Date: 2010-03-14 10:30:07

Author: barendgehrels
Date: 2010-03-14 10:30:06 EDT (Sun, 14 Mar 2010)
New Revision: 60578
URL: http://svn.boost.org/trac/boost/changeset/60578

Log:
Updated dissolve ("dissolve" renamed to "dissolve_inserter", added free function "dissolve")
Added dissolve for multipolygons
Text files modified: 
   sandbox/geometry/boost/geometry/algorithms/dissolve.hpp       |   147 +++++++++++++++++++++++---------------- 
   sandbox/geometry/boost/geometry/multi/algorithms/dissolve.hpp |    83 +++++++++++++++++++---                  
   2 files changed, 158 insertions(+), 72 deletions(-)

Modified: sandbox/geometry/boost/geometry/algorithms/dissolve.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/dissolve.hpp	(original)
+++ sandbox/geometry/boost/geometry/algorithms/dissolve.hpp	2010-03-14 10:30:06 EDT (Sun, 14 Mar 2010)
@@ -23,7 +23,7 @@
 #include <boost/geometry/algorithms/overlay/traverse.hpp>
 #include <boost/geometry/algorithms/overlay/assemble.hpp>
 
-#include <boost/geometry/strategies/area_result.hpp>
+#include <boost/geometry/algorithms/convert.hpp>
 
 #include <boost/geometry/geometries/concepts/check.hpp>
 
@@ -37,9 +37,10 @@
 {
 
 
-template <typename Geometry, typename OutputIterator>
-struct dissolve_region
+template <typename Geometry, typename GeometryOut>
+struct dissolve_ring_or_polygon
 {
+	template <typename OutputIterator>
     static inline OutputIterator apply(Geometry const& geometry,
                 OutputIterator out)
     {
@@ -56,32 +57,43 @@
                 detail::overlay::calculate_distance_policy
             >(geometry, turns, policy);
 
+		// The dissolve process is not necessary if there are no turns at all
 
-        typedef typename ring_type<Geometry>::type ring_type;
-        typedef std::vector<ring_type> out_vector;
-        out_vector rings;
-
-        // Enrich the turns
-        typedef typename strategy_side
-        <
-            typename cs_tag<Geometry>::type
-        >::type side_strategy_type;
-
-        enrich_intersection_points(turns, geometry, geometry,
-                    side_strategy_type());
-
-
-        // Traverse the polygons twice in two different directions
-        traverse(geometry, geometry, detail::overlay::operation_union,
-                        turns, rings);
-
-        clear_visit_info(turns);
-
-        traverse(geometry, geometry, detail::overlay::operation_intersection,
-                        turns, rings);
-
-        return detail::overlay::assemble<Geometry>(rings, turns,
-                        geometry, geometry, 1, true, out);
+		if (boost::size(turns) > 0)
+		{
+			typedef typename ring_type<Geometry>::type ring_type;
+			typedef std::vector<ring_type> out_vector;
+			out_vector rings;
+
+			// Enrich the turns
+			typedef typename strategy_side
+			<
+				typename cs_tag<Geometry>::type
+			>::type side_strategy_type;
+
+			enrich_intersection_points(turns, geometry, geometry,
+						side_strategy_type());
+
+
+			// Traverse the polygons twice in two different directions
+			traverse(geometry, geometry, detail::overlay::operation_union,
+							turns, rings);
+
+			clear_visit_info(turns);
+
+			traverse(geometry, geometry, detail::overlay::operation_intersection,
+							turns, rings);
+
+			return detail::overlay::assemble<GeometryOut>(rings, turns,
+							geometry, geometry, 1, true, out);
+		}
+		else
+		{
+			GeometryOut g;
+			geometry::convert(geometry, g);
+			*out++ = g;
+			return out;
+		}
     }
 };
 
@@ -97,41 +109,24 @@
 
 template
 <
-    typename GeometryTag,
-    typename Geometry,
-    typename OutputIterator
+	typename GeometryTag, 
+	typename GeometryOutTag, 
+	typename Geometry, 
+	typename GeometryOut
 >
 struct dissolve
 {};
 
 
-template
-<
-    typename Polygon,
-    typename OutputIterator
->
-struct dissolve
-    <
-        polygon_tag,
-        Polygon,
-        OutputIterator
-    >
-    : detail::dissolve::dissolve_region<Polygon, OutputIterator>
+template<typename Polygon, typename PolygonOut>
+struct dissolve<polygon_tag, polygon_tag, Polygon, PolygonOut>
+    : detail::dissolve::dissolve_ring_or_polygon<Polygon, PolygonOut>
 {};
 
 
-template
-<
-    typename Ring,
-    typename OutputIterator
->
-struct dissolve
-    <
-        ring_tag,
-        Ring,
-        OutputIterator
-    >
-    : detail::dissolve::dissolve_region<Ring, OutputIterator>
+template<typename Ring, typename RingOut>
+struct dissolve<ring_tag, ring_tag, Ring, RingOut>
+    : detail::dissolve::dissolve_ring_or_polygon<Ring, RingOut>
 {};
 
 
@@ -147,27 +142,59 @@
     \tparam OutputIterator type of intersection container
         (e.g. vector of "intersection/turn point"'s)
     \param geometry first geometry
-    \param output container which will contain intersection points
+    \param output container which will contain dissolved geometry
  */
 template
 <
+    typename GeometryOut,
     typename Geometry,
     typename OutputIterator
 >
-inline OutputIterator dissolve(Geometry const& geometry, OutputIterator output)
+inline OutputIterator dissolve_inserter(Geometry const& geometry, OutputIterator out)
 {
     concept::check<Geometry const>();
-
+    concept::check<GeometryOut>();
 
     return dispatch::dissolve
     <
         typename tag<Geometry>::type,
+		typename tag<GeometryOut>::type,
+        Geometry,
+		GeometryOut
+    >::apply(geometry, out);
+}
+
+
+template
+<
+    typename Geometry,
+    typename GeometryOut
+>
+inline void dissolve(Geometry const& geometry, GeometryOut& out)
+{
+    concept::check<Geometry const>();
+    concept::check<GeometryOut>();
+
+	std::vector<GeometryOut> v;
+    dispatch::dissolve
+    <
+        typename tag<Geometry>::type,
+		typename tag<GeometryOut>::type,
         Geometry,
-        OutputIterator
-    >::apply(geometry, output);
+		GeometryOut
+	>::apply(geometry, std::back_inserter(v));
+	if (boost::size(v) > 0)
+	{
+		out = v.front();
+	}
+	else
+	{
+		out = geometry;
+	}
 }
 
 
+
 }} // namespace boost::geometry
 
 #endif // BOOST_GEOMETRY_ALGORITHMS_DISSOLVE_HPP

Modified: sandbox/geometry/boost/geometry/multi/algorithms/dissolve.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/multi/algorithms/dissolve.hpp	(original)
+++ sandbox/geometry/boost/geometry/multi/algorithms/dissolve.hpp	2010-03-14 10:30:06 EDT (Sun, 14 Mar 2010)
@@ -17,23 +17,82 @@
 {
 
 
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace dissolve
+{
+
+template <typename Multi, typename MultiOut>
+struct dissolve_multi
+{
+	template <typename OutputIterator>
+    static inline OutputIterator apply(Multi const& multi, OutputIterator out)
+    {
+		typedef typename boost::range_value<Multi>::type polygon_type;
+		typedef typename boost::range_value<MultiOut>::type output_polygon_type;
+		typedef typename boost::range_iterator<Multi const>::type iterator_type;
+		
+		// Step 1: dissolve all polygons in the multi-polygon, independantly
+		MultiOut step1;
+        for (iterator_type it = boost::begin(multi);
+            it != boost::end(multi);
+            ++it)
+        {
+			dissolve_ring_or_polygon
+				<
+					polygon_type,
+					output_polygon_type
+				>::apply(*it, std::back_inserter(step1));
+		}
+
+		// Step 2: remove mutual overlap
+		// TODO: solve quadratic behaviour by alternating division in x/y axis
+		// per division there are 3 cases: cases above the line, cases below the line, cases crossing the line
+		// recursively handle those 3 cases and union them.
+		MultiOut step2;
+        for (iterator_type it = boost::begin(step1);
+            it != boost::end(step1);
+            ++it)
+        {
+			if (step2.empty())
+			{
+				step2.push_back(*it);
+			}
+			else
+			{
+				MultiOut unioned;
+				for (iterator_type it2 = boost::begin(step2);
+					it2 != boost::end(step2);
+					++it2)
+				{
+					geometry::union_inserter
+						<
+							output_polygon_type
+						>(*it2, *it, std::back_inserter(unioned));
+				}
+				step2.swap(unioned);
+			}
+		}
+
+		// Step 3: output
+		*out++ = step2;
+		return out;
+	}
+};
+
+
+}} // namespace detail::dissolve
+#endif
+
+
+
 #ifndef DOXYGEN_NO_DISPATCH
 namespace dispatch
 {
 
 
-template
-<
-    typename Multi,
-    typename OutputIterator
->
-struct dissolve
-    <
-        multi_polygon_tag,
-        Multi,
-        OutputIterator
-    >
-    : detail::dissolve::dissolve_region<Multi, OutputIterator>
+template<typename Multi, typename MultiOut>
+struct dissolve<multi_polygon_tag, multi_polygon_tag, Multi, MultiOut>
+    : detail::dissolve::dissolve_multi<Multi, MultiOut>
 {};