1 // Boost.Geometry (aka GGL, Generic Geometry Library)
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.
8 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
9 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP
23 #include <boost/mpl/assert.hpp>
24 #include <boost/range.hpp>
25 #include <boost/type_traits/remove_reference.hpp>
27 #include <boost/variant/apply_visitor.hpp>
28 #include <boost/variant/static_visitor.hpp>
29 #include <boost/variant/variant_fwd.hpp>
31 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
33 #include <boost/geometry/core/closure.hpp>
34 #include <boost/geometry/core/cs.hpp>
35 #include <boost/geometry/core/exterior_ring.hpp>
36 #include <boost/geometry/core/interior_rings.hpp>
37 #include <boost/geometry/core/mutable_range.hpp>
38 #include <boost/geometry/core/ring_type.hpp>
39 #include <boost/geometry/core/tags.hpp>
41 #include <boost/geometry/geometries/concepts/check.hpp>
43 #include <boost/geometry/algorithms/area.hpp>
44 #include <boost/geometry/algorithms/disjoint.hpp>
45 #include <boost/geometry/algorithms/detail/multi_modify.hpp>
46 #include <boost/geometry/util/order_as_direction.hpp>
48 namespace boost { namespace geometry
51 // Silence warning C4127: conditional expression is constant
54 #pragma warning(disable : 4127)
57 #ifndef DOXYGEN_NO_DETAIL
58 namespace detail { namespace correct
61 template <typename Geometry>
64 static inline void apply(Geometry& )
69 template <typename Box, std::size_t Dimension, std::size_t DimensionCount>
70 struct correct_box_loop
72 typedef typename coordinate_type<Box>::type coordinate_type;
74 static inline void apply(Box& box)
76 if (get<min_corner, Dimension>(box) > get<max_corner, Dimension>(box))
78 // Swap the coordinates
79 coordinate_type max_value = get<min_corner, Dimension>(box);
80 coordinate_type min_value = get<max_corner, Dimension>(box);
81 set<min_corner, Dimension>(box, min_value);
82 set<max_corner, Dimension>(box, max_value);
87 Box, Dimension + 1, DimensionCount
94 template <typename Box, std::size_t DimensionCount>
95 struct correct_box_loop<Box, DimensionCount, DimensionCount>
97 static inline void apply(Box& )
103 // Correct a box: make min/max correct
104 template <typename Box>
108 static inline void apply(Box& box)
110 // Currently only for Cartesian coordinates
111 // (or spherical without crossing dateline)
112 // Future version: adapt using strategies
115 Box, 0, dimension<Box>::type::value
121 // Close a ring, if not closed
122 template <typename Ring, typename Predicate>
125 typedef typename point_type<Ring>::type point_type;
126 typedef typename coordinate_type<Ring>::type coordinate_type;
128 typedef typename strategy::area::services::default_strategy
130 typename cs_tag<point_type>::type,
132 >::type strategy_type;
134 typedef detail::area::ring_area
136 order_as_direction<geometry::point_order<Ring>::value>::value,
137 geometry::closure<Ring>::value
141 static inline void apply(Ring& r)
144 if (boost::size(r) > 2)
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;
150 if (disjoint && (s == closed))
152 geometry::append(r, *boost::begin(r));
154 if (! disjoint && s != closed)
156 // Open it by removing last point
157 geometry::traits::resize<Ring>::apply(r, boost::size(r) - 1);
162 typedef typename default_area_result<Ring>::type area_result_type;
163 area_result_type const zero = area_result_type();
164 if (predicate(ring_area_type::apply(r, strategy_type()), zero))
166 std::reverse(boost::begin(r), boost::end(r));
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
176 typedef typename ring_type<Polygon>::type ring_type;
177 typedef typename default_area_result<Polygon>::type area_result_type;
179 static inline void apply(Polygon& poly)
184 std::less<area_result_type>
185 >::apply(exterior_ring(poly));
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)
195 std::greater<area_result_type>
202 }} // namespace detail::correct
203 #endif // DOXYGEN_NO_DETAIL
206 #ifndef DOXYGEN_NO_DISPATCH
210 template <typename Geometry, typename Tag = typename tag<Geometry>::type>
211 struct correct: not_implemented<Tag>
214 template <typename Point>
215 struct correct<Point, point_tag>
216 : detail::correct::correct_nop<Point>
219 template <typename LineString>
220 struct correct<LineString, linestring_tag>
221 : detail::correct::correct_nop<LineString>
224 template <typename Segment>
225 struct correct<Segment, segment_tag>
226 : detail::correct::correct_nop<Segment>
230 template <typename Box>
231 struct correct<Box, box_tag>
232 : detail::correct::correct_box<Box>
235 template <typename Ring>
236 struct correct<Ring, ring_tag>
237 : detail::correct::correct_ring
240 std::less<typename default_area_result<Ring>::type>
244 template <typename Polygon>
245 struct correct<Polygon, polygon_tag>
246 : detail::correct::correct_polygon<Polygon>
250 template <typename MultiPoint>
251 struct correct<MultiPoint, multi_point_tag>
252 : detail::correct::correct_nop<MultiPoint>
256 template <typename MultiLineString>
257 struct correct<MultiLineString, multi_linestring_tag>
258 : detail::correct::correct_nop<MultiLineString>
262 template <typename Geometry>
263 struct correct<Geometry, multi_polygon_tag>
264 : detail::multi_modify
267 detail::correct::correct_polygon
269 typename boost::range_value<Geometry>::type
275 } // namespace dispatch
276 #endif // DOXYGEN_NO_DISPATCH
279 namespace resolve_variant {
281 template <typename Geometry>
284 static inline void apply(Geometry& geometry)
286 concepts::check<Geometry const>();
287 dispatch::correct<Geometry>::apply(geometry);
291 template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
292 struct correct<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
294 struct visitor: boost::static_visitor<void>
296 template <typename Geometry>
297 void operator()(Geometry& geometry) const
299 correct<Geometry>::apply(geometry);
304 apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)>& geometry)
306 boost::apply_visitor(visitor(), geometry);
310 } // namespace resolve_variant
314 \brief Corrects a geometry
315 \details Corrects a geometry: all rings which are wrongly oriented with respect
316 to their expected orientation are reversed. To all rings which do not have a
317 closing point and are typed as they should have one, the first point is
318 appended. Also boxes can be corrected.
320 \tparam Geometry \tparam_geometry
321 \param geometry \param_geometry which will be corrected if necessary
323 \qbk{[include reference/algorithms/correct.qbk]}
325 template <typename Geometry>
326 inline void correct(Geometry& geometry)
328 resolve_variant::correct<Geometry>::apply(geometry);
331 #if defined(_MSC_VER)
335 }} // namespace boost::geometry
338 #endif // BOOST_GEOMETRY_ALGORITHMS_CORRECT_HPP