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

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