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 are_polygon_interiors_disjoint(PolygonIterator polygons_first,PolygonIterator polygons_beyond,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor,Strategy const & strategy)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: has_multi_index(signed_size_type multi_index)158 has_multi_index(signed_size_type multi_index) 159 : m_multi_index(multi_index) 160 {} 161 162 template <typename Turn> operator ()(Turn const & turn) const163 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 > applyboost::geometry::detail::is_valid::is_valid_multipolygon::has_property_per_polygon185 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 > have_holes_inside(PolygonIterator polygons_first,PolygonIterator polygons_beyond,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor,Strategy const & strategy)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 > have_connected_interior(PolygonIterator polygons_first,PolygonIterator polygons_beyond,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor,Strategy const & strategy)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 { per_polygonboost::geometry::detail::is_valid::is_valid_multipolygon::per_polygon274 per_polygon(VisitPolicy& policy, Strategy const& strategy) 275 : m_policy(policy) 276 , m_strategy(strategy) 277 {} 278 279 template <typename Polygon> applyboost::geometry::detail::is_valid::is_valid_multipolygon::per_polygon280 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> apply(MultiPolygon const & multipolygon,VisitPolicy & visitor,Strategy const & 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 406