Boost logo

Boost-Commit :

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;


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk