[Boost-commit] svn:boost r77227 - in trunk/boost/geometry: algorithms/detail extensions/algorithms/buffer

Subject: [Boost-commit] svn:boost r77227 - in trunk/boost/geometry: algorithms/detail extensions/algorithms/buffer
From: barend.gehrels_at_[hidden]
Date: 2012-03-05 09:07:54

Author: barendgehrels
Date: 2012-03-05 09:07:53 EST (Mon, 05 Mar 2012)
New Revision: 77227
URL: http://svn.boost.org/trac/boost/changeset/77227

Log:
[geometry] buffer, extracted occupation info to separate file
Added:
   trunk/boost/geometry/algorithms/detail/occupation_info.hpp   (contents, props changed)
Text files modified: 
   trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp                       |     4                                         
   trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp             |   235 ++++++++------------------------------- 
   trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection_with_mapper.hpp |     2                                         
   3 files changed, 52 insertions(+), 189 deletions(-)

Added: trunk/boost/geometry/algorithms/detail/occupation_info.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/geometry/algorithms/detail/occupation_info.hpp	2012-03-05 09:07:53 EST (Mon, 05 Mar 2012)
@@ -0,0 +1,211 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+
+// Copyright (c) 2012 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_OCCUPATION_INFO_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
+
+
+#include <algorithm>
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/coordinate_type.hpp>
+#include <boost/geometry/core/point_type.hpp>
+
+#include <boost/geometry/algorithms/equals.hpp>
+#include <boost/geometry/iterators/closing_iterator.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail
+{
+
+template <typename T, typename P1, typename P2>
+inline T calculate_angle(P1 const& from_point, P2 const& to_point)
+{
+    typedef P1 vector_type;
+    vector_type v = from_point;
+    geometry::subtract_point(v, to_point);
+    return atan2(geometry::get<1>(v), geometry::get<0>(v));
+}
+
+template <typename Iterator, typename Vector>
+inline Iterator advance_circular(Iterator it, Vector const& vector, bool forward = true)
+{
+	int const increment = forward ? 1 : -1;
+	if (it == boost::begin(vector) && increment < 0)
+	{
+		it = boost::end(vector);
+	}
+	it += increment;
+	if (it == boost::end(vector))
+	{
+		it = boost::begin(vector);
+	}
+	return it;
+}
+
+template <typename T>
+struct angle_info
+{
+	typedef T angle_type;
+    T angle;
+    bool incoming;
+};
+
+template <typename AngleInfo>
+class occupation_info
+{
+	typedef std::vector<AngleInfo> collection_type;
+
+	struct angle_sort
+	{
+		inline bool operator()(AngleInfo const& left, AngleInfo const& right) const
+		{
+			// In this case we can compare even double using equals
+			// return geometry::math::equals(left.angle, right.angle)
+			return left.angle == right.angle
+				? int(left.incoming) < int(right.incoming)
+				: left.angle < right.angle
+				;
+		}
+	};
+
+    collection_type angles;
+    bool m_occupied;
+	bool m_calculated;
+
+	inline bool is_occupied()
+	{
+		if (boost::size(angles) <= 1)
+		{
+			return false;
+		}
+
+		std::sort(angles.begin(), angles.end(), angle_sort());
+
+		typedef geometry::closing_iterator<collection_type const> closing_iterator;
+		closing_iterator vit(angles);
+		closing_iterator end(angles, true);
+
+		closing_iterator prev = vit++;
+		for( ; vit != end; prev = vit++)
+		{
+			if (! geometry::math::equals(prev->angle, vit->angle)
+				&& ! prev->incoming
+				&& vit->incoming)
+			{
+				return false;
+			}
+		}
+		return true;
+	}
+
+public :
+    inline occupation_info()
+        : m_occupied(false)
+		, m_calculated(false)
+    {}
+
+	template <typename Point1, typename Point2>
+	inline void add(Point1 const& point1, Point2 const& point2, bool incoming)
+	{
+        AngleInfo info;
+        info.incoming = incoming;
+        info.angle = calculate_angle<typename AngleInfo::angle_type>(point1, point2);
+        angles.push_back(info);
+
+		m_calculated = false;
+	}
+
+	inline bool occupied()
+	{
+		if (! m_calculated)
+		{
+			m_occupied = is_occupied();
+			m_calculated = true;
+		}
+		return m_occupied;
+	}
+
+};
+
+
+template <typename Point, typename Ring, typename Info>
+inline void add_incoming_and_outgoing_angles(Point const& point,
+				Ring const& ring, int segment_index,
+                Info& info)
+{
+    typedef typename boost::range_iterator
+        <
+            Ring const
+        >::type iterator_type;
+
+	int const n = boost::size(ring);
+	if (segment_index >= n || segment_index < 0)
+	{
+		return;
+	}
+
+	iterator_type it = boost::begin(ring) + segment_index;
+
+    if (geometry::equals(point, *it))
+    {
+		it = advance_circular(it, ring, false);
+    }
+
+	info.add(*it, point, true);
+
+	it = advance_circular(it, ring);
+    for (int defensive_check = 0; 
+		geometry::equals(point, *it) && defensive_check < n; 
+		defensive_check++)
+    {
+		it = advance_circular(it, ring);
+    }
+
+	info.add(*it, point, false);
+}
+
+
+// Map in two senses of the word: it is a std::map where the key is a point.
+// Per point an "occupation_info" record is kept
+// Used for the buffer (but will also be used for intersections/unions having complex self-tangencies)
+template <typename Point, typename OccupationInfo>
+class occupation_map
+{
+public :
+    typedef std::map<Point, OccupationInfo, geometry::less<Point> > map_type;
+    map_type map;
+
+    OccupationInfo& find_or_insert(Point point)
+    {
+        typename map_type::iterator it = map.find(point);
+        if (it == boost::end(map))
+        {
+            std::pair<typename map_type::iterator, bool> pair 
+                        = map.insert(std::make_pair(point, OccupationInfo()));
+            it = pair.first;
+        }
+
+        return it->second;
+    }
+
+};
+
+
+} // namespace detail
+#endif // DOXYGEN_NO_DETAIL
+
+
+}} // namespace boost::geometry
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP

Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp	2012-03-05 09:07:53 EST (Mon, 05 Mar 2012)
@@ -111,7 +111,7 @@
     intersection_location_type location;
     
     int count_within, count_on_helper, count_on_offsetted, count_on_corner;
-	int count_on_closed;
+	int count_on_occupied;
     
 #ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
         std::string debug_string;
@@ -124,7 +124,7 @@
         , count_on_helper(0)
         , count_on_offsetted(0)
         , count_on_corner(0)
-		, count_on_closed(0)
+		, count_on_occupied(0)
     {}
 };
 

Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection.hpp	2012-03-05 09:07:53 EST (Mon, 05 Mar 2012)
@@ -27,9 +27,9 @@
 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+#include <boost/geometry/algorithms/detail/occupation_info.hpp>
 #include <boost/geometry/algorithms/detail/partition.hpp>
 
-#include <boost/geometry/iterators/closing_iterator.hpp>
 
 #include <boost/geometry/extensions/algorithms/buffer/buffered_ring.hpp>
 #include <boost/geometry/extensions/algorithms/buffer/buffer_policies.hpp>
@@ -86,65 +86,11 @@
 };
 
 
-// TODO replace double by T
-template <typename P1, typename P2>
-inline double calculate_angle(P1 const& from_point, P2 const& to_point)
-{
-    typedef P1 vector_type;
-    vector_type v = from_point;
-    geometry::subtract_point(v, to_point);
-    return atan2(geometry::get<1>(v), geometry::get<0>(v));
-}
-
-template <typename Iterator, typename Vector>
-inline Iterator advance_circular(Iterator it, Vector const& vector, int increment = 1)
-{
-	if (it == boost::begin(vector) && increment < 0)
-	{
-		it = boost::end(vector);
-	}
-	it += increment;
-	if (it == boost::end(vector))
-	{
-		it = boost::begin(vector);
-	}
-	return it;
-}
-
-
-// BEGIN clustered
-// TODO will be restructured and moved to clustered-manager
-
-struct angle_info
-{
-    double angle; // TODO: T
-    bool incoming;
-
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-    std::string debug_info;
-    bool debug;
-#endif
-
-};
-
-struct cluster_info
-{
-    std::vector<angle_info> angles;
-};
-
-struct buffer_cluster_info : public cluster_info
-{
-    std::set<segment_identifier> seg_ids;
-    std::set<int> turn_indices;
-};
-
-// END clustered
-
-
 template <typename Ring>
 struct buffered_piece_collection
 {
     typedef typename geometry::point_type<Ring>::type point_type;
+    typedef typename geometry::coordinate_type<Ring>::type coordinate_type;
 
     struct piece
     {
@@ -161,6 +107,7 @@
         std::vector<point_type> helper_segments; // 3 points for segment, 2 points for join - 0 points for flat-end
     };
 
+
     typedef typename strategy::side::services::default_strategy
                 <
                         typename cs_tag<point_type>::type
@@ -184,9 +131,26 @@
         // To check clustered locations we keep track of segments being opposite somewhere
         std::set<segment_identifier> m_in_opposite_segments;
 
+	struct buffer_occupation_info : public occupation_info<angle_info<coordinate_type> >
+	{
+		std::set<segment_identifier> seg_ids;
+		std::set<int> turn_indices;
+	};
+
+    typedef occupation_map<point_type, buffer_occupation_info> occupation_map_type;
+    occupation_map_type m_occupation_map;
+
 
-    typedef std::map<point_type, buffer_cluster_info, geometry::less<point_type> > clustered_location_type;
-    clustered_location_type clustered_turn_locations;
+	struct redundant_turn
+	{
+		inline bool operator()(buffer_turn_info<point_type> const& turn) const
+		{
+			// Erase discarded turns (location not OK) and the turns
+			// only used to detect oppositeness.
+			return turn.location != location_ok 
+				|| turn.opposite();
+		}
+	};
 
 
     inline bool is_neighbor(piece const& piece1, piece const& piece2) const
@@ -304,76 +268,20 @@
         return segment_relation_disjoint;
         }
 
-	// TODO will be restructured and moved to clustered-manager
-    inline void get_points(point_type const& point, buffer_turn_operation<point_type> const& operation, angle_info& tp1, angle_info& tp2) const
+    inline void add_angles(int index, point_type const& point, buffer_turn_operation<point_type> const& operation)
     {
-        typedef typename boost::range_iterator
-            <
-                Ring const
-            >::type iterator_type;
-
-        //typedef geometry::ever_circling_iterator<iterator_type> ec_iterator_type;
-
-        std::ostringstream out;
-        out << operation.seg_id.segment_index << "/" << operation.other_id.segment_index << " " << operation_char(operation.operation);
-
-        // Get the vectors (coming in, and going out of this point)
-        buffered_ring<Ring> const& ring = offsetted_rings[operation.seg_id.multi_index];
-
-		iterator_type it = boost::begin(ring) + operation.seg_id.segment_index;
-
-        if (geometry::equals(point, *it))
-        {
-			it = advance_circular(it, ring, -1);
+        buffer_occupation_info& info = m_occupation_map.find_or_insert(point);
+        info.turn_indices.insert(index);
+        if (info.seg_ids.count(operation.seg_id) <= 0)
+        {
+            info.seg_ids.insert(operation.seg_id);
+            add_incoming_and_outgoing_angles(point, 
+						offsetted_rings[operation.seg_id.multi_index], 
+						operation.seg_id.segment_index, 
+						info);
         }
-
-        tp1.incoming = true;
-        tp1.angle = calculate_angle(*it, point);
-
-		it = advance_circular(it, ring);
-		int const n = boost::size(ring);
-        for (int defensive_check = 0; 
-			geometry::equals(point, *it) && defensive_check < n; 
-			defensive_check++)
-        {
-			it = advance_circular(it, ring);
-        }
-
-        tp2.incoming = false;
-        tp2.angle = calculate_angle(*it, point);
-
-#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
-        tp1.debug = operation.seg_id.segment_index == 32;
-        tp1.debug_info = out.str();
-        tp2.debug_info = out.str();
-        tp2.debug = operation.seg_id.segment_index == 32;
-#endif
     }
 
-    inline void add_segment(int index, point_type const& point, buffer_turn_operation<point_type> const& operation)
-    {
-        typename clustered_location_type::iterator it = clustered_turn_locations.find(point);
-        if (it == boost::end(clustered_turn_locations))
-        {
-            buffer_cluster_info a;
-            std::pair<typename clustered_location_type::iterator, bool> pair = clustered_turn_locations.insert(std::make_pair(point, a));
-            it = pair.first;
-        }
-
-        buffer_cluster_info& admin = it->second;
-        admin.turn_indices.insert(index);
-        if (admin.seg_ids.count(operation.seg_id) <= 0)
-        {
-            admin.seg_ids.insert(operation.seg_id);
-
-            angle_info tp[2];
-            get_points(point, operation, tp[0], tp[1]);
-            admin.angles.push_back(tp[0]);
-            admin.angles.push_back(tp[1]);
-        }
-    }
-
-
     inline void classify_turn(buffer_turn_info<point_type>& turn, piece const& pc) const
     {
         if (pc.type == buffered_flat_end)
@@ -459,60 +367,27 @@
             }
         }
     }
-		struct angle_sort
-		{
-			inline bool operator()(angle_info const& left, angle_info const& right) const
-			{
-				return geometry::math::equals(left.angle, right.angle)
-					? int(left.incoming) < int(right.incoming)
-					: left.angle < right.angle
-					;
-			}
-		};
 
-	inline void classify_clustered()
+	inline void classify_occupied_locations()
         {
-
-        for (typename boost::range_iterator<clustered_location_type>::type it =
-	            boost::begin(clustered_turn_locations);
-			it != boost::end(clustered_turn_locations); ++it)
+        for (typename boost::range_iterator<typename occupation_map_type::map_type>::type it =
+	            boost::begin(m_occupation_map.map);
+			it != boost::end(m_occupation_map.map); ++it)
         {
-	        buffer_cluster_info& admin = it->second;
-			if (boost::size(admin.angles) > 1)
+	        buffer_occupation_info& info = it->second;
+			if (info.occupied())
                         {
-				std::sort(admin.angles.begin(), admin.angles.end(), angle_sort());
-
-				// Verify if completely closed
-				bool closed = true;
-
-				typedef geometry::closing_iterator<std::vector<angle_info> const> closing_iterator;
-				closing_iterator vit(admin.angles);
-				closing_iterator end(admin.angles, true);
-
-				closing_iterator prev = vit++;
-				for( ; vit != end && closed; prev = vit++)
-				{
-					if (! geometry::math::equals(prev->angle, vit->angle)
-						&& ! prev->incoming
-						&& vit->incoming)
-					{
-						closed = false;
-					}
-				}
-				if (closed)
+				for (std::set<int>::const_iterator sit = info.turn_indices.begin();
+					sit != info.turn_indices.end();
+					++sit)
                                 {
-					for (std::set<int>::iterator sit = admin.turn_indices.begin();
-						sit != admin.turn_indices.end();
-						++sit)
-					{
-						m_turns[*sit].count_on_closed++;
-					}
+					m_turns[*sit].count_on_occupied++;
                                 }
                         }
         }
         }
 
-	inline void get_clusters()
+	inline void get_occupation()
     {
                 fill_opposite_segments();
 
@@ -524,13 +399,12 @@
                         if (m_in_opposite_segments.count(turn.operations[0].seg_id) > 0
                                 || m_in_opposite_segments.count(turn.operations[1].seg_id) > 0)
                         {
-				add_segment(index, turn.point, turn.operations[0]);
-				add_segment(index, turn.point, turn.operations[1]);
+				add_angles(index, turn.point, turn.operations[0]);
+				add_angles(index, turn.point, turn.operations[1]);
                         }
                 }
         }
 
-
     inline void classify_turns()
     {
 
@@ -540,7 +414,7 @@
         for (typename boost::range_iterator<turn_vector_type>::type it =
             boost::begin(m_turns); it != boost::end(m_turns); ++it)
                 {
-            if (it->count_on_closed == 0)
+            if (it->count_on_occupied == 0)
             {
                 typename std::vector<piece>::const_iterator pit;
                 for (pit = boost::begin(m_pieces);
@@ -558,7 +432,7 @@
         {
             if (it->count_within > 0 
                 || it->count_on_helper > 0
-				|| it->count_on_closed > 0
+				|| it->count_on_occupied > 0
                                 )
             {
                 it->location = inside_buffer;
@@ -608,8 +482,8 @@
             }
         }
 
-		get_clusters();
-        classify_clustered();
+		get_occupation();
+        classify_occupied_locations();
         classify_turns();
 
         if (boost::is_same<typename tag_cast<typename tag<Geometry>::type, areal_tag>::type, areal_tag>())
@@ -754,17 +628,6 @@
             }
         }
     }
-		struct redundant_turn
-		{
-			inline bool operator()(buffer_turn_info<point_type> const& turn) const
-			{
-				// Erase discarded turns (location not OK) and the turns
-				// only used to detect oppositeness.
-				return turn.location != location_ok 
-					|| turn.opposite();
-			}
-		};
-
                     
     inline void discard_turns()
     {

Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection_with_mapper.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection_with_mapper.hpp	(original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffered_piece_collection_with_mapper.hpp	2012-03-05 09:07:53 EST (Mon, 05 Mar 2012)
@@ -122,7 +122,7 @@
                                         << "-" << it->count_on_helper
                                         << "-" << it->count_on_corner
                                         << "-" << it->count_on_offsetted
-					<< "-" << it->count_on_closed
+					<< "-" << it->count_on_occupied
                                         //<< it->debug_string
                                         ;
                                 out << color << std::endl;