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_DISJOINT_MULTIPOINT_GEOMETRY_HPP
11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP
12 
13 #include <algorithm>
14 #include <vector>
15 
16 #include <boost/range.hpp>
17 
18 #include <boost/geometry/core/assert.hpp>
19 #include <boost/geometry/core/tags.hpp>
20 
21 #include <boost/geometry/geometries/box.hpp>
22 
23 #include <boost/geometry/iterators/segment_iterator.hpp>
24 
25 #include <boost/geometry/algorithms/envelope.hpp>
26 #include <boost/geometry/algorithms/expand.hpp>
27 
28 #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
29 #include <boost/geometry/algorithms/detail/partition.hpp>
30 #include <boost/geometry/algorithms/detail/disjoint/multirange_geometry.hpp>
31 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
32 #include <boost/geometry/algorithms/detail/disjoint/point_geometry.hpp>
33 #include <boost/geometry/algorithms/detail/relate/less.hpp>
34 
35 #include <boost/geometry/algorithms/dispatch/disjoint.hpp>
36 
37 
38 namespace boost { namespace geometry
39 {
40 
41 
42 #ifndef DOXYGEN_NO_DETAIL
43 namespace detail { namespace disjoint
44 {
45 
46 
47 template <typename MultiPoint1, typename MultiPoint2>
48 class multipoint_multipoint
49 {
50 private:
51     template <typename Iterator>
52     class unary_disjoint_predicate
53         : detail::relate::less
54     {
55     private:
56         typedef detail::relate::less base_type;
57 
58     public:
unary_disjoint_predicate(Iterator first,Iterator last)59         unary_disjoint_predicate(Iterator first, Iterator last)
60             : base_type(), m_first(first), m_last(last)
61         {}
62 
63         template <typename Point>
apply(Point const & point) const64         inline bool apply(Point const& point) const
65         {
66             return !std::binary_search(m_first,
67                                        m_last,
68                                        point,
69                                        static_cast<base_type const&>(*this));
70         }
71 
72     private:
73         Iterator m_first, m_last;
74     };
75 
76 public:
apply(MultiPoint1 const & multipoint1,MultiPoint2 const & multipoint2)77     static inline bool apply(MultiPoint1 const& multipoint1,
78                              MultiPoint2 const& multipoint2)
79     {
80         BOOST_GEOMETRY_ASSERT( boost::size(multipoint1) <= boost::size(multipoint2) );
81 
82         typedef typename boost::range_value<MultiPoint1>::type point1_type;
83 
84         std::vector<point1_type> points1(boost::begin(multipoint1),
85                                          boost::end(multipoint1));
86 
87         std::sort(points1.begin(), points1.end(), detail::relate::less());
88 
89         typedef unary_disjoint_predicate
90             <
91                 typename std::vector<point1_type>::const_iterator
92             > predicate_type;
93 
94         return check_iterator_range
95             <
96                 predicate_type
97             >::apply(boost::begin(multipoint2),
98                      boost::end(multipoint2),
99                      predicate_type(points1.begin(), points1.end()));
100     }
101 };
102 
103 
104 template <typename MultiPoint, typename Linear>
105 class multipoint_linear
106 {
107 private:
108     // structs for partition -- start
109     struct expand_box
110     {
111         template <typename Box, typename Geometry>
applyboost::geometry::detail::disjoint::multipoint_linear::expand_box112         static inline void apply(Box& total, Geometry const& geometry)
113         {
114             geometry::expand(total, geometry::return_envelope<Box>(geometry));
115         }
116 
117     };
118 
119     struct overlaps_box
120     {
121         template <typename Box, typename Geometry>
applyboost::geometry::detail::disjoint::multipoint_linear::overlaps_box122         static inline bool apply(Box const& box, Geometry const& geometry)
123         {
124             return ! dispatch::disjoint<Geometry, Box>::apply(geometry, box);
125         }
126     };
127 
128     class item_visitor_type
129     {
130     public:
item_visitor_type()131         item_visitor_type() : m_intersection_found(false) {}
132 
133         template <typename Item1, typename Item2>
apply(Item1 const & item1,Item2 const & item2)134         inline void apply(Item1 const& item1, Item2 const& item2)
135         {
136             if (! m_intersection_found
137                 && ! dispatch::disjoint<Item1, Item2>::apply(item1, item2))
138             {
139                 m_intersection_found = true;
140             }
141         }
142 
intersection_found() const143         inline bool intersection_found() const { return m_intersection_found; }
144 
145     private:
146         bool m_intersection_found;
147     };
148     // structs for partition -- end
149 
150     class segment_range
151     {
152     public:
153         typedef geometry::segment_iterator<Linear const> const_iterator;
154         typedef const_iterator iterator;
155 
segment_range(Linear const & linear)156         segment_range(Linear const& linear)
157             : m_linear(linear)
158         {}
159 
begin() const160         const_iterator begin() const
161         {
162             return geometry::segments_begin(m_linear);
163         }
164 
end() const165         const_iterator end() const
166         {
167             return geometry::segments_end(m_linear);
168         }
169 
170     private:
171         Linear const& m_linear;
172     };
173 
174 public:
apply(MultiPoint const & multipoint,Linear const & linear)175     static inline bool apply(MultiPoint const& multipoint, Linear const& linear)
176     {
177         item_visitor_type visitor;
178 
179         geometry::partition
180             <
181                 geometry::model::box<typename point_type<MultiPoint>::type>,
182                 expand_box,
183                 overlaps_box
184             >::apply(multipoint, segment_range(linear), visitor);
185 
186         return ! visitor.intersection_found();
187     }
188 
apply(Linear const & linear,MultiPoint const & multipoint)189     static inline bool apply(Linear const& linear, MultiPoint const& multipoint)
190     {
191         return apply(multipoint, linear);
192     }
193 };
194 
195 
196 }} // namespace detail::disjoint
197 #endif // DOXYGEN_NO_DETAIL
198 
199 
200 
201 
202 #ifndef DOXYGEN_NO_DISPATCH
203 namespace dispatch
204 {
205 
206 
207 template <typename Point, typename MultiPoint, std::size_t DimensionCount>
208 struct disjoint
209     <
210         Point, MultiPoint, DimensionCount, point_tag, multi_point_tag, false
211     > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Point>
212 {};
213 
214 
215 template <typename MultiPoint, typename Segment, std::size_t DimensionCount>
216 struct disjoint
217     <
218         MultiPoint, Segment, DimensionCount, multi_point_tag, segment_tag, false
219     > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Segment>
220 {};
221 
222 
223 template <typename MultiPoint, typename Box, std::size_t DimensionCount>
224 struct disjoint
225     <
226         MultiPoint, Box, DimensionCount, multi_point_tag, box_tag, false
227     > : detail::disjoint::multirange_constant_size_geometry<MultiPoint, Box>
228 {};
229 
230 
231 template
232 <
233     typename MultiPoint1,
234     typename MultiPoint2,
235     std::size_t DimensionCount
236 >
237 struct disjoint
238     <
239         MultiPoint1, MultiPoint2, DimensionCount,
240         multi_point_tag, multi_point_tag, false
241     >
242 {
applyboost::geometry::dispatch::disjoint243     static inline bool apply(MultiPoint1 const& multipoint1,
244                              MultiPoint2 const& multipoint2)
245     {
246         if ( boost::size(multipoint2) < boost::size(multipoint1) )
247         {
248             return detail::disjoint::multipoint_multipoint
249                 <
250                     MultiPoint2, MultiPoint1
251                 >::apply(multipoint2, multipoint1);
252         }
253 
254         return detail::disjoint::multipoint_multipoint
255             <
256                 MultiPoint1, MultiPoint2
257             >::apply(multipoint1, multipoint2);
258    }
259 };
260 
261 
262 template <typename Linear, typename MultiPoint, std::size_t DimensionCount>
263 struct disjoint
264     <
265         Linear, MultiPoint, DimensionCount, linear_tag, multi_point_tag, false
266     > : detail::disjoint::multipoint_linear<MultiPoint, Linear>
267 {};
268 
269 
270 template <typename MultiPoint, typename Linear, std::size_t DimensionCount>
271 struct disjoint
272     <
273         MultiPoint, Linear, DimensionCount, multi_point_tag, linear_tag, false
274     > : detail::disjoint::multipoint_linear<MultiPoint, Linear>
275 {};
276 
277 
278 } // namespace dispatch
279 #endif // DOXYGEN_NO_DISPATCH
280 
281 
282 }} // namespace boost::geometry
283 
284 
285 
286 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_DISJOINT_MULTIPOINT_GEOMETRY_HPP
287