boost/geometry/algorithms/detail/overlay/overlay.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland
   5
   6 // Use, modification and distribution is subject to the Boost Software License,
   7 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9
  10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
  12
  13
  14 #include <deque>
  15 #include <map>
  16
  17 #include <boost/range.hpp>
  18 #include <boost/mpl/assert.hpp>
  19
  20
  21 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
  22 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
  23 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
  24 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  25 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
  26 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
  27 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  28
  29 #include <boost/geometry/algorithms/detail/recalculate.hpp>
  30
  31 #include <boost/geometry/algorithms/num_points.hpp>
  32 #include <boost/geometry/algorithms/reverse.hpp>
  33
  34 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
  35 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
  36 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
  37 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
  38 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
  39
  40 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
  41
  42
  43 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
  44 #  include <boost/geometry/io/dsv/write.hpp>
  45 #endif
  46
  47 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
  48 # include <boost/timer.hpp>
  49 #endif
  50
  51
  52 namespace boost { namespace geometry
  53 {
  54
  55
  56 #ifndef DOXYGEN_NO_DETAIL
  57 namespace detail { namespace overlay
  58 {
  59
  60 // Skip for assemble process
  61 template <typename TurnInfo>
  62 inline bool skip(TurnInfo const& turn_info)
  63 {
  64     return (turn_info.discarded || turn_info.both(operation_union))
  65         && ! turn_info.any_blocked()
  66         && ! turn_info.both(operation_intersection)
  67         ;
  68 }
  69
  70
  71 template <typename TurnPoints, typename Map>
  72 inline void map_turns(Map& map, TurnPoints const& turn_points)
  73 {
  74     typedef typename boost::range_value<TurnPoints>::type turn_point_type;
  75     typedef typename turn_point_type::container_type container_type;
  76
  77     for (typename boost::range_iterator<TurnPoints const>::type
  78             it = boost::begin(turn_points);
  79          it != boost::end(turn_points);
  80          ++it)
  81     {
  82         if (! skip(*it))
  83         {
  84             for (typename boost::range_iterator<container_type const>::type
  85                     op_it = boost::begin(it->operations);
  86                 op_it != boost::end(it->operations);
  87                 ++op_it)
  88             {
  89                 ring_identifier ring_id
  90                     (
  91                         op_it->seg_id.source_index,
  92                         op_it->seg_id.multi_index,
  93                         op_it->seg_id.ring_index
  94                     );
  95                 map[ring_id]++;
  96             }
  97         }
  98     }
  99 }
 100
 101
 102 template
 103 <
 104     typename GeometryOut, overlay_type Direction, bool ReverseOut,
 105     typename Geometry1, typename Geometry2,
 106     typename OutputIterator
 107 >
 108 inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
 109             Geometry2 const& geometry2,
 110             OutputIterator out)
 111 {
 112     typedef std::deque
 113         <
 114             typename geometry::ring_type<GeometryOut>::type
 115         > ring_container_type;
 116
 117     typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties;
 118
 119 // Silence warning C4127: conditional expression is constant
 120 #if defined(_MSC_VER)
 121 #pragma warning(push)
 122 #pragma warning(disable : 4127)
 123 #endif
 124
 125     // Union: return either of them
 126     // Intersection: return nothing
 127     // Difference: return first of them
 128     if (Direction == overlay_intersection
 129         || (Direction == overlay_difference
 130             && geometry::num_points(geometry1) == 0))
 131     {
 132         return out;
 133     }
 134
 135 #if defined(_MSC_VER)
 136 #pragma warning(pop)
 137 #endif
 138
 139
 140     std::map<ring_identifier, int> empty;
 141     std::map<ring_identifier, properties> all_of_one_of_them;
 142
 143     select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them, false);
 144     ring_container_type rings;
 145     assign_parents(geometry1, geometry2, rings, all_of_one_of_them);
 146     return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
 147 }
 148
 149
 150 template
 151 <
 152     typename Geometry1, typename Geometry2,
 153     bool Reverse1, bool Reverse2, bool ReverseOut,
 154     typename GeometryOut,
 155     overlay_type Direction
 156 >
 157 struct overlay
 158 {
 159     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
 160     static inline OutputIterator apply(
 161                 Geometry1 const& geometry1, Geometry2 const& geometry2,
 162                 RobustPolicy const& robust_policy,
 163                 OutputIterator out,
 164                 Strategy const& )
 165     {
 166         if ( geometry::num_points(geometry1) == 0
 167           && geometry::num_points(geometry2) == 0 )
 168         {
 169             return out;
 170         }
 171
 172         if ( geometry::num_points(geometry1) == 0
 173           || geometry::num_points(geometry2) == 0 )
 174         {
 175             return return_if_one_input_is_empty
 176                 <
 177                     GeometryOut, Direction, ReverseOut
 178                 >(geometry1, geometry2, out);
 179         }
 180
 181         typedef typename geometry::point_type<GeometryOut>::type point_type;
 182         typedef detail::overlay::traversal_turn_info
 183         <
 184             point_type,
 185             typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
 186         > turn_info;
 187         typedef std::deque<turn_info> container_type;
 188
 189         typedef std::deque
 190             <
 191                 typename geometry::ring_type<GeometryOut>::type
 192             > ring_container_type;
 193
 194         container_type turn_points;
 195
 196 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
 197         boost::timer timer;
 198 #endif
 199
 200 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 201 std::cout << "get turns" << std::endl;
 202 #endif
 203         detail::get_turns::no_interrupt_policy policy;
 204         geometry::get_turns
 205             <
 206                 Reverse1, Reverse2,
 207                 detail::overlay::assign_null_policy
 208             >(geometry1, geometry2, robust_policy, turn_points, policy);
 209
 210 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
 211         std::cout << "get_turns: " << timer.elapsed() << std::endl;
 212 #endif
 213
 214 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 215 std::cout << "enrich" << std::endl;
 216 #endif
 217         typename Strategy::side_strategy_type side_strategy;
 218         geometry::enrich_intersection_points<Reverse1, Reverse2>(turn_points,
 219                 Direction == overlay_union
 220                     ? geometry::detail::overlay::operation_union
 221                     : geometry::detail::overlay::operation_intersection,
 222                     geometry1, geometry2,
 223                     robust_policy,
 224                     side_strategy);
 225
 226 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
 227         std::cout << "enrich_intersection_points: " << timer.elapsed() << std::endl;
 228 #endif
 229
 230
 231 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
 232 std::cout << "traverse" << std::endl;
 233 #endif
 234         // Traverse through intersection/turn points and create rings of them.
 235         // Note that these rings are always in clockwise order, even in CCW polygons,
 236         // and are marked as "to be reversed" below
 237         ring_container_type rings;
 238         traverse<Reverse1, Reverse2, Geometry1, Geometry2>::apply
 239                 (
 240                     geometry1, geometry2,
 241                     Direction == overlay_union
 242                         ? geometry::detail::overlay::operation_union
 243                         : geometry::detail::overlay::operation_intersection,
 244                     robust_policy,
 245                     turn_points, rings
 246                 );
 247
 248 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
 249         std::cout << "traverse: " << timer.elapsed() << std::endl;
 250 #endif
 251
 252
 253         std::map<ring_identifier, int> map;
 254         map_turns(map, turn_points);
 255
 256 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
 257         std::cout << "map_turns: " << timer.elapsed() << std::endl;
 258 #endif
 259
 260         typedef ring_properties<typename geometry::point_type<GeometryOut>::type> properties;
 261
 262         std::map<ring_identifier, properties> selected;
 263         select_rings<Direction>(geometry1, geometry2, map, selected, ! turn_points.empty());
 264
 265 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
 266         std::cout << "select_rings: " << timer.elapsed() << std::endl;
 267 #endif
 268
 269
 270         // Add rings created during traversal
 271         {
 272             ring_identifier id(2, 0, -1);
 273             for (typename boost::range_iterator<ring_container_type>::type
 274                     it = boost::begin(rings);
 275                  it != boost::end(rings);
 276                  ++it)
 277             {
 278                 selected[id] = properties(*it, true);
 279                 selected[id].reversed = ReverseOut;
 280                 id.multi_index++;
 281             }
 282         }
 283
 284 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
 285         std::cout << "add traversal rings: " << timer.elapsed() << std::endl;
 286 #endif
 287
 288
 289         assign_parents(geometry1, geometry2, rings, selected);
 290
 291 #ifdef BOOST_GEOMETRY_TIME_OVERLAY
 292         std::cout << "assign_parents: " << timer.elapsed() << std::endl;
 293 #endif
 294
 295         return add_rings<GeometryOut>(selected, geometry1, geometry2, rings, out);
 296     }
 297 };
 298
 299
 300 }} // namespace detail::overlay
 301 #endif // DOXYGEN_NO_DETAIL
 302
 303
 304 }} // namespace boost::geometry
 305
 306
 307 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP