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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2014, Oracle and/or its affiliates.
   4
   5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
   6
   7 // Licensed under the Boost Software License version 1.0.
   8 // http://www.boost.org/users/license.html
   9
  10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP
  12
  13 #include <deque>
  14 #include <vector>
  15
  16 #include <boost/iterator/filter_iterator.hpp>
  17 #include <boost/range.hpp>
  18
  19 #include <boost/geometry/core/exterior_ring.hpp>
  20 #include <boost/geometry/core/interior_rings.hpp>
  21 #include <boost/geometry/core/ring_type.hpp>
  22 #include <boost/geometry/core/tags.hpp>
  23
  24 #include <boost/geometry/util/range.hpp>
  25
  26 #include <boost/geometry/geometries/box.hpp>
  27
  28 #include <boost/geometry/algorithms/within.hpp>
  29
  30 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
  31 #include <boost/geometry/algorithms/detail/partition.hpp>
  32
  33 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
  34 #include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp>
  35 #include <boost/geometry/algorithms/detail/is_valid/polygon.hpp>
  36
  37 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
  38 #include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp>
  39
  40 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
  41
  42
  43 namespace boost { namespace geometry
  44 {
  45
  46
  47 #ifndef DOXYGEN_NO_DETAIL
  48 namespace detail { namespace is_valid
  49 {
  50
  51
  52 template <typename MultiPolygon, bool AllowDuplicates>
  53 class is_valid_multipolygon
  54     : is_valid_polygon
  55         <
  56             typename boost::range_value<MultiPolygon>::type,
  57             AllowDuplicates,
  58             true // check only the validity of rings
  59         >
  60 {
  61 private:
  62     typedef is_valid_polygon
  63         <
  64             typename boost::range_value<MultiPolygon>::type,
  65             AllowDuplicates,
  66             true
  67         > base;
  68
  69
  70
  71     template <typename PolygonIterator, typename TurnIterator>
  72     static inline
  73     bool are_polygon_interiors_disjoint(PolygonIterator polygons_first,
  74                                         PolygonIterator polygons_beyond,
  75                                         TurnIterator turns_first,
  76                                         TurnIterator turns_beyond)
  77     {
  78         // collect all polygons that have turns
  79         std::set<signed_index_type> multi_indices;
  80         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
  81         {
  82             multi_indices.insert(tit->operations[0].seg_id.multi_index);
  83             multi_indices.insert(tit->operations[1].seg_id.multi_index);
  84         }
  85
  86         // put polygon iterators without turns in a vector
  87         std::vector<PolygonIterator> polygon_iterators;
  88         signed_index_type multi_index = 0;
  89         for (PolygonIterator it = polygons_first; it != polygons_beyond;
  90              ++it, ++multi_index)
  91         {
  92             if ( multi_indices.find(multi_index) == multi_indices.end() )
  93             {
  94                 polygon_iterators.push_back(it);
  95             }
  96         }
  97
  98         typename base::item_visitor visitor;
  99
 100         geometry::partition
 101             <
 102                 geometry::model::box<typename point_type<MultiPolygon>::type>,
 103                 typename base::expand_box,
 104                 typename base::overlaps_box
 105             >::apply(polygon_iterators, visitor);
 106
 107         return !visitor.items_overlap;
 108     }
 109
 110
 111
 112     class has_multi_index
 113     {
 114     public:
 115         has_multi_index(signed_index_type multi_index)
 116             : m_multi_index(multi_index)
 117         {}
 118
 119         template <typename Turn>
 120         inline bool operator()(Turn const& turn) const
 121         {
 122             return turn.operations[0].seg_id.multi_index == m_multi_index
 123                 && turn.operations[1].seg_id.multi_index == m_multi_index;
 124         }
 125
 126     private:
 127         signed_index_type const m_multi_index;
 128     };
 129
 130
 131
 132     template <typename Predicate>
 133     struct has_property_per_polygon
 134     {
 135         template <typename PolygonIterator, typename TurnIterator>
 136         static inline bool apply(PolygonIterator polygons_first,
 137                                  PolygonIterator polygons_beyond,
 138                                  TurnIterator turns_first,
 139                                  TurnIterator turns_beyond)
 140         {
 141             signed_index_type multi_index = 0;
 142             for (PolygonIterator it = polygons_first; it != polygons_beyond;
 143                  ++it, ++multi_index)
 144             {
 145                 has_multi_index index_predicate(multi_index);
 146
 147                 typedef boost::filter_iterator
 148                     <
 149                         has_multi_index, TurnIterator
 150                     > filtered_turn_iterator;
 151
 152                 filtered_turn_iterator filtered_turns_first(index_predicate,
 153                                                             turns_first,
 154                                                             turns_beyond);
 155
 156                 filtered_turn_iterator filtered_turns_beyond(index_predicate,
 157                                                              turns_beyond,
 158                                                              turns_beyond);
 159
 160                 if ( !Predicate::apply(*it,
 161                                        filtered_turns_first,
 162                                        filtered_turns_beyond) )
 163                 {
 164                     return false;
 165                 }
 166             }
 167             return true;
 168         }
 169     };
 170
 171
 172
 173     template <typename PolygonIterator, typename TurnIterator>
 174     static inline bool have_holes_inside(PolygonIterator polygons_first,
 175                                          PolygonIterator polygons_beyond,
 176                                          TurnIterator turns_first,
 177                                          TurnIterator turns_beyond)
 178     {
 179         return has_property_per_polygon
 180             <
 181                 typename base::has_holes_inside
 182             >::apply(polygons_first, polygons_beyond,
 183                      turns_first, turns_beyond);
 184     }
 185
 186
 187
 188     template <typename PolygonIterator, typename TurnIterator>
 189     static inline bool have_connected_interior(PolygonIterator polygons_first,
 190                                                PolygonIterator polygons_beyond,
 191                                                TurnIterator turns_first,
 192                                                TurnIterator turns_beyond)
 193     {
 194         return has_property_per_polygon
 195             <
 196                 typename base::has_connected_interior
 197             >::apply(polygons_first, polygons_beyond,
 198                      turns_first, turns_beyond);
 199     }
 200
 201
 202 public:
 203     static inline bool apply(MultiPolygon const& multipolygon)
 204     {
 205         typedef debug_validity_phase<MultiPolygon> debug_phase;
 206
 207         // check validity of all polygons ring
 208         debug_phase::apply(1);
 209
 210         if ( !detail::check_iterator_range
 211                   <
 212                       base,
 213                       false // do not allow empty multi-polygons
 214                   >::apply(boost::begin(multipolygon),
 215                            boost::end(multipolygon)) )
 216         {
 217             return false;
 218         }
 219
 220
 221         // compute turns and check if all are acceptable
 222         debug_phase::apply(2);
 223
 224         typedef has_valid_self_turns<MultiPolygon> has_valid_turns;
 225
 226         std::deque<typename has_valid_turns::turn_type> turns;
 227         bool has_invalid_turns = !has_valid_turns::apply(multipolygon, turns);
 228         debug_print_turns(turns.begin(), turns.end());
 229
 230         if ( has_invalid_turns )
 231         {
 232             return false;
 233         }
 234
 235
 236         // check if each polygon's interior rings are inside the
 237         // exterior and not one inside the other
 238         debug_phase::apply(3);
 239
 240         if ( !have_holes_inside(boost::begin(multipolygon),
 241                                 boost::end(multipolygon),
 242                                 turns.begin(),
 243                                 turns.end()) )
 244         {
 245             return false;
 246         }
 247
 248
 249         // check that each polygon's interior is connected
 250         debug_phase::apply(4);
 251
 252         if ( !have_connected_interior(boost::begin(multipolygon),
 253                                       boost::end(multipolygon),
 254                                       turns.begin(),
 255                                       turns.end()) )
 256         {
 257             return false;
 258         }
 259
 260
 261         // check if polygon interiors are disjoint
 262         debug_phase::apply(5);
 263         return are_polygon_interiors_disjoint(boost::begin(multipolygon),
 264                                               boost::end(multipolygon),
 265                                               turns.begin(),
 266                                               turns.end());
 267     }
 268 };
 269
 270 }} // namespace detail::is_valid
 271 #endif // DOXYGEN_NO_DETAIL
 272
 273
 274
 275 #ifndef DOXYGEN_NO_DISPATCH
 276 namespace dispatch
 277 {
 278
 279
 280 // Not clear what the definition is.
 281 // Right now we check that each element is simple (in fact valid), and
 282 // that the MultiPolygon is also valid.
 283 //
 284 // Reference (for validity of MultiPolygons): OGC 06-103r4 (6.1.14)
 285 template <typename MultiPolygon, bool AllowSpikes, bool AllowDuplicates>
 286 struct is_valid<MultiPolygon, multi_polygon_tag, AllowSpikes, AllowDuplicates>
 287     : detail::is_valid::is_valid_multipolygon<MultiPolygon, AllowDuplicates>
 288 {};
 289
 290
 291 } // namespace dispatch
 292 #endif // DOXYGEN_NO_DISPATCH
 293
 294
 295 }} // namespace boost::geometry
 296
 297 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP