boost/geometry/algorithms/detail/is_valid/multipolygon.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014-2019, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   6 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
   7
   8 // Licensed under the Boost Software License version 1.0.
   9 // http://www.boost.org/users/license.html
  10
  11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP
  12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP
  13
  14 #include <deque>
  15 #include <vector>
  16
  17 #include <boost/core/ignore_unused.hpp>
  18 #include <boost/iterator/filter_iterator.hpp>
  19 #include <boost/range.hpp>
  20
  21 #include <boost/geometry/core/exterior_ring.hpp>
  22 #include <boost/geometry/core/interior_rings.hpp>
  23 #include <boost/geometry/core/ring_type.hpp>
  24 #include <boost/geometry/core/tags.hpp>
  25
  26 #include <boost/geometry/util/condition.hpp>
  27 #include <boost/geometry/util/range.hpp>
  28
  29 #include <boost/geometry/geometries/box.hpp>
  30
  31 #include <boost/geometry/algorithms/validity_failure_type.hpp>
  32 #include <boost/geometry/algorithms/within.hpp>
  33
  34 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
  35 #include <boost/geometry/algorithms/detail/partition.hpp>
  36
  37 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
  38 #include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp>
  39 #include <boost/geometry/algorithms/detail/is_valid/polygon.hpp>
  40
  41 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
  42 #include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp>
  43
  44 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
  45
  46 #include <boost/geometry/strategies/intersection.hpp>
  47
  48
  49 namespace boost { namespace geometry
  50 {
  51
  52
  53 #ifndef DOXYGEN_NO_DETAIL
  54 namespace detail { namespace is_valid
  55 {
  56
  57
  58 template <typename MultiPolygon, bool AllowEmptyMultiGeometries>
  59 class is_valid_multipolygon
  60     : is_valid_polygon
  61         <
  62             typename boost::range_value<MultiPolygon>::type,
  63             true // check only the validity of rings
  64         >
  65 {
  66 private:
  67     typedef is_valid_polygon
  68         <
  69             typename boost::range_value<MultiPolygon>::type,
  70             true
  71         > base;
  72
  73
  74
  75     template
  76     <
  77         typename PolygonIterator,
  78         typename TurnIterator,
  79         typename VisitPolicy,
  80         typename Strategy
  81     >
  82     static inline
  83     bool are_polygon_interiors_disjoint(PolygonIterator polygons_first,
  84                                         PolygonIterator polygons_beyond,
  85                                         TurnIterator turns_first,
  86                                         TurnIterator turns_beyond,
  87                                         VisitPolicy& visitor,
  88                                         Strategy const& strategy)
  89     {
  90         boost::ignore_unused(visitor);
  91
  92         // collect all polygons that have crossing turns
  93         std::set<signed_size_type> multi_indices;
  94         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
  95         {
  96             if (! tit->touch_only)
  97             {
  98                 multi_indices.insert(tit->operations[0].seg_id.multi_index);
  99                 multi_indices.insert(tit->operations[1].seg_id.multi_index);
 100             }
 101         }
 102
 103         typedef geometry::model::box<typename point_type<MultiPolygon>::type> box_type;
 104         typedef typename base::template partition_item<PolygonIterator, box_type> item_type;
 105
 106         // put polygon iterators without turns in a vector
 107         std::vector<item_type> polygon_iterators;
 108         signed_size_type multi_index = 0;
 109         for (PolygonIterator it = polygons_first; it != polygons_beyond;
 110              ++it, ++multi_index)
 111         {
 112             if (multi_indices.find(multi_index) == multi_indices.end())
 113             {
 114                 polygon_iterators.push_back(item_type(it));
 115             }
 116         }
 117
 118         // prepare strategies
 119         typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
 120         envelope_strategy_type const envelope_strategy
 121             = strategy.get_envelope_strategy();
 122         typedef typename Strategy::disjoint_box_box_strategy_type disjoint_box_box_strategy_type;
 123         disjoint_box_box_strategy_type const disjoint_strategy
 124             = strategy.get_disjoint_box_box_strategy();
 125
 126         // call partition to check if polygons are disjoint from each other
 127         typename base::template item_visitor_type<Strategy> item_visitor(strategy);
 128
 129         geometry::partition
 130             <
 131                 geometry::model::box<typename point_type<MultiPolygon>::type>
 132             >::apply(polygon_iterators, item_visitor,
 133                      typename base::template expand_box
 134                         <
 135                             envelope_strategy_type
 136                         >(envelope_strategy),
 137                      typename base::template overlaps_box
 138                         <
 139                             envelope_strategy_type,
 140                             disjoint_box_box_strategy_type
 141                         >(envelope_strategy, disjoint_strategy));
 142
 143         if (item_visitor.items_overlap)
 144         {
 145             return visitor.template apply<failure_intersecting_interiors>();
 146         }
 147         else
 148         {
 149             return visitor.template apply<no_failure>();
 150         }
 151     }
 152
 153
 154
 155     class has_multi_index
 156     {
 157     public:
 158         has_multi_index(signed_size_type multi_index)
 159             : m_multi_index(multi_index)
 160         {}
 161
 162         template <typename Turn>
 163         inline bool operator()(Turn const& turn) const
 164         {
 165             return turn.operations[0].seg_id.multi_index == m_multi_index
 166                 && turn.operations[1].seg_id.multi_index == m_multi_index;
 167         }
 168
 169     private:
 170         signed_size_type const m_multi_index;
 171     };
 172
 173
 174
 175     template <typename Predicate>
 176     struct has_property_per_polygon
 177     {
 178         template
 179         <
 180             typename PolygonIterator,
 181             typename TurnIterator,
 182             typename VisitPolicy,
 183             typename Strategy
 184         >
 185         static inline bool apply(PolygonIterator polygons_first,
 186                                  PolygonIterator polygons_beyond,
 187                                  TurnIterator turns_first,
 188                                  TurnIterator turns_beyond,
 189                                  VisitPolicy& visitor,
 190                                  Strategy const& strategy)
 191         {
 192             signed_size_type multi_index = 0;
 193             for (PolygonIterator it = polygons_first; it != polygons_beyond;
 194                  ++it, ++multi_index)
 195             {
 196                 has_multi_index index_predicate(multi_index);
 197
 198                 typedef boost::filter_iterator
 199                     <
 200                         has_multi_index, TurnIterator
 201                     > filtered_turn_iterator;
 202
 203                 filtered_turn_iterator filtered_turns_first(index_predicate,
 204                                                             turns_first,
 205                                                             turns_beyond);
 206
 207                 filtered_turn_iterator filtered_turns_beyond(index_predicate,
 208                                                              turns_beyond,
 209                                                              turns_beyond);
 210
 211                 if (! Predicate::apply(*it,
 212                                        filtered_turns_first,
 213                                        filtered_turns_beyond,
 214                                        visitor,
 215                                        strategy))
 216                 {
 217                     return false;
 218                 }
 219             }
 220             return true;
 221         }
 222     };
 223
 224
 225
 226     template
 227     <
 228         typename PolygonIterator,
 229         typename TurnIterator,
 230         typename VisitPolicy,
 231         typename Strategy
 232     >
 233     static inline bool have_holes_inside(PolygonIterator polygons_first,
 234                                          PolygonIterator polygons_beyond,
 235                                          TurnIterator turns_first,
 236                                          TurnIterator turns_beyond,
 237                                          VisitPolicy& visitor,
 238                                          Strategy const& strategy)
 239     {
 240         return has_property_per_polygon
 241             <
 242                 typename base::has_holes_inside
 243             >::apply(polygons_first, polygons_beyond,
 244                      turns_first, turns_beyond, visitor, strategy);
 245     }
 246
 247
 248
 249     template
 250     <
 251         typename PolygonIterator,
 252         typename TurnIterator,
 253         typename VisitPolicy,
 254         typename Strategy
 255     >
 256     static inline bool have_connected_interior(PolygonIterator polygons_first,
 257                                                PolygonIterator polygons_beyond,
 258                                                TurnIterator turns_first,
 259                                                TurnIterator turns_beyond,
 260                                                VisitPolicy& visitor,
 261                                                Strategy const& strategy)
 262     {
 263         return has_property_per_polygon
 264             <
 265                 typename base::has_connected_interior
 266             >::apply(polygons_first, polygons_beyond,
 267                      turns_first, turns_beyond, visitor, strategy);
 268     }
 269
 270
 271     template <typename VisitPolicy, typename Strategy>
 272     struct per_polygon
 273     {
 274         per_polygon(VisitPolicy& policy, Strategy const& strategy)
 275             : m_policy(policy)
 276             , m_strategy(strategy)
 277         {}
 278
 279         template <typename Polygon>
 280         inline bool apply(Polygon const& polygon) const
 281         {
 282             return base::apply(polygon, m_policy, m_strategy);
 283         }
 284
 285         VisitPolicy& m_policy;
 286         Strategy const& m_strategy;
 287     };
 288 public:
 289     template <typename VisitPolicy, typename Strategy>
 290     static inline bool apply(MultiPolygon const& multipolygon,
 291                              VisitPolicy& visitor,
 292                              Strategy const& strategy)
 293     {
 294         typedef debug_validity_phase<MultiPolygon> debug_phase;
 295
 296         if (BOOST_GEOMETRY_CONDITION(AllowEmptyMultiGeometries)
 297             && boost::empty(multipolygon))
 298         {
 299             return visitor.template apply<no_failure>();
 300         }
 301
 302         // check validity of all polygons ring
 303         debug_phase::apply(1);
 304
 305         if (! detail::check_iterator_range
 306                   <
 307                       per_polygon<VisitPolicy, Strategy>,
 308                       false // do not check for empty multipolygon (done above)
 309                   >::apply(boost::begin(multipolygon),
 310                            boost::end(multipolygon),
 311                            per_polygon<VisitPolicy, Strategy>(visitor, strategy)))
 312         {
 313             return false;
 314         }
 315
 316
 317         // compute turns and check if all are acceptable
 318         debug_phase::apply(2);
 319
 320         typedef has_valid_self_turns<MultiPolygon, typename Strategy::cs_tag> has_valid_turns;
 321
 322         std::deque<typename has_valid_turns::turn_type> turns;
 323         bool has_invalid_turns =
 324             ! has_valid_turns::apply(multipolygon, turns, visitor, strategy);
 325         debug_print_turns(turns.begin(), turns.end());
 326
 327         if (has_invalid_turns)
 328         {
 329             return false;
 330         }
 331
 332
 333         // check if each polygon's interior rings are inside the
 334         // exterior and not one inside the other
 335         debug_phase::apply(3);
 336
 337         if (! have_holes_inside(boost::begin(multipolygon),
 338                                 boost::end(multipolygon),
 339                                 turns.begin(),
 340                                 turns.end(),
 341                                 visitor,
 342                                 strategy))
 343         {
 344             return false;
 345         }
 346
 347
 348         // check that each polygon's interior is connected
 349         debug_phase::apply(4);
 350
 351         if (! have_connected_interior(boost::begin(multipolygon),
 352                                       boost::end(multipolygon),
 353                                       turns.begin(),
 354                                       turns.end(),
 355                                       visitor,
 356                                       strategy))
 357         {
 358             return false;
 359         }
 360
 361
 362         // check if polygon interiors are disjoint
 363         debug_phase::apply(5);
 364         return are_polygon_interiors_disjoint(boost::begin(multipolygon),
 365                                               boost::end(multipolygon),
 366                                               turns.begin(),
 367                                               turns.end(),
 368                                               visitor,
 369                                               strategy);
 370     }
 371 };
 372
 373 }} // namespace detail::is_valid
 374 #endif // DOXYGEN_NO_DETAIL
 375
 376
 377
 378 #ifndef DOXYGEN_NO_DISPATCH
 379 namespace dispatch
 380 {
 381
 382
 383 // Not clear what the definition is.
 384 // Right now we check that each element is simple (in fact valid), and
 385 // that the MultiPolygon is also valid.
 386 //
 387 // Reference (for validity of MultiPolygons): OGC 06-103r4 (6.1.14)
 388 template <typename MultiPolygon, bool AllowEmptyMultiGeometries>
 389 struct is_valid
 390     <
 391         MultiPolygon, multi_polygon_tag, AllowEmptyMultiGeometries
 392     > : detail::is_valid::is_valid_multipolygon
 393         <
 394             MultiPolygon, AllowEmptyMultiGeometries
 395         >
 396 {};
 397
 398
 399 } // namespace dispatch
 400 #endif // DOXYGEN_NO_DISPATCH
 401
 402
 403 }} // namespace boost::geometry
 404
 405 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP