1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2008-2012 Bruno Lalande, Paris, France.
5 // Copyright (c) 2009-2012 Mateusz Loskot, London, UK.
6 
7 // This file was modified by Oracle on 2013.
8 // Modifications copyright (c) 2013, Oracle and/or its affiliates.
9 
10 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
11 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
12 
13 // Use, modification and distribution is subject to the Boost Software License,
14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
15 // http://www.boost.org/LICENSE_1_0.txt)
16 
17 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_WITHIN_NO_TURNS_HPP
18 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_WITHIN_NO_TURNS_HPP
19 
20 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
21 #include <boost/geometry/algorithms/detail/within/point_in_geometry.hpp>
22 
23 namespace boost { namespace geometry {
24 
25 #ifndef DOXYGEN_NO_DETAIL
26 namespace detail_dispatch { namespace within {
27 
28 // returns true if G1 is within G2
29 // this function should be called only if there are no intersection points
30 // otherwise it may return invalid result
31 // e.g. when non-first point of G1 is outside G2 or when some rings of G1 are the same as rings of G2
32 
33 template <typename Geometry1,
34           typename Geometry2,
35           typename Tag1 = typename geometry::tag<Geometry1>::type,
36           typename Tag2 = typename geometry::tag<Geometry2>::type>
37 struct within_no_turns
38 {
39     template <typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::within_no_turns40     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
41     {
42         typedef typename geometry::point_type<Geometry1>::type point1_type;
43         point1_type p;
44         if ( !geometry::point_on_border(p, geometry1) )
45             return false;
46 
47         return detail::within::point_in_geometry(p, geometry2, strategy) >= 0;
48     }
49 };
50 
51 template <typename Geometry1, typename Geometry2>
52 struct within_no_turns<Geometry1, Geometry2, ring_tag, polygon_tag>
53 {
54     template <typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::within_no_turns55     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
56     {
57         typedef typename geometry::point_type<Geometry1>::type point1_type;
58         typedef typename geometry::point_type<Geometry2>::type point2_type;
59         point1_type p;
60         if ( !geometry::point_on_border(p, geometry1) )
61             return false;
62         // check if one of ring points is outside the polygon
63         if ( detail::within::point_in_geometry(p, geometry2, strategy) < 0 )
64             return false;
65         // Now check if holes of G2 aren't inside G1
66         typedef typename boost::range_const_iterator
67             <
68                 typename geometry::interior_type<Geometry2>::type
69             >::type iterator;
70         for ( iterator it = boost::begin(geometry::interior_rings(geometry2)) ;
71               it != boost::end(geometry::interior_rings(geometry2)) ;
72               ++it )
73         {
74             point2_type p;
75             if ( !geometry::point_on_border(p, *it) )
76                 return false;
77             if ( detail::within::point_in_geometry(p, geometry1, strategy) > 0 )
78                 return false;
79         }
80         return true;
81     }
82 };
83 
84 template <typename Geometry1, typename Geometry2>
85 struct within_no_turns<Geometry1, Geometry2, polygon_tag, polygon_tag>
86 {
87     template <typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::within_no_turns88     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
89     {
90         typedef typename geometry::point_type<Geometry1>::type point1_type;
91         typedef typename geometry::point_type<Geometry2>::type point2_type;
92         point1_type p;
93         if ( !geometry::point_on_border(p, geometry1) )
94             return false;
95         // check if one of ring points is outside the polygon
96         if ( detail::within::point_in_geometry(p, geometry2, strategy) < 0 )
97             return false;
98         // Now check if holes of G2 aren't inside G1
99         typedef typename boost::range_const_iterator
100             <
101                 typename geometry::interior_type<Geometry2>::type
102             >::type iterator2;
103         for ( iterator2 it = boost::begin(geometry::interior_rings(geometry2)) ;
104               it != boost::end(geometry::interior_rings(geometry2)) ;
105               ++it )
106         {
107             point2_type p2;
108             if ( !geometry::point_on_border(p2, *it) )
109                 return false;
110             // if the hole of G2 is inside G1
111             if ( detail::within::point_in_geometry(p2, geometry1, strategy) > 0 )
112             {
113                 // if it's also inside one of the G1 holes, it's ok
114                 bool ok = false;
115                 typedef typename boost::range_const_iterator
116                     <
117                         typename geometry::interior_type<Geometry1>::type
118                     >::type iterator1;
119                 for ( iterator1 it1 = boost::begin(geometry::interior_rings(geometry1)) ;
120                       it1 != boost::end(geometry::interior_rings(geometry1)) ;
121                       ++it1 )
122                 {
123                     if ( detail::within::point_in_geometry(p2, *it1, strategy) < 0 )
124                     {
125                         ok = true;
126                         break;
127                     }
128                 }
129                 if ( !ok )
130                     return false;
131             }
132         }
133         return true;
134     }
135 };
136 
137 template <typename Geometry1,
138           typename Geometry2,
139           typename Tag1 = typename geometry::tag<Geometry1>::type,
140           typename Tag2 = typename geometry::tag<Geometry2>::type,
141           bool IsMulti1 = boost::is_base_of<geometry::multi_tag, Tag1>::value,
142           bool IsMulti2 = boost::is_base_of<geometry::multi_tag, Tag2>::value>
143 struct within_no_turns_multi
144 {
145     template <typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::within_no_turns_multi146     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
147     {
148         return within_no_turns<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
149     }
150 };
151 
152 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
153 struct within_no_turns_multi<Geometry1, Geometry2, Tag1, Tag2, true, false>
154 {
155     template <typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::within_no_turns_multi156     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
157     {
158         // All values of G1 must be inside G2
159         typedef typename boost::range_value<Geometry1>::type subgeometry1;
160         typedef typename boost::range_const_iterator<Geometry1>::type iterator;
161         for ( iterator it = boost::begin(geometry1) ; it != boost::end(geometry1) ; ++it )
162         {
163             if ( !within_no_turns<subgeometry1, Geometry2>::apply(*it, geometry2, strategy) )
164                 return false;
165         }
166         return true;
167     }
168 };
169 
170 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
171 struct within_no_turns_multi<Geometry1, Geometry2, Tag1, Tag2, false, true>
172 {
173     template <typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::within_no_turns_multi174     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
175     {
176         // G1 must be within at least one value of G2
177         typedef typename boost::range_value<Geometry2>::type subgeometry2;
178         typedef typename boost::range_const_iterator<Geometry2>::type iterator;
179         for ( iterator it = boost::begin(geometry2) ; it != boost::end(geometry2) ; ++it )
180         {
181             if ( within_no_turns<Geometry1, subgeometry2>::apply(geometry1, *it, strategy) )
182                 return true;
183         }
184         return false;
185     }
186 };
187 
188 template <typename Geometry1, typename Geometry2, typename Tag1, typename Tag2>
189 struct within_no_turns_multi<Geometry1, Geometry2, Tag1, Tag2, true, true>
190 {
191     template <typename Strategy> static inline
applyboost::geometry::detail_dispatch::within::within_no_turns_multi192     bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
193     {
194         // each value of G1 must be inside at least one value of G2
195         typedef typename boost::range_value<Geometry1>::type subgeometry1;
196         typedef typename boost::range_const_iterator<Geometry1>::type iterator;
197         for ( iterator it = boost::begin(geometry1) ; it != boost::end(geometry1) ; ++it )
198         {
199             if ( !within_no_turns_multi<subgeometry1, Geometry2>::apply(*it, geometry2, strategy) )
200                 return false;
201         }
202         return true;
203     }
204 };
205 
206 }} // namespace detail_dispatch::within
207 
208 namespace detail { namespace within {
209 
210 template <typename Geometry1, typename Geometry2, typename Strategy>
within_no_turns(Geometry1 const & geometry1,Geometry2 const & geometry2,Strategy const & strategy)211 inline bool within_no_turns(Geometry1 const& geometry1, Geometry2 const& geometry2, Strategy const& strategy)
212 {
213     return detail_dispatch::within::within_no_turns_multi<Geometry1, Geometry2>::apply(geometry1, geometry2, strategy);
214 }
215 
216 }} // namespace detail::within
217 #endif // DOXYGEN_NO_DETAIL
218 
219 }} // namespace boost::geometry
220 
221 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_WITHIN_WITHIN_NO_TURNS_HPP
222