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 2017.
8 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10 
11 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
12 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
13 
14 // Use, modification and distribution is subject to the Boost Software License,
15 // Version 1.Dimension. (See accompanying file LICENSE_1_0.txt or copy at
16 // http://www.boost.org/LICENSE_1_0.txt)
17 
18 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_ON_BORDER_HPP
19 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_ON_BORDER_HPP
20 
21 
22 #include <cstddef>
23 
24 #include <boost/range.hpp>
25 #include <boost/static_assert.hpp>
26 
27 #include <boost/geometry/core/tags.hpp>
28 #include <boost/geometry/core/point_type.hpp>
29 #include <boost/geometry/core/ring_type.hpp>
30 
31 #include <boost/geometry/geometries/concepts/check.hpp>
32 
33 #include <boost/geometry/algorithms/assign.hpp>
34 #include <boost/geometry/algorithms/detail/convert_point_to_point.hpp>
35 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
36 
37 #include <boost/geometry/util/condition.hpp>
38 
39 
40 namespace boost { namespace geometry
41 {
42 
43 
44 #ifndef DOXYGEN_NO_DETAIL
45 namespace detail { namespace point_on_border
46 {
47 
48 
49 struct get_point
50 {
51     template <typename Point>
applyboost::geometry::detail::point_on_border::get_point52     static inline bool apply(Point& destination, Point const& source)
53     {
54         destination = source;
55         return true;
56     }
57 };
58 
59 template<typename Point, std::size_t Dimension, std::size_t DimensionCount>
60 struct midpoint_helper
61 {
62     template <typename InputPoint>
applyboost::geometry::detail::point_on_border::midpoint_helper63     static inline bool apply(Point& p, InputPoint const& p1, InputPoint const& p2)
64     {
65         typename coordinate_type<Point>::type const two = 2;
66         set<Dimension>(p,
67                     (get<Dimension>(p1) + get<Dimension>(p2)) / two);
68         return midpoint_helper<Point, Dimension + 1, DimensionCount>::apply(p, p1, p2);
69     }
70 };
71 
72 
73 template <typename Point, std::size_t DimensionCount>
74 struct midpoint_helper<Point, DimensionCount, DimensionCount>
75 {
76     template <typename InputPoint>
applyboost::geometry::detail::point_on_border::midpoint_helper77     static inline bool apply(Point& , InputPoint const& , InputPoint const& )
78     {
79         return true;
80     }
81 };
82 
83 
84 template <bool Midpoint>
85 struct point_on_range
86 {
87     // Version with iterator
88     template<typename Point, typename Iterator>
applyboost::geometry::detail::point_on_border::point_on_range89     static inline bool apply(Point& point, Iterator begin, Iterator end)
90     {
91         Iterator it = begin;
92         if (it == end)
93         {
94             return false;
95         }
96 
97         if (! Midpoint)
98         {
99             geometry::detail::conversion::convert_point_to_point(*it, point);
100             return true;
101         }
102 
103         Iterator prev = it++;
104 
105         // Go to next non-duplicate point
106         while (it != end
107             && detail::equals::equals_point_point(*it, *prev))
108         {
109             prev = it++;
110         }
111         if (it != end)
112         {
113             return midpoint_helper
114                 <
115                     Point,
116                     0, dimension<Point>::value
117                 >::apply(point, *prev, *it);
118         }
119         return false;
120     }
121 
122     // Version with range
123     template<typename Point, typename Range>
applyboost::geometry::detail::point_on_border::point_on_range124     static inline bool apply(Point& point, Range const& range)
125     {
126         typedef typename geometry::cs_tag<Point>::type cs_tag;
127         BOOST_STATIC_ASSERT((! Midpoint || boost::is_same<cs_tag, cartesian_tag>::value));
128 
129         return apply(point, boost::begin(range), boost::end(range));
130     }
131 };
132 
133 
134 template <bool Midpoint>
135 struct point_on_polygon
136 {
137     template<typename Point, typename Polygon>
applyboost::geometry::detail::point_on_border::point_on_polygon138     static inline bool apply(Point& point, Polygon const& polygon)
139     {
140         return point_on_range
141             <
142                 Midpoint
143             >::apply(point, exterior_ring(polygon));
144     }
145 };
146 
147 
148 template <bool Midpoint>
149 struct point_on_box
150 {
151     template<typename Point, typename Box>
applyboost::geometry::detail::point_on_border::point_on_box152     static inline bool apply(Point& point, Box const& box)
153     {
154         if (BOOST_GEOMETRY_CONDITION(Midpoint))
155         {
156             Point p1, p2;
157             detail::assign::assign_box_2d_corner<min_corner, min_corner>(box, p1);
158             detail::assign::assign_box_2d_corner<max_corner, min_corner>(box, p2);
159             midpoint_helper
160                 <
161                     Point,
162                     0, dimension<Point>::value
163                 >::apply(point, p1, p2);
164         }
165         else
166         {
167             detail::assign::assign_box_2d_corner<min_corner, min_corner>(box, point);
168         }
169 
170         return true;
171     }
172 };
173 
174 
175 template <typename Policy>
176 struct point_on_multi
177 {
178     template<typename Point, typename MultiGeometry>
applyboost::geometry::detail::point_on_border::point_on_multi179     static inline bool apply(Point& point, MultiGeometry const& multi)
180     {
181         // Take a point on the first multi-geometry
182         // (i.e. the first that is not empty)
183         for (typename boost::range_iterator
184                 <
185                     MultiGeometry const
186                 >::type it = boost::begin(multi);
187             it != boost::end(multi);
188             ++it)
189         {
190             if (Policy::apply(point, *it))
191             {
192                 return true;
193             }
194         }
195         return false;
196     }
197 };
198 
199 
200 }} // namespace detail::point_on_border
201 #endif // DOXYGEN_NO_DETAIL
202 
203 
204 #ifndef DOXYGEN_NO_DISPATCH
205 namespace dispatch
206 {
207 
208 
209 template
210 <
211     typename GeometryTag,
212     bool Midpoint
213 
214 >
215 struct point_on_border
216 {};
217 
218 
219 template <bool Midpoint>
220 struct point_on_border<point_tag, Midpoint>
221     : detail::point_on_border::get_point
222 {};
223 
224 
225 template <bool Midpoint>
226 struct point_on_border<linestring_tag, Midpoint>
227     : detail::point_on_border::point_on_range<Midpoint>
228 {};
229 
230 
231 template <bool Midpoint>
232 struct point_on_border<ring_tag, Midpoint>
233     : detail::point_on_border::point_on_range<Midpoint>
234 {};
235 
236 
237 template <bool Midpoint>
238 struct point_on_border<polygon_tag, Midpoint>
239     : detail::point_on_border::point_on_polygon<Midpoint>
240 {};
241 
242 
243 template <bool Midpoint>
244 struct point_on_border<box_tag, Midpoint>
245     : detail::point_on_border::point_on_box<Midpoint>
246 {};
247 
248 
249 template <bool Midpoint>
250 struct point_on_border<multi_polygon_tag, Midpoint>
251     : detail::point_on_border::point_on_multi
252         <
253             detail::point_on_border::point_on_polygon<Midpoint>
254         >
255 {};
256 
257 
258 template <bool Midpoint>
259 struct point_on_border<multi_linestring_tag, Midpoint>
260     : detail::point_on_border::point_on_multi
261         <
262             detail::point_on_border::point_on_range<Midpoint>
263         >
264 {};
265 
266 
267 } // namespace dispatch
268 #endif // DOXYGEN_NO_DISPATCH
269 
270 
271 /*!
272 \brief Take point on a border
273 \ingroup overlay
274 \tparam Geometry geometry type. This also defines the type of the output point
275 \param point to assign
276 \param geometry geometry to take point from
277 \return TRUE if successful, else false.
278     It is only false if polygon/line have no points
279 \note for a polygon, it is always a point on the exterior ring
280  */
281 template <typename Point, typename Geometry>
point_on_border(Point & point,Geometry const & geometry)282 inline bool point_on_border(Point& point, Geometry const& geometry)
283 {
284     concepts::check<Point>();
285     concepts::check<Geometry const>();
286 
287     return dispatch::point_on_border
288             <
289                 typename tag<Geometry>::type,
290                 false
291             >::apply(point, geometry);
292 }
293 
294 
295 /*!
296 \tparam Midpoint boolean flag, true if the point should not be a vertex, but some point
297     in between of two vertices
298 \note for Midpoint, it is not taken from two consecutive duplicate vertices,
299     (unless there are no other).
300  */
301 /*
302 template <bool Midpoint, typename Point, typename Geometry>
303 inline bool point_on_border(Point& point, Geometry const& geometry)
304 {
305     concepts::check<Point>();
306     concepts::check<Geometry const>();
307 
308     return dispatch::point_on_border
309             <
310                 typename tag<Geometry>::type,
311                 Midpoint
312             >::apply(point, geometry);
313 }
314 */
315 
316 }} // namespace boost::geometry
317 
318 
319 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_POINT_ON_BORDER_HPP
320