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 // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
7
8 // This file was modified by Oracle on 2017.
9 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11
12 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
13 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
14
15 // Use, modification and distribution is subject to the Boost Software License,
16 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
17 // http://www.boost.org/LICENSE_1_0.txt)
18
19 #ifndef BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP
20 #define BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP
21
22
23 #include <algorithm>
24 #include <cstddef>
25 #include <functional>
26
27 #include <boost/mpl/assert.hpp>
28 #include <boost/range.hpp>
29 #include <boost/type_traits/remove_reference.hpp>
30
31 #include <boost/variant/apply_visitor.hpp>
32 #include <boost/variant/static_visitor.hpp>
33 #include <boost/variant/variant_fwd.hpp>
34
35 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
36
37 #include <boost/geometry/core/closure.hpp>
38 #include <boost/geometry/core/cs.hpp>
39 #include <boost/geometry/core/exterior_ring.hpp>
40 #include <boost/geometry/core/interior_rings.hpp>
41 #include <boost/geometry/core/mutable_range.hpp>
42 #include <boost/geometry/core/ring_type.hpp>
43 #include <boost/geometry/core/tags.hpp>
44
45 #include <boost/geometry/geometries/concepts/check.hpp>
46
47 #include <boost/geometry/algorithms/area.hpp>
48 #include <boost/geometry/algorithms/disjoint.hpp>
49 #include <boost/geometry/algorithms/detail/multi_modify.hpp>
50 #include <boost/geometry/util/order_as_direction.hpp>
51
52 namespace boost { namespace geometry
53 {
54
55 // Silence warning C4127: conditional expression is constant
56 #if defined(_MSC_VER)
57 #pragma warning(push)
58 #pragma warning(disable : 4127)
59 #endif
60
61 #ifndef DOXYGEN_NO_DETAIL
62 namespace detail { namespace correct
63 {
64
65 template <typename Geometry>
66 struct correct_nop
67 {
68 template <typename Strategy>
applyboost::geometry::detail::correct::correct_nop69 static inline void apply(Geometry& , Strategy const& )
70 {}
71 };
72
73
74 template <typename Box, std::size_t Dimension, std::size_t DimensionCount>
75 struct correct_box_loop
76 {
77 typedef typename coordinate_type<Box>::type coordinate_type;
78
applyboost::geometry::detail::correct::correct_box_loop79 static inline void apply(Box& box)
80 {
81 if (get<min_corner, Dimension>(box) > get<max_corner, Dimension>(box))
82 {
83 // Swap the coordinates
84 coordinate_type max_value = get<min_corner, Dimension>(box);
85 coordinate_type min_value = get<max_corner, Dimension>(box);
86 set<min_corner, Dimension>(box, min_value);
87 set<max_corner, Dimension>(box, max_value);
88 }
89
90 correct_box_loop
91 <
92 Box, Dimension + 1, DimensionCount
93 >::apply(box);
94 }
95 };
96
97
98
99 template <typename Box, std::size_t DimensionCount>
100 struct correct_box_loop<Box, DimensionCount, DimensionCount>
101 {
applyboost::geometry::detail::correct::correct_box_loop102 static inline void apply(Box& )
103 {}
104
105 };
106
107
108 // Correct a box: make min/max correct
109 template <typename Box>
110 struct correct_box
111 {
112 template <typename Strategy>
applyboost::geometry::detail::correct::correct_box113 static inline void apply(Box& box, Strategy const& )
114 {
115 // Currently only for Cartesian coordinates
116 // (or spherical without crossing dateline)
117 // Future version: adapt using strategies
118 correct_box_loop
119 <
120 Box, 0, dimension<Box>::type::value
121 >::apply(box);
122 }
123 };
124
125
126 // Close a ring, if not closed
127 template <typename Ring, template <typename> class Predicate>
128 struct correct_ring
129 {
130 typedef typename point_type<Ring>::type point_type;
131 typedef typename coordinate_type<Ring>::type coordinate_type;
132
133 typedef detail::area::ring_area
134 <
135 order_as_direction<geometry::point_order<Ring>::value>::value,
136 geometry::closure<Ring>::value
137 > ring_area_type;
138
139
140 template <typename Strategy>
applyboost::geometry::detail::correct::correct_ring141 static inline void apply(Ring& r, Strategy const& strategy)
142 {
143 // Check close-ness
144 if (boost::size(r) > 2)
145 {
146 // check if closed, if not, close it
147 bool const disjoint = geometry::disjoint(*boost::begin(r), *(boost::end(r) - 1));
148 closure_selector const s = geometry::closure<Ring>::value;
149
150 if (disjoint && (s == closed))
151 {
152 geometry::append(r, *boost::begin(r));
153 }
154 if (! disjoint && s != closed)
155 {
156 // Open it by removing last point
157 geometry::traits::resize<Ring>::apply(r, boost::size(r) - 1);
158 }
159 }
160 // Check area
161 typedef typename Strategy::return_type area_result_type;
162 Predicate<area_result_type> predicate;
163 area_result_type const zero = 0;
164 if (predicate(ring_area_type::apply(r, strategy), zero))
165 {
166 std::reverse(boost::begin(r), boost::end(r));
167 }
168 }
169 };
170
171 // Correct a polygon: normalizes all rings, sets outer ring clockwise, sets all
172 // inner rings counter clockwise (or vice versa depending on orientation)
173 template <typename Polygon>
174 struct correct_polygon
175 {
176 typedef typename ring_type<Polygon>::type ring_type;
177
178 template <typename Strategy>
applyboost::geometry::detail::correct::correct_polygon179 static inline void apply(Polygon& poly, Strategy const& strategy)
180 {
181 correct_ring
182 <
183 ring_type,
184 std::less
185 >::apply(exterior_ring(poly), strategy);
186
187 typename interior_return_type<Polygon>::type
188 rings = interior_rings(poly);
189 for (typename detail::interior_iterator<Polygon>::type
190 it = boost::begin(rings); it != boost::end(rings); ++it)
191 {
192 correct_ring
193 <
194 ring_type,
195 std::greater
196 >::apply(*it, strategy);
197 }
198 }
199 };
200
201
202 }} // namespace detail::correct
203 #endif // DOXYGEN_NO_DETAIL
204
205
206 #ifndef DOXYGEN_NO_DISPATCH
207 namespace dispatch
208 {
209
210 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
211 struct correct: not_implemented<Tag>
212 {};
213
214 template <typename Point>
215 struct correct<Point, point_tag>
216 : detail::correct::correct_nop<Point>
217 {};
218
219 template <typename LineString>
220 struct correct<LineString, linestring_tag>
221 : detail::correct::correct_nop<LineString>
222 {};
223
224 template <typename Segment>
225 struct correct<Segment, segment_tag>
226 : detail::correct::correct_nop<Segment>
227 {};
228
229
230 template <typename Box>
231 struct correct<Box, box_tag>
232 : detail::correct::correct_box<Box>
233 {};
234
235 template <typename Ring>
236 struct correct<Ring, ring_tag>
237 : detail::correct::correct_ring
238 <
239 Ring,
240 std::less
241 >
242 {};
243
244 template <typename Polygon>
245 struct correct<Polygon, polygon_tag>
246 : detail::correct::correct_polygon<Polygon>
247 {};
248
249
250 template <typename MultiPoint>
251 struct correct<MultiPoint, multi_point_tag>
252 : detail::correct::correct_nop<MultiPoint>
253 {};
254
255
256 template <typename MultiLineString>
257 struct correct<MultiLineString, multi_linestring_tag>
258 : detail::correct::correct_nop<MultiLineString>
259 {};
260
261
262 template <typename Geometry>
263 struct correct<Geometry, multi_polygon_tag>
264 : detail::multi_modify
265 <
266 Geometry,
267 detail::correct::correct_polygon
268 <
269 typename boost::range_value<Geometry>::type
270 >
271 >
272 {};
273
274
275 } // namespace dispatch
276 #endif // DOXYGEN_NO_DISPATCH
277
278
279 namespace resolve_variant {
280
281 template <typename Geometry>
282 struct correct
283 {
284 template <typename Strategy>
applyboost::geometry::resolve_variant::correct285 static inline void apply(Geometry& geometry, Strategy const& strategy)
286 {
287 concepts::check<Geometry const>();
288 dispatch::correct<Geometry>::apply(geometry, strategy);
289 }
290 };
291
292 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
293 struct correct<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
294 {
295 template <typename Strategy>
296 struct visitor: boost::static_visitor<void>
297 {
298 Strategy const& m_strategy;
299
visitorboost::geometry::resolve_variant::correct::visitor300 visitor(Strategy const& strategy): m_strategy(strategy) {}
301
302 template <typename Geometry>
operator ()boost::geometry::resolve_variant::correct::visitor303 void operator()(Geometry& geometry) const
304 {
305 correct<Geometry>::apply(geometry, m_strategy);
306 }
307 };
308
309 template <typename Strategy>
310 static inline void
applyboost::geometry::resolve_variant::correct311 apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry, Strategy const& strategy)
312 {
313 boost::apply_visitor(visitor<Strategy>(strategy), geometry);
314 }
315 };
316
317 } // namespace resolve_variant
318
319
320 /*!
321 \brief Corrects a geometry
322 \details Corrects a geometry: all rings which are wrongly oriented with respect
323 to their expected orientation are reversed. To all rings which do not have a
324 closing point and are typed as they should have one, the first point is
325 appended. Also boxes can be corrected.
326 \ingroup correct
327 \tparam Geometry \tparam_geometry
328 \param geometry \param_geometry which will be corrected if necessary
329
330 \qbk{[include reference/algorithms/correct.qbk]}
331 */
332 template <typename Geometry>
correct(Geometry & geometry)333 inline void correct(Geometry& geometry)
334 {
335 typedef typename point_type<Geometry>::type point_type;
336
337 typedef typename strategy::area::services::default_strategy
338 <
339 typename cs_tag<point_type>::type,
340 point_type
341 >::type strategy_type;
342
343 resolve_variant::correct<Geometry>::apply(geometry, strategy_type());
344 }
345
346 /*!
347 \brief Corrects a geometry
348 \details Corrects a geometry: all rings which are wrongly oriented with respect
349 to their expected orientation are reversed. To all rings which do not have a
350 closing point and are typed as they should have one, the first point is
351 appended. Also boxes can be corrected.
352 \ingroup correct
353 \tparam Geometry \tparam_geometry
354 \tparam Strategy \tparam_strategy{Area}
355 \param geometry \param_geometry which will be corrected if necessary
356 \param strategy \param_strategy{area}
357
358 \qbk{distinguish,with strategy}
359
360 \qbk{[include reference/algorithms/correct.qbk]}
361 */
362 template <typename Geometry, typename Strategy>
correct(Geometry & geometry,Strategy const & strategy)363 inline void correct(Geometry& geometry, Strategy const& strategy)
364 {
365 resolve_variant::correct<Geometry>::apply(geometry, strategy);
366 }
367
368 #if defined(_MSC_VER)
369 #pragma warning(pop)
370 #endif
371
372 }} // namespace boost::geometry
373
374
375 #endif // BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP
376