Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@16: // Copyright (c) 2012 Barend Gehrels, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
Chris@16: #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP
Chris@16: 
Chris@16: #if ! defined(NDEBUG)
Chris@16: //  #define BOOST_GEOMETRY_DEBUG_BUFFER_OCCUPATION
Chris@16: #endif
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <boost/range.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/core/coordinate_type.hpp>
Chris@16: #include <boost/geometry/core/point_type.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/equals.hpp>
Chris@16: #include <boost/geometry/iterators/closing_iterator.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/algorithms/detail/get_left_turns.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_DETAIL
Chris@16: namespace detail
Chris@16: {
Chris@16: 
Chris@16: template <typename P>
Chris@16: class relaxed_less
Chris@16: {
Chris@16:     typedef typename geometry::coordinate_type<P>::type coordinate_type;
Chris@16: 
Chris@16:     coordinate_type epsilon;
Chris@16: 
Chris@16: public :
Chris@16: 
Chris@16:     inline relaxed_less()
Chris@16:     {
Chris@16:         // TODO: adapt for ttmath, and maybe build the map in another way 
Chris@16:         // (e.g. exact constellations of segment-id's), maybe adaptive.
Chris@16:         epsilon = std::numeric_limits<double>::epsilon() * 100.0;
Chris@16:     }
Chris@16: 
Chris@16:     inline bool operator()(P const& a, P const& b) const
Chris@16:     {
Chris@16:         coordinate_type const dx = math::abs(geometry::get<0>(a) - geometry::get<0>(b));
Chris@16:         coordinate_type const dy = math::abs(geometry::get<1>(a) - geometry::get<1>(b));
Chris@16: 
Chris@16: 
Chris@16:         if (dx < epsilon && dy < epsilon)
Chris@16:         {
Chris@16:             return false;
Chris@16:         }
Chris@16:         if (dx < epsilon)
Chris@16:         {
Chris@16:             return geometry::get<1>(a) < geometry::get<1>(b);
Chris@16:         }
Chris@16: 
Chris@16:         return geometry::get<0>(a) < geometry::get<0>(b);
Chris@16:     }
Chris@16: 
Chris@16:     inline bool equals(P const& a, P const& b) const
Chris@16:     {
Chris@16:         typedef typename geometry::coordinate_type<P>::type coordinate_type;
Chris@16: 
Chris@16:         coordinate_type const dx = math::abs(geometry::get<0>(a) - geometry::get<0>(b));
Chris@16:         coordinate_type const dy = math::abs(geometry::get<1>(a) - geometry::get<1>(b));
Chris@16: 
Chris@16:         return dx < epsilon && dy < epsilon;
Chris@16:     };
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename T, typename P1, typename P2>
Chris@16: inline T calculate_angle(P1 const& from_point, P2 const& to_point)
Chris@16: {
Chris@16:     typedef P1 vector_type;
Chris@16:     vector_type v = from_point;
Chris@16:     geometry::subtract_point(v, to_point);
Chris@16:     return atan2(geometry::get<1>(v), geometry::get<0>(v));
Chris@16: }
Chris@16: 
Chris@16: template <typename Iterator, typename Vector>
Chris@16: inline Iterator advance_circular(Iterator it, Vector const& vector, segment_identifier& seg_id, bool forward = true)
Chris@16: {
Chris@16:     int const increment = forward ? 1 : -1;
Chris@16:     if (it == boost::begin(vector) && increment < 0)
Chris@16:     {
Chris@16:         it = boost::end(vector);
Chris@16:         seg_id.segment_index = boost::size(vector);
Chris@16:     }
Chris@16:     it += increment;
Chris@16:     seg_id.segment_index += increment;
Chris@16:     if (it == boost::end(vector))
Chris@16:     {
Chris@16:         seg_id.segment_index = 0;
Chris@16:         it = boost::begin(vector);
Chris@16:     }
Chris@16:     return it;
Chris@16: }
Chris@16: 
Chris@16: template <typename Point, typename T>
Chris@16: struct angle_info
Chris@16: {
Chris@16:     typedef T angle_type;
Chris@16:     typedef Point point_type;
Chris@16: 
Chris@16:     segment_identifier seg_id;
Chris@16:     int turn_index;
Chris@16:     int operation_index;
Chris@16:     Point intersection_point;
Chris@16:     Point direction_point;
Chris@16:     T angle;
Chris@16:     bool incoming;
Chris@16: };
Chris@16: 
Chris@16: template <typename AngleInfo>
Chris@16: class occupation_info
Chris@16: {
Chris@16:     typedef std::vector<AngleInfo> collection_type;
Chris@16: 
Chris@16:     struct angle_sort
Chris@16:     {
Chris@16:         inline bool operator()(AngleInfo const& left, AngleInfo const& right) const
Chris@16:         {
Chris@16:             // In this case we can compare even double using equals
Chris@16:             // return geometry::math::equals(left.angle, right.angle)
Chris@16:             return left.angle == right.angle
Chris@16:                 ? int(left.incoming) < int(right.incoming)
Chris@16:                 : left.angle < right.angle
Chris@16:                 ;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16: public :
Chris@16:     collection_type angles;
Chris@16: private :
Chris@16:     bool m_occupied;
Chris@16:     bool m_calculated;
Chris@16: 
Chris@16:     inline bool is_occupied()
Chris@16:     {
Chris@16:         if (boost::size(angles) <= 1)
Chris@16:         {
Chris@16:             return false;
Chris@16:         }
Chris@16: 
Chris@16:         std::sort(angles.begin(), angles.end(), angle_sort());
Chris@16: 
Chris@16:         typedef geometry::closing_iterator<collection_type const> closing_iterator;
Chris@16:         closing_iterator vit(angles);
Chris@16:         closing_iterator end(angles, true);
Chris@16: 
Chris@16:         closing_iterator prev = vit++;
Chris@16:         for( ; vit != end; prev = vit++)
Chris@16:         {
Chris@16:             if (! geometry::math::equals(prev->angle, vit->angle)
Chris@16:                 && ! prev->incoming
Chris@16:                 && vit->incoming)
Chris@16:             {
Chris@16:                 return false;
Chris@16:             }
Chris@16:         }
Chris@16:         return true;
Chris@16:     }
Chris@16: 
Chris@16: public :
Chris@16:     inline occupation_info()
Chris@16:         : m_occupied(false)
Chris@16:         , m_calculated(false)
Chris@16:     {}
Chris@16: 
Chris@16:     template <typename PointC, typename Point1, typename Point2>
Chris@16:     inline void add(PointC const& map_point, Point1 const& direction_point, Point2 const& intersection_point,
Chris@16:                     int turn_index, int operation_index,
Chris@16:                     segment_identifier const& seg_id, bool incoming)
Chris@16:     {
Chris@16:         //std::cout << "-> adding angle " << geometry::wkt(direction_point) << " .. " << geometry::wkt(intersection_point) << " " << int(incoming) << std::endl;
Chris@16:         if (geometry::equals(direction_point, intersection_point))
Chris@16:         {
Chris@16:             //std::cout << "EQUAL! Skipping" << std::endl;
Chris@16:             return;
Chris@16:         }
Chris@16: 
Chris@16:         AngleInfo info;
Chris@16:         info.incoming = incoming;
Chris@16:         info.angle = calculate_angle<typename AngleInfo::angle_type>(direction_point, map_point);
Chris@16:         info.seg_id = seg_id;
Chris@16:         info.turn_index = turn_index;
Chris@16:         info.operation_index = operation_index;
Chris@16:         info.intersection_point = intersection_point;
Chris@16:         info.direction_point = direction_point;
Chris@16:         angles.push_back(info);
Chris@16: 
Chris@16:         m_calculated = false;
Chris@16:     }
Chris@16: 
Chris@16:     inline bool occupied()
Chris@16:     {
Chris@16:         if (! m_calculated)
Chris@16:         {
Chris@16:             m_occupied = is_occupied();
Chris@16:             m_calculated = true;
Chris@16:         }
Chris@16:         return m_occupied;
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Turns, typename TurnSegmentIndices>
Chris@16:     inline void get_left_turns(
Chris@16:                     Turns& turns, TurnSegmentIndices const& turn_segment_indices,
Chris@16:                     std::set<int>& keep_indices)
Chris@16:     {
Chris@16:         std::sort(angles.begin(), angles.end(), angle_sort());
Chris@16:         calculate_left_turns<AngleInfo>(angles, turns, turn_segment_indices, keep_indices);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename Point, typename Ring, typename Info>
Chris@16: inline void add_incoming_and_outgoing_angles(Point const& map_point, Point const& intersection_point,
Chris@16:                 Ring const& ring, 
Chris@16:                 int turn_index,
Chris@16:                 int operation_index,
Chris@16:                 segment_identifier seg_id,
Chris@16:                 Info& info)
Chris@16: {
Chris@16:     typedef typename boost::range_iterator
Chris@16:         <
Chris@16:             Ring const
Chris@16:         >::type iterator_type;
Chris@16: 
Chris@16:     int const n = boost::size(ring);
Chris@16:     if (seg_id.segment_index >= n || seg_id.segment_index < 0)
Chris@16:     {
Chris@16:         return;
Chris@16:     }
Chris@16: 
Chris@16:     segment_identifier real_seg_id = seg_id;
Chris@16:     iterator_type it = boost::begin(ring) + seg_id.segment_index;
Chris@16: 
Chris@16:     // TODO: if we use turn-info ("to", "middle"), we know if to advance without resorting to equals
Chris@16:     relaxed_less<Point> comparator;
Chris@16: 
Chris@16:     if (comparator.equals(intersection_point, *it))
Chris@16:     {
Chris@16:         // It should be equal only once. But otherwise we skip it (in "add")
Chris@16:         it = advance_circular(it, ring, seg_id, false);
Chris@16:     }
Chris@16: 
Chris@16:     info.add(map_point, *it, intersection_point, turn_index, operation_index, real_seg_id, true);
Chris@16: 
Chris@16:     if (comparator.equals(intersection_point, *it))
Chris@16:     {
Chris@16:         it = advance_circular(it, ring, real_seg_id);
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@16:         // Don't upgrade the ID
Chris@16:         it = advance_circular(it, ring, seg_id);
Chris@16:     }
Chris@16:     for (int defensive_check = 0; 
Chris@16:         comparator.equals(intersection_point, *it) && defensive_check < n; 
Chris@16:         defensive_check++)
Chris@16:     {
Chris@16:         it = advance_circular(it, ring, real_seg_id);
Chris@16:     }
Chris@16: 
Chris@16:     info.add(map_point, *it, intersection_point, turn_index, operation_index, real_seg_id, false);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: // Map in two senses of the word: it is a std::map where the key is a point.
Chris@16: // Per point an "occupation_info" record is kept
Chris@16: // Used for the buffer (but will also be used for intersections/unions having complex self-tangencies)
Chris@16: template <typename Point, typename OccupationInfo>
Chris@16: class occupation_map
Chris@16: {
Chris@16: public :
Chris@16:     typedef std::map<Point, OccupationInfo, relaxed_less<Point> > map_type;
Chris@16: 
Chris@16:     map_type map;
Chris@16:     std::set<int> turn_indices;
Chris@16: 
Chris@16:     inline OccupationInfo& find_or_insert(Point const& point, Point& mapped_point)
Chris@16:     {
Chris@16:         typename map_type::iterator it = map.find(point);
Chris@16:         if (it == boost::end(map))
Chris@16:         {
Chris@16:             std::pair<typename map_type::iterator, bool> pair 
Chris@16:                         = map.insert(std::make_pair(point, OccupationInfo()));
Chris@16:             it = pair.first;
Chris@16:         }
Chris@16:         mapped_point = it->first;
Chris@16:         return it->second;
Chris@16:     }
Chris@16: 
Chris@16:     inline bool contains(Point const& point) const
Chris@16:     {
Chris@16:         typename map_type::const_iterator it = map.find(point);
Chris@16:         return it != boost::end(map);
Chris@16:     }
Chris@16: 
Chris@16:     inline bool contains_turn_index(int index) const
Chris@16:     {
Chris@16:         return turn_indices.count(index) > 0;
Chris@16:     }
Chris@16: 
Chris@16:     inline void insert_turn_index(int index)
Chris@16:     {
Chris@16:         turn_indices.insert(index);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: } // namespace detail
Chris@16: #endif // DOXYGEN_NO_DETAIL
Chris@16: 
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OCCUPATION_INFO_HPP