diff options
Diffstat (limited to 'boost/geometry/algorithms/detail/is_valid/ring.hpp')
| -rw-r--r-- | boost/geometry/algorithms/detail/is_valid/ring.hpp | 173 |
1 files changed, 173 insertions, 0 deletions
diff --git a/boost/geometry/algorithms/detail/is_valid/ring.hpp b/boost/geometry/algorithms/detail/is_valid/ring.hpp new file mode 100644 index 0000000000..c88df79b05 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/ring.hpp @@ -0,0 +1,173 @@ +// Boost.Geometry (aka GGL, Generic Geometry Library) + +// Copyright (c) 2014, Oracle and/or its affiliates. + +// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle + +// Licensed under the Boost Software License version 1.0. +// http://www.boost.org/users/license.html + +#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP + +#include <boost/geometry/core/closure.hpp> +#include <boost/geometry/core/cs.hpp> +#include <boost/geometry/core/point_order.hpp> + +#include <boost/geometry/util/order_as_direction.hpp> +#include <boost/geometry/util/range.hpp> + +#include <boost/geometry/algorithms/equals.hpp> + +#include <boost/geometry/views/reversible_view.hpp> +#include <boost/geometry/views/closeable_view.hpp> + +#include <boost/geometry/algorithms/area.hpp> +#include <boost/geometry/algorithms/intersects.hpp> +#include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp> +#include <boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp> + +#include <boost/geometry/strategies/area.hpp> + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + + +// struct to check whether a ring is topologically closed +template <typename Ring, closure_selector Closure /* open */> +struct is_topologically_closed +{ + static inline bool apply(Ring const&) + { + return true; + } +}; + +template <typename Ring> +struct is_topologically_closed<Ring, closed> +{ + static inline bool apply(Ring const& ring) + { + return geometry::equals(range::front(ring), range::back(ring)); + } +}; + + + +template <typename ResultType, bool IsInteriorRing /* false */> +struct ring_area_predicate +{ + typedef std::greater<ResultType> type; +}; + +template <typename ResultType> +struct ring_area_predicate<ResultType, true> +{ + typedef std::less<ResultType> type; +}; + + + +template <typename Ring, bool IsInteriorRing> +struct is_properly_oriented +{ + typedef typename point_type<Ring>::type point_type; + + typedef typename strategy::area::services::default_strategy + < + typename cs_tag<point_type>::type, + point_type + >::type strategy_type; + + typedef detail::area::ring_area + < + order_as_direction<geometry::point_order<Ring>::value>::value, + geometry::closure<Ring>::value + > ring_area_type; + + typedef typename default_area_result<Ring>::type area_result_type; + + static inline bool apply(Ring const& ring) + { + typename ring_area_predicate + < + area_result_type, IsInteriorRing + >::type predicate; + + // Check area + area_result_type const zero = area_result_type(); + return predicate(ring_area_type::apply(ring, strategy_type()), zero); + } +}; + + + +template +< + typename Ring, + bool AllowDuplicates, + bool CheckSelfIntersections = true, + bool IsInteriorRing = false +> +struct is_valid_ring +{ + static inline bool apply(Ring const& ring) + { + // return invalid if any of the following condition holds: + // (a) the ring's size is below the minimal one + // (b) the ring is not topologically closed + // (c) the ring has spikes + // (d) the ring has duplicate points (if AllowDuplicates is false) + // (e) the boundary of the ring has self-intersections + // (f) the order of the points is inconsistent with the defined order + // + // Note: no need to check if the area is zero. If this is the + // case, then the ring must have at least two spikes, which is + // checked by condition (c). + + closure_selector const closure = geometry::closure<Ring>::value; + + return + ( boost::size(ring) + >= core_detail::closure::minimum_ring_size<closure>::value ) + && is_topologically_closed<Ring, closure>::apply(ring) + && (AllowDuplicates || !has_duplicates<Ring, closure>::apply(ring)) + && !has_spikes<Ring, closure>::apply(ring) + && !(CheckSelfIntersections && geometry::intersects(ring)) + && is_properly_oriented<Ring, IsInteriorRing>::apply(ring); + } +}; + + +}} // namespace dispatch +#endif // DOXYGEN_NO_DETAIL + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + +// A Ring is a Polygon with exterior boundary only. +// The Ring's boundary must be a LinearRing (see OGC 06-103-r4, +// 6.1.7.1, for the definition of LinearRing) +// +// Reference (for polygon validity): OGC 06-103r4 (6.1.11.1) +template <typename Ring, bool AllowSpikes, bool AllowDuplicates> +struct is_valid<Ring, ring_tag, AllowSpikes, AllowDuplicates> + : detail::is_valid::is_valid_ring<Ring, AllowDuplicates> +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP |