ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/is_valid/polygon.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
   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_POLYGON_HPP
  11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP
  12
  13 #include <cstddef>
  14 #ifdef BOOST_GEOMETRY_TEST_DEBUG
  15 #include <iostream>
  16 #endif // BOOST_GEOMETRY_TEST_DEBUG
  17
  18 #include <algorithm>
  19 #include <deque>
  20 #include <iterator>
  21 #include <set>
  22 #include <vector>
  23
  24 #include <boost/core/ignore_unused.hpp>
  25 #include <boost/range.hpp>
  26
  27 #include <boost/geometry/core/assert.hpp>
  28 #include <boost/geometry/core/exterior_ring.hpp>
  29 #include <boost/geometry/core/interior_rings.hpp>
  30 #include <boost/geometry/core/ring_type.hpp>
  31 #include <boost/geometry/core/tags.hpp>
  32
  33 #include <boost/geometry/util/condition.hpp>
  34 #include <boost/geometry/util/range.hpp>
  35
  36 #include <boost/geometry/geometries/box.hpp>
  37
  38 #include <boost/geometry/iterators/point_iterator.hpp>
  39
  40 #include <boost/geometry/algorithms/covered_by.hpp>
  41 #include <boost/geometry/algorithms/disjoint.hpp>
  42 #include <boost/geometry/algorithms/expand.hpp>
  43 #include <boost/geometry/algorithms/num_interior_rings.hpp>
  44 #include <boost/geometry/algorithms/validity_failure_type.hpp>
  45 #include <boost/geometry/algorithms/within.hpp>
  46
  47 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
  48 #include <boost/geometry/algorithms/detail/partition.hpp>
  49
  50 #include <boost/geometry/algorithms/detail/is_valid/complement_graph.hpp>
  51 #include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
  52 #include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp>
  53 #include <boost/geometry/algorithms/detail/is_valid/ring.hpp>
  54
  55 #include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
  56 #include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp>
  57 #include <boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp>
  58
  59 #include <boost/geometry/algorithms/dispatch/is_valid.hpp>
  60
  61
  62 namespace boost { namespace geometry
  63 {
  64
  65
  66 #ifndef DOXYGEN_NO_DETAIL
  67 namespace detail { namespace is_valid
  68 {
  69
  70
  71 template <typename Polygon, bool CheckRingValidityOnly = false>
  72 class is_valid_polygon
  73 {
  74 protected:
  75     typedef debug_validity_phase<Polygon> debug_phase;
  76
  77     template <typename VisitPolicy>
  78     struct per_ring
  79     {
  80         per_ring(VisitPolicy& policy) : m_policy(policy) {}
  81
  82         template <typename Ring>
  83         inline bool apply(Ring const& ring) const
  84         {
  85             return detail::is_valid::is_valid_ring
  86                 <
  87                     Ring, false, true
  88                 >::apply(ring, m_policy);
  89         }
  90
  91         VisitPolicy& m_policy;
  92     };
  93
  94     template <typename InteriorRings, typename VisitPolicy>
  95     static bool has_valid_interior_rings(InteriorRings const& interior_rings,
  96                                          VisitPolicy& visitor)
  97     {
  98         return
  99             detail::check_iterator_range
 100                 <
 101                     per_ring<VisitPolicy>,
 102                     true // allow for empty interior ring range
 103                 >::apply(boost::begin(interior_rings),
 104                          boost::end(interior_rings),
 105                          per_ring<VisitPolicy>(visitor));
 106     }
 107
 108     struct has_valid_rings
 109     {
 110         template <typename VisitPolicy>
 111         static inline bool apply(Polygon const& polygon, VisitPolicy& visitor)
 112         {
 113             typedef typename ring_type<Polygon>::type ring_type;
 114
 115             // check validity of exterior ring
 116             debug_phase::apply(1);
 117
 118             if (! detail::is_valid::is_valid_ring
 119                      <
 120                          ring_type,
 121                          false // do not check self intersections
 122                      >::apply(exterior_ring(polygon), visitor))
 123             {
 124                 return false;
 125             }
 126
 127             // check validity of interior rings
 128             debug_phase::apply(2);
 129
 130             return has_valid_interior_rings(geometry::interior_rings(polygon),
 131                                             visitor);
 132         }
 133     };
 134
 135
 136     // structs for partition -- start
 137     struct expand_box
 138     {
 139         template <typename Box, typename Iterator>
 140         static inline void apply(Box& total, Iterator const& it)
 141         {
 142             geometry::expand(total, geometry::return_envelope<Box>(*it));
 143         }
 144
 145     };
 146
 147     struct overlaps_box
 148     {
 149         template <typename Box, typename Iterator>
 150         static inline bool apply(Box const& box, Iterator const& it)
 151         {
 152             return ! geometry::disjoint(*it, box);
 153         }
 154     };
 155
 156
 157     struct item_visitor_type
 158     {
 159         bool items_overlap;
 160
 161         item_visitor_type() : items_overlap(false) {}
 162
 163         template <typename Item1, typename Item2>
 164         inline void apply(Item1 const& item1, Item2 const& item2)
 165         {
 166             if (! items_overlap
 167                 && (geometry::within(*points_begin(*item1), *item2)
 168                     || geometry::within(*points_begin(*item2), *item1))
 169                 )
 170             {
 171                 items_overlap = true;
 172             }
 173         }
 174     };
 175     // structs for partition -- end
 176
 177
 178     template
 179     <
 180         typename RingIterator,
 181         typename ExteriorRing,
 182         typename TurnIterator,
 183         typename VisitPolicy
 184     >
 185     static inline bool are_holes_inside(RingIterator rings_first,
 186                                         RingIterator rings_beyond,
 187                                         ExteriorRing const& exterior_ring,
 188                                         TurnIterator turns_first,
 189                                         TurnIterator turns_beyond,
 190                                         VisitPolicy& visitor)
 191     {
 192         boost::ignore_unused(visitor);
 193
 194         // collect the interior ring indices that have turns with the
 195         // exterior ring
 196         std::set<signed_size_type> ring_indices;
 197         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
 198         {
 199             if (tit->operations[0].seg_id.ring_index == -1)
 200             {
 201                 BOOST_GEOMETRY_ASSERT(tit->operations[1].seg_id.ring_index != -1);
 202                 ring_indices.insert(tit->operations[1].seg_id.ring_index);
 203             }
 204             else if (tit->operations[1].seg_id.ring_index == -1)
 205             {
 206                 BOOST_GEOMETRY_ASSERT(tit->operations[0].seg_id.ring_index != -1);
 207                 ring_indices.insert(tit->operations[0].seg_id.ring_index);
 208             }
 209         }
 210
 211         signed_size_type ring_index = 0;
 212         for (RingIterator it = rings_first; it != rings_beyond;
 213              ++it, ++ring_index)
 214         {
 215             // do not examine interior rings that have turns with the
 216             // exterior ring
 217             if (ring_indices.find(ring_index) == ring_indices.end()
 218                 && ! geometry::covered_by(range::front(*it), exterior_ring))
 219             {
 220                 return visitor.template apply<failure_interior_rings_outside>();
 221             }
 222         }
 223
 224         // collect all rings (exterior and/or interior) that have turns
 225         for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit)
 226         {
 227             ring_indices.insert(tit->operations[0].seg_id.ring_index);
 228             ring_indices.insert(tit->operations[1].seg_id.ring_index);
 229         }
 230
 231         // put iterators for interior rings without turns in a vector
 232         std::vector<RingIterator> ring_iterators;
 233         ring_index = 0;
 234         for (RingIterator it = rings_first; it != rings_beyond;
 235              ++it, ++ring_index)
 236         {
 237             if (ring_indices.find(ring_index) == ring_indices.end())
 238             {
 239                 ring_iterators.push_back(it);
 240             }
 241         }
 242
 243         // call partition to check is interior rings are disjoint from
 244         // each other
 245         item_visitor_type item_visitor;
 246
 247         geometry::partition
 248             <
 249                 geometry::model::box<typename point_type<Polygon>::type>,
 250                 expand_box,
 251                 overlaps_box
 252             >::apply(ring_iterators, item_visitor);
 253
 254         if (item_visitor.items_overlap)
 255         {
 256             return visitor.template apply<failure_nested_interior_rings>();
 257         }
 258         else
 259         {
 260             return visitor.template apply<no_failure>();
 261         }
 262     }
 263
 264     template
 265     <
 266         typename InteriorRings,
 267         typename ExteriorRing,
 268         typename TurnIterator,
 269         typename VisitPolicy
 270     >
 271     static inline bool are_holes_inside(InteriorRings const& interior_rings,
 272                                         ExteriorRing const& exterior_ring,
 273                                         TurnIterator first,
 274                                         TurnIterator beyond,
 275                                         VisitPolicy& visitor)
 276     {
 277         return are_holes_inside(boost::begin(interior_rings),
 278                                 boost::end(interior_rings),
 279                                 exterior_ring,
 280                                 first,
 281                                 beyond,
 282                                 visitor);
 283     }
 284
 285     struct has_holes_inside
 286     {
 287         template <typename TurnIterator, typename VisitPolicy>
 288         static inline bool apply(Polygon const& polygon,
 289                                  TurnIterator first,
 290                                  TurnIterator beyond,
 291                                  VisitPolicy& visitor)
 292         {
 293             return are_holes_inside(geometry::interior_rings(polygon),
 294                                     geometry::exterior_ring(polygon),
 295                                     first,
 296                                     beyond,
 297                                     visitor);
 298         }
 299     };
 300
 301
 302
 303
 304     struct has_connected_interior
 305     {
 306         template <typename TurnIterator, typename VisitPolicy>
 307         static inline bool apply(Polygon const& polygon,
 308                                  TurnIterator first,
 309                                  TurnIterator beyond,
 310                                  VisitPolicy& visitor)
 311         {
 312             boost::ignore_unused(visitor);
 313
 314             typedef typename std::iterator_traits
 315                 <
 316                     TurnIterator
 317                 >::value_type turn_type;
 318             typedef complement_graph<typename turn_type::point_type> graph;
 319
 320             graph g(geometry::num_interior_rings(polygon) + 1);
 321             for (TurnIterator tit = first; tit != beyond; ++tit)
 322             {
 323                 typename graph::vertex_handle v1 = g.add_vertex
 324                     ( tit->operations[0].seg_id.ring_index + 1 );
 325                 typename graph::vertex_handle v2 = g.add_vertex
 326                     ( tit->operations[1].seg_id.ring_index + 1 );
 327                 typename graph::vertex_handle vip = g.add_vertex(tit->point);
 328
 329                 g.add_edge(v1, vip);
 330                 g.add_edge(v2, vip);
 331             }
 332
 333 #ifdef BOOST_GEOMETRY_TEST_DEBUG
 334             debug_print_complement_graph(std::cout, g);
 335 #endif // BOOST_GEOMETRY_TEST_DEBUG
 336
 337             if (g.has_cycles())
 338             {
 339                 return visitor.template apply<failure_disconnected_interior>();
 340             }
 341             else
 342             {
 343                 return visitor.template apply<no_failure>();
 344             }
 345         }
 346     };
 347
 348 public:
 349     template <typename VisitPolicy>
 350     static inline bool apply(Polygon const& polygon, VisitPolicy& visitor)
 351     {
 352         if (! has_valid_rings::apply(polygon, visitor))
 353         {
 354             return false;
 355         }
 356
 357         if (BOOST_GEOMETRY_CONDITION(CheckRingValidityOnly))
 358         {
 359             return true;
 360         }
 361
 362         // compute turns and check if all are acceptable
 363         debug_phase::apply(3);
 364
 365         typedef has_valid_self_turns<Polygon> has_valid_turns;
 366
 367         std::deque<typename has_valid_turns::turn_type> turns;
 368         bool has_invalid_turns
 369             = ! has_valid_turns::apply(polygon, turns, visitor);
 370         debug_print_turns(turns.begin(), turns.end());
 371
 372         if (has_invalid_turns)
 373         {
 374             return false;
 375         }
 376
 377         // check if all interior rings are inside the exterior ring
 378         debug_phase::apply(4);
 379
 380         if (! has_holes_inside::apply(polygon,
 381                                       turns.begin(), turns.end(),
 382                                       visitor))
 383         {
 384             return false;
 385         }
 386
 387         // check whether the interior of the polygon is a connected set
 388         debug_phase::apply(5);
 389
 390         return has_connected_interior::apply(polygon,
 391                                              turns.begin(),
 392                                              turns.end(),
 393                                              visitor);
 394     }
 395 };
 396
 397
 398 }} // namespace detail::is_valid
 399 #endif // DOXYGEN_NO_DETAIL
 400
 401
 402
 403 #ifndef DOXYGEN_NO_DISPATCH
 404 namespace dispatch
 405 {
 406
 407
 408 // A Polygon is always a simple geometric object provided that it is valid.
 409 //
 410 // Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1)
 411 template <typename Polygon, bool AllowEmptyMultiGeometries>
 412 struct is_valid
 413     <
 414         Polygon, polygon_tag, AllowEmptyMultiGeometries
 415     > : detail::is_valid::is_valid_polygon<Polygon>
 416 {};
 417
 418
 419 } // namespace dispatch
 420 #endif // DOXYGEN_NO_DISPATCH
 421
 422
 423 }} // namespace boost::geometry
 424
 425 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP