1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2014-2017, 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 std::iterator_traits<PolygonIterator>::value_type polygon_type;
120         typedef typename Strategy::template point_in_geometry_strategy
121             <
122                 polygon_type, polygon_type
123             >::type within_strategy_type;
124         within_strategy_type const within_strategy
125             = strategy.template get_point_in_geometry_strategy<polygon_type, polygon_type>();
126         typedef typename Strategy::envelope_strategy_type envelope_strategy_type;
127         envelope_strategy_type const envelope_strategy
128             = strategy.get_envelope_strategy();
129 
130         // call partition to check if polygons are disjoint from each other
131         typename base::template item_visitor_type<within_strategy_type> item_visitor(within_strategy);
132 
133         geometry::partition
134             <
135                 geometry::model::box<typename point_type<MultiPolygon>::type>
136             >::apply(polygon_iterators, item_visitor,
137                      typename base::template expand_box<envelope_strategy_type>(envelope_strategy),
138                      typename base::template overlaps_box<envelope_strategy_type>(envelope_strategy));
139 
140         if (item_visitor.items_overlap)
141         {
142             return visitor.template apply<failure_intersecting_interiors>();
143         }
144         else
145         {
146             return visitor.template apply<no_failure>();
147         }
148     }
149 
150 
151 
152     class has_multi_index
153     {
154     public:
has_multi_index(signed_size_type multi_index)155         has_multi_index(signed_size_type multi_index)
156             : m_multi_index(multi_index)
157         {}
158 
159         template <typename Turn>
operator ()(Turn const & turn) const160         inline bool operator()(Turn const& turn) const
161         {
162             return turn.operations[0].seg_id.multi_index == m_multi_index
163                 && turn.operations[1].seg_id.multi_index == m_multi_index;
164         }
165 
166     private:
167         signed_size_type const m_multi_index;
168     };
169 
170 
171 
172     template <typename Predicate>
173     struct has_property_per_polygon
174     {
175         template
176         <
177             typename PolygonIterator,
178             typename TurnIterator,
179             typename VisitPolicy,
180             typename Strategy
181         >
applyboost::geometry::detail::is_valid::is_valid_multipolygon::has_property_per_polygon182         static inline bool apply(PolygonIterator polygons_first,
183                                  PolygonIterator polygons_beyond,
184                                  TurnIterator turns_first,
185                                  TurnIterator turns_beyond,
186                                  VisitPolicy& visitor,
187                                  Strategy const& strategy)
188         {
189             signed_size_type multi_index = 0;
190             for (PolygonIterator it = polygons_first; it != polygons_beyond;
191                  ++it, ++multi_index)
192             {
193                 has_multi_index index_predicate(multi_index);
194 
195                 typedef boost::filter_iterator
196                     <
197                         has_multi_index, TurnIterator
198                     > filtered_turn_iterator;
199 
200                 filtered_turn_iterator filtered_turns_first(index_predicate,
201                                                             turns_first,
202                                                             turns_beyond);
203 
204                 filtered_turn_iterator filtered_turns_beyond(index_predicate,
205                                                              turns_beyond,
206                                                              turns_beyond);
207 
208                 if (! Predicate::apply(*it,
209                                        filtered_turns_first,
210                                        filtered_turns_beyond,
211                                        visitor,
212                                        strategy))
213                 {
214                     return false;
215                 }
216             }
217             return true;
218         }
219     };
220 
221 
222 
223     template
224     <
225         typename PolygonIterator,
226         typename TurnIterator,
227         typename VisitPolicy,
228         typename Strategy
229     >
have_holes_inside(PolygonIterator polygons_first,PolygonIterator polygons_beyond,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor,Strategy const & strategy)230     static inline bool have_holes_inside(PolygonIterator polygons_first,
231                                          PolygonIterator polygons_beyond,
232                                          TurnIterator turns_first,
233                                          TurnIterator turns_beyond,
234                                          VisitPolicy& visitor,
235                                          Strategy const& strategy)
236     {
237         return has_property_per_polygon
238             <
239                 typename base::has_holes_inside
240             >::apply(polygons_first, polygons_beyond,
241                      turns_first, turns_beyond, visitor, strategy);
242     }
243 
244 
245 
246     template
247     <
248         typename PolygonIterator,
249         typename TurnIterator,
250         typename VisitPolicy,
251         typename Strategy
252     >
have_connected_interior(PolygonIterator polygons_first,PolygonIterator polygons_beyond,TurnIterator turns_first,TurnIterator turns_beyond,VisitPolicy & visitor,Strategy const & strategy)253     static inline bool have_connected_interior(PolygonIterator polygons_first,
254                                                PolygonIterator polygons_beyond,
255                                                TurnIterator turns_first,
256                                                TurnIterator turns_beyond,
257                                                VisitPolicy& visitor,
258                                                Strategy const& strategy)
259     {
260         return has_property_per_polygon
261             <
262                 typename base::has_connected_interior
263             >::apply(polygons_first, polygons_beyond,
264                      turns_first, turns_beyond, visitor, strategy);
265     }
266 
267 
268     template <typename VisitPolicy, typename Strategy>
269     struct per_polygon
270     {
per_polygonboost::geometry::detail::is_valid::is_valid_multipolygon::per_polygon271         per_polygon(VisitPolicy& policy, Strategy const& strategy)
272             : m_policy(policy)
273             , m_strategy(strategy)
274         {}
275 
276         template <typename Polygon>
applyboost::geometry::detail::is_valid::is_valid_multipolygon::per_polygon277         inline bool apply(Polygon const& polygon) const
278         {
279             return base::apply(polygon, m_policy, m_strategy);
280         }
281 
282         VisitPolicy& m_policy;
283         Strategy const& m_strategy;
284     };
285 public:
286     template <typename VisitPolicy, typename Strategy>
apply(MultiPolygon const & multipolygon,VisitPolicy & visitor,Strategy const & strategy)287     static inline bool apply(MultiPolygon const& multipolygon,
288                              VisitPolicy& visitor,
289                              Strategy const& strategy)
290     {
291         typedef debug_validity_phase<MultiPolygon> debug_phase;
292 
293         if (BOOST_GEOMETRY_CONDITION(
294                 AllowEmptyMultiGeometries && boost::empty(multipolygon)))
295         {
296             return visitor.template apply<no_failure>();
297         }
298 
299         // check validity of all polygons ring
300         debug_phase::apply(1);
301 
302         if (! detail::check_iterator_range
303                   <
304                       per_polygon<VisitPolicy, Strategy>,
305                       false // do not check for empty multipolygon (done above)
306                   >::apply(boost::begin(multipolygon),
307                            boost::end(multipolygon),
308                            per_polygon<VisitPolicy, Strategy>(visitor, strategy)))
309         {
310             return false;
311         }
312 
313 
314         // compute turns and check if all are acceptable
315         debug_phase::apply(2);
316 
317         typedef has_valid_self_turns<MultiPolygon> has_valid_turns;
318 
319         std::deque<typename has_valid_turns::turn_type> turns;
320         bool has_invalid_turns =
321             ! has_valid_turns::apply(multipolygon, turns, visitor, strategy);
322         debug_print_turns(turns.begin(), turns.end());
323 
324         if (has_invalid_turns)
325         {
326             return false;
327         }
328 
329 
330         // check if each polygon's interior rings are inside the
331         // exterior and not one inside the other
332         debug_phase::apply(3);
333 
334         if (! have_holes_inside(boost::begin(multipolygon),
335                                 boost::end(multipolygon),
336                                 turns.begin(),
337                                 turns.end(),
338                                 visitor,
339                                 strategy))
340         {
341             return false;
342         }
343 
344 
345         // check that each polygon's interior is connected
346         debug_phase::apply(4);
347 
348         if (! have_connected_interior(boost::begin(multipolygon),
349                                       boost::end(multipolygon),
350                                       turns.begin(),
351                                       turns.end(),
352                                       visitor,
353                                       strategy))
354         {
355             return false;
356         }
357 
358 
359         // check if polygon interiors are disjoint
360         debug_phase::apply(5);
361         return are_polygon_interiors_disjoint(boost::begin(multipolygon),
362                                               boost::end(multipolygon),
363                                               turns.begin(),
364                                               turns.end(),
365                                               visitor,
366                                               strategy);
367     }
368 };
369 
370 }} // namespace detail::is_valid
371 #endif // DOXYGEN_NO_DETAIL
372 
373 
374 
375 #ifndef DOXYGEN_NO_DISPATCH
376 namespace dispatch
377 {
378 
379 
380 // Not clear what the definition is.
381 // Right now we check that each element is simple (in fact valid), and
382 // that the MultiPolygon is also valid.
383 //
384 // Reference (for validity of MultiPolygons): OGC 06-103r4 (6.1.14)
385 template <typename MultiPolygon, bool AllowEmptyMultiGeometries>
386 struct is_valid
387     <
388         MultiPolygon, multi_polygon_tag, AllowEmptyMultiGeometries
389     > : detail::is_valid::is_valid_multipolygon
390         <
391             MultiPolygon, AllowEmptyMultiGeometries
392         >
393 {};
394 
395 
396 } // namespace dispatch
397 #endif // DOXYGEN_NO_DISPATCH
398 
399 
400 }} // namespace boost::geometry
401 
402 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP
403