1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // This file was modified by Oracle on 2013, 2014, 2017.
6 // Modifications copyright (c) 2013-2017, Oracle and/or its affiliates.
7 
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9 
10 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
13 
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP
16 
17 #include <algorithm>
18 #include <vector>
19 
20 #include <boost/range/empty.hpp>
21 
22 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
23 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
24 #include <boost/geometry/algorithms/detail/relate/less.hpp>
25 #include <boost/geometry/algorithms/detail/relate/result.hpp>
26 
27 namespace boost { namespace geometry
28 {
29 
30 #ifndef DOXYGEN_NO_DETAIL
31 namespace detail { namespace relate {
32 
33 template <typename Point1, typename Point2>
34 struct point_point
35 {
36     static const bool interruption_enabled = false;
37 
38     template <typename Result, typename Strategy>
applyboost::geometry::detail::relate::point_point39     static inline void apply(Point1 const& point1, Point2 const& point2,
40                              Result & result,
41                              Strategy const& /*strategy*/)
42     {
43         bool equal = detail::equals::equals_point_point(point1, point2);
44         if ( equal )
45         {
46             relate::set<interior, interior, '0'>(result);
47         }
48         else
49         {
50             relate::set<interior, exterior, '0'>(result);
51             relate::set<exterior, interior, '0'>(result);
52         }
53 
54         relate::set<exterior, exterior, result_dimension<Point1>::value>(result);
55     }
56 };
57 
58 template <typename Point, typename MultiPoint>
point_multipoint_check(Point const & point,MultiPoint const & multi_point)59 std::pair<bool, bool> point_multipoint_check(Point const& point, MultiPoint const& multi_point)
60 {
61     bool found_inside = false;
62     bool found_outside = false;
63 
64     // point_in_geometry could be used here but why iterate over MultiPoint twice?
65     // we must search for a point in the exterior because all points in MultiPoint can be equal
66 
67     typedef typename boost::range_iterator<MultiPoint const>::type iterator;
68     iterator it = boost::begin(multi_point);
69     iterator last = boost::end(multi_point);
70     for ( ; it != last ; ++it )
71     {
72         bool ii = detail::equals::equals_point_point(point, *it);
73 
74         if ( ii )
75             found_inside = true;
76         else
77             found_outside = true;
78 
79         if ( found_inside && found_outside )
80             break;
81     }
82 
83     return std::make_pair(found_inside, found_outside);
84 }
85 
86 template <typename Point, typename MultiPoint, bool Transpose = false>
87 struct point_multipoint
88 {
89     static const bool interruption_enabled = false;
90 
91     template <typename Result, typename Strategy>
applyboost::geometry::detail::relate::point_multipoint92     static inline void apply(Point const& point, MultiPoint const& multi_point,
93                              Result & result,
94                              Strategy const& /*strategy*/)
95     {
96         if ( boost::empty(multi_point) )
97         {
98             // TODO: throw on empty input?
99             relate::set<interior, exterior, '0', Transpose>(result);
100             return;
101         }
102 
103         std::pair<bool, bool> rel = point_multipoint_check(point, multi_point);
104 
105         if ( rel.first ) // some point of MP is equal to P
106         {
107             relate::set<interior, interior, '0', Transpose>(result);
108 
109             if ( rel.second ) // a point of MP was found outside P
110             {
111                 relate::set<exterior, interior, '0', Transpose>(result);
112             }
113         }
114         else
115         {
116             relate::set<interior, exterior, '0', Transpose>(result);
117             relate::set<exterior, interior, '0', Transpose>(result);
118         }
119 
120         relate::set<exterior, exterior, result_dimension<Point>::value, Transpose>(result);
121     }
122 };
123 
124 template <typename MultiPoint, typename Point>
125 struct multipoint_point
126 {
127     static const bool interruption_enabled = false;
128 
129     template <typename Result, typename Strategy>
applyboost::geometry::detail::relate::multipoint_point130     static inline void apply(MultiPoint const& multi_point, Point const& point,
131                              Result & result,
132                              Strategy const& strategy)
133     {
134         point_multipoint<Point, MultiPoint, true>::apply(point, multi_point, result, strategy);
135     }
136 };
137 
138 template <typename MultiPoint1, typename MultiPoint2>
139 struct multipoint_multipoint
140 {
141     static const bool interruption_enabled = true;
142 
143     template <typename Result, typename Strategy>
applyboost::geometry::detail::relate::multipoint_multipoint144     static inline void apply(MultiPoint1 const& multi_point1, MultiPoint2 const& multi_point2,
145                              Result & result,
146                              Strategy const& /*strategy*/)
147     {
148         {
149             // TODO: throw on empty input?
150             bool empty1 = boost::empty(multi_point1);
151             bool empty2 = boost::empty(multi_point2);
152             if ( empty1 && empty2 )
153             {
154                 return;
155             }
156             else if ( empty1 )
157             {
158                 relate::set<exterior, interior, '0'>(result);
159                 return;
160             }
161             else if ( empty2 )
162             {
163                 relate::set<interior, exterior, '0'>(result);
164                 return;
165             }
166         }
167 
168         // The geometry containing smaller number of points will be analysed first
169         if ( boost::size(multi_point1) < boost::size(multi_point2) )
170         {
171             search_both<false>(multi_point1, multi_point2, result);
172         }
173         else
174         {
175             search_both<true>(multi_point2, multi_point1, result);
176         }
177 
178         relate::set<exterior, exterior, result_dimension<MultiPoint1>::value>(result);
179     }
180 
181     template <bool Transpose, typename MPt1, typename MPt2, typename Result>
search_bothboost::geometry::detail::relate::multipoint_multipoint182     static inline void search_both(MPt1 const& first_sorted_mpt, MPt2 const& first_iterated_mpt,
183                                    Result & result)
184     {
185         if ( relate::may_update<interior, interior, '0'>(result)
186           || relate::may_update<interior, exterior, '0'>(result)
187           || relate::may_update<exterior, interior, '0'>(result) )
188         {
189             // NlogN + MlogN
190             bool is_disjoint = search<Transpose>(first_sorted_mpt, first_iterated_mpt, result);
191 
192             if ( BOOST_GEOMETRY_CONDITION(is_disjoint || result.interrupt) )
193                 return;
194         }
195 
196         if ( relate::may_update<interior, interior, '0'>(result)
197           || relate::may_update<interior, exterior, '0'>(result)
198           || relate::may_update<exterior, interior, '0'>(result) )
199         {
200             // MlogM + NlogM
201             search<! Transpose>(first_iterated_mpt, first_sorted_mpt, result);
202         }
203     }
204 
205     template <bool Transpose,
206               typename SortedMultiPoint,
207               typename IteratedMultiPoint,
208               typename Result>
searchboost::geometry::detail::relate::multipoint_multipoint209     static inline bool search(SortedMultiPoint const& sorted_mpt,
210                               IteratedMultiPoint const& iterated_mpt,
211                               Result & result)
212     {
213         // sort points from the 1 MPt
214         typedef typename geometry::point_type<SortedMultiPoint>::type point_type;
215         std::vector<point_type> points(boost::begin(sorted_mpt), boost::end(sorted_mpt));
216         std::sort(points.begin(), points.end(), less());
217 
218         bool found_inside = false;
219         bool found_outside = false;
220 
221         // for each point in the second MPt
222         typedef typename boost::range_iterator<IteratedMultiPoint const>::type iterator;
223         for ( iterator it = boost::begin(iterated_mpt) ;
224               it != boost::end(iterated_mpt) ; ++it )
225         {
226             bool ii =
227                 std::binary_search(points.begin(), points.end(), *it, less());
228             if ( ii )
229                 found_inside = true;
230             else
231                 found_outside = true;
232 
233             if ( found_inside && found_outside )
234                 break;
235         }
236 
237         if ( found_inside ) // some point of MP2 is equal to some of MP1
238         {
239 // TODO: if I/I is set for one MPt, this won't be changed when the other one in analysed
240 //       so if e.g. only I/I must be analysed we musn't check the other MPt
241 
242             relate::set<interior, interior, '0', Transpose>(result);
243 
244             if ( found_outside ) // some point of MP2 was found outside of MP1
245             {
246                 relate::set<exterior, interior, '0', Transpose>(result);
247             }
248         }
249         else
250         {
251             relate::set<interior, exterior, '0', Transpose>(result);
252             relate::set<exterior, interior, '0', Transpose>(result);
253         }
254 
255         // if no point is intersecting the other MPt then we musn't analyse the reversed case
256         return ! found_inside;
257     }
258 };
259 
260 }} // namespace detail::relate
261 #endif // DOXYGEN_NO_DETAIL
262 
263 }} // namespace boost::geometry
264 
265 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_POINT_POINT_HPP
266