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

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