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