From 08c1e93fa36a49f49325a07fe91ff92c964c2b6c Mon Sep 17 00:00:00 2001 From: Chanho Park Date: Thu, 11 Dec 2014 18:55:56 +0900 Subject: Imported Upstream version 1.57.0 --- boost/geometry/algorithms/detail/is_valid/box.hpp | 86 +++++ .../detail/is_valid/complement_graph.hpp | 239 +++++++++++++ .../detail/is_valid/debug_complement_graph.hpp | 70 ++++ .../detail/is_valid/debug_print_turns.hpp | 64 ++++ .../detail/is_valid/debug_validity_phase.hpp | 68 ++++ .../algorithms/detail/is_valid/has_duplicates.hpp | 70 ++++ .../algorithms/detail/is_valid/has_spikes.hpp | 139 ++++++++ .../detail/is_valid/has_valid_self_turns.hpp | 93 +++++ .../algorithms/detail/is_valid/implementation.hpp | 21 ++ .../algorithms/detail/is_valid/interface.hpp | 78 +++++ .../detail/is_valid/is_acceptable_turn.hpp | 144 ++++++++ .../geometry/algorithms/detail/is_valid/linear.hpp | 125 +++++++ .../algorithms/detail/is_valid/multipolygon.hpp | 297 ++++++++++++++++ .../algorithms/detail/is_valid/pointlike.hpp | 62 ++++ .../algorithms/detail/is_valid/polygon.hpp | 376 +++++++++++++++++++++ boost/geometry/algorithms/detail/is_valid/ring.hpp | 173 ++++++++++ .../algorithms/detail/is_valid/segment.hpp | 61 ++++ 17 files changed, 2166 insertions(+) create mode 100644 boost/geometry/algorithms/detail/is_valid/box.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/complement_graph.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/has_spikes.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/implementation.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/interface.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/linear.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/multipolygon.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/pointlike.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/polygon.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/ring.hpp create mode 100644 boost/geometry/algorithms/detail/is_valid/segment.hpp (limited to 'boost/geometry/algorithms/detail/is_valid') diff --git a/boost/geometry/algorithms/detail/is_valid/box.hpp b/boost/geometry/algorithms/detail/is_valid/box.hpp new file mode 100644 index 0000000000..f82b3f9bf1 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/box.hpp @@ -0,0 +1,86 @@ +// 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_BOX_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_BOX_HPP + +#include + +#include +#include +#include + +#include + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + +template +struct has_valid_corners +{ + static inline bool apply(Box const& box) + { + if ( geometry::get(box) + <= + geometry::get(box) ) + { + return false; + } + return has_valid_corners::apply(box); + } +}; + + +template +struct has_valid_corners +{ + static inline bool apply(Box const&) + { + return true; + } +}; + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +// A box is always simple +// A box is a Polygon, and it satisfies the conditions for Polygon validity. +// +// The only thing we have to check is whether the max corner lies in +// the upper-right quadrant as defined by the min corner +// +// Reference (for polygon validity): OGC 06-103r4 (6.1.11.1) +template +struct is_valid + : detail::is_valid::has_valid_corners::value> +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_BOX_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/complement_graph.hpp b/boost/geometry/algorithms/detail/is_valid/complement_graph.hpp new file mode 100644 index 0000000000..c59139a92e --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/complement_graph.hpp @@ -0,0 +1,239 @@ +// 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_COMPLEMENT_GRAPH_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP + +#include + +#include +#include +#include +#include + +#include +#include + +#include + + +namespace boost { namespace geometry +{ + +namespace detail { namespace is_valid +{ + + +template +class complement_graph_vertex +{ +public: + complement_graph_vertex(std::size_t id) + : m_id(id) + , m_turn_point(NULL) + {} + + complement_graph_vertex(TurnPoint const* turn_point, + std::size_t expected_id) + : m_id(expected_id) + , m_turn_point(turn_point) + {} + + inline std::size_t id() const { return m_id; } + + inline bool operator<(complement_graph_vertex const& other) const + { + if ( m_turn_point != NULL && other.m_turn_point != NULL ) + { + return geometry::less + < + TurnPoint + >()(*m_turn_point, *other.m_turn_point); + } + if ( m_turn_point == NULL && other.m_turn_point == NULL ) + { + return m_id < other.m_id; + } + return m_turn_point == NULL; + } + +private: + // the value of m_turn_point determines the type of the vertex + // non-NULL: vertex corresponds to an IP + // NULL : vertex corresponds to a hole or outer space, and the id + // is the ring id of the corresponding ring of the polygon + std::size_t m_id; + TurnPoint const* m_turn_point; +}; + + + + +template +class complement_graph +{ +private: + typedef complement_graph_vertex vertex; + typedef std::set vertex_container; + +public: + typedef typename vertex_container::const_iterator vertex_handle; + +private: + struct vertex_handle_less + { + inline bool operator()(vertex_handle v1, vertex_handle v2) const + { + return v1->id() < v2->id(); + } + }; + + typedef std::set neighbor_container; + + class has_cycles_dfs_data + { + public: + has_cycles_dfs_data(std::size_t num_nodes) + : m_visited(num_nodes, false) + , m_parent_id(num_nodes, -1) + {} + + inline signed_index_type parent_id(vertex_handle v) const + { + return m_parent_id[v->id()]; + } + + inline void set_parent_id(vertex_handle v, signed_index_type id) + { + m_parent_id[v->id()] = id; + } + + inline bool visited(vertex_handle v) const + { + return m_visited[v->id()]; + } + + inline void set_visited(vertex_handle v, bool value) + { + m_visited[v->id()] = value; + } + private: + std::vector m_visited; + std::vector m_parent_id; + }; + + + inline bool has_cycles(vertex_handle start_vertex, + has_cycles_dfs_data& data) const + { + std::stack stack; + stack.push(start_vertex); + + while ( !stack.empty() ) + { + vertex_handle v = stack.top(); + stack.pop(); + + data.set_visited(v, true); + for (typename neighbor_container::const_iterator nit + = m_neighbors[v->id()].begin(); + nit != m_neighbors[v->id()].end(); ++nit) + { + if ( static_cast((*nit)->id()) != data.parent_id(v) ) + { + if ( data.visited(*nit) ) + { + return true; + } + else + { + data.set_parent_id(*nit, static_cast(v->id())); + stack.push(*nit); + } + } + } + } + return false; + } + +public: + // num_rings: total number of rings, including the exterior ring + complement_graph(std::size_t num_rings) + : m_num_rings(num_rings) + , m_num_turns(0) + , m_vertices() + , m_neighbors(num_rings) + {} + + // inserts a ring vertex in the graph and returns its handle + // ring id's are zero-based (so the first interior ring has id 1) + inline vertex_handle add_vertex(signed_index_type id) + { + return m_vertices.insert(vertex(static_cast(id))).first; + } + + // inserts an IP in the graph and returns its id + inline vertex_handle add_vertex(TurnPoint const& turn_point) + { + std::pair res + = m_vertices.insert(vertex(boost::addressof(turn_point), + m_num_rings + m_num_turns) + ); + + if ( res.second ) + { + // a new element is inserted + m_neighbors.push_back(neighbor_container()); + ++m_num_turns; + } + return res.first; + } + + inline void add_edge(vertex_handle v1, vertex_handle v2) + { + BOOST_ASSERT( v1 != m_vertices.end() ); + BOOST_ASSERT( v2 != m_vertices.end() ); + m_neighbors[v1->id()].insert(v2); + m_neighbors[v2->id()].insert(v1); + } + + inline bool has_cycles() const + { + // initialize all vertices as non-visited and with no parent set + // this is done by the constructor of has_cycles_dfs_data + has_cycles_dfs_data data(m_num_rings + m_num_turns); + + // for each non-visited vertex, start a DFS from that vertex + for (vertex_handle it = m_vertices.begin(); + it != m_vertices.end(); ++it) + { + if ( !data.visited(it) && has_cycles(it, data) ) + { + return true; + } + } + return false; + } + + template + friend inline + void debug_print_complement_graph(OStream&, complement_graph const&); + +private: + std::size_t m_num_rings, m_num_turns; + vertex_container m_vertices; + std::vector m_neighbors; +}; + + +}} // namespace detail::is_valid + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp b/boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp new file mode 100644 index 0000000000..60f597e296 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp @@ -0,0 +1,70 @@ +// 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_DEBUG_COMPLEMENT_GRAPH_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_DEBUG_COMPLEMENT_GRAPH_HPP + +#ifdef BOOST_GEOMETRY_TEST_DEBUG +#include +#endif + +namespace boost { namespace geometry +{ + +namespace detail { namespace is_valid +{ + + +#ifdef BOOST_GEOMETRY_TEST_DEBUG +template +inline void +debug_print_complement_graph(OutputStream& os, + complement_graph const& graph) +{ + typedef typename complement_graph::vertex_handle vertex_handle; + + os << "num rings: " << graph.m_num_rings << std::endl; + os << "vertex ids: {"; + for (vertex_handle it = graph.m_vertices.begin(); + it != graph.m_vertices.end(); ++it) + { + os << " " << it->id(); + } + os << " }" << std::endl; + + for (vertex_handle it = graph.m_vertices.begin(); + it != graph.m_vertices.end(); ++it) + { + os << "neighbors of " << it->id() << ": {"; + for (typename complement_graph + < + TurnPoint + >::neighbor_container::const_iterator + nit = graph.m_neighbors[it->id()].begin(); + nit != graph.m_neighbors[it->id()].end(); ++nit) + { + os << " " << (*nit)->id(); + } + os << "}" << std::endl; + } +} +#else +template +inline void debug_print_complement_graph(OutputStream&, + complement_graph const&) +{ +} +#endif + + +}} // namespace detail::is_valid + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp b/boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp new file mode 100644 index 0000000000..6824921b63 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp @@ -0,0 +1,64 @@ +// 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_DEBUG_PRINT_TURNS_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_DEBUG_PRINT_TURNS_HPP + +#ifdef BOOST_GEOMETRY_TEST_DEBUG +#include + +#include +#include +#endif + + +namespace boost { namespace geometry +{ + +namespace detail { namespace is_valid +{ + +#ifdef BOOST_GEOMETRY_TEST_DEBUG +template +inline void debug_print_turns(TurnIterator first, TurnIterator beyond) +{ + std::cout << "turns:"; + for (TurnIterator tit = first; tit != beyond; ++tit) + { + std::cout << " [" + << geometry::method_char(tit->method) + << "," + << geometry::operation_char(tit->operations[0].operation) + << "/" + << geometry::operation_char(tit->operations[1].operation) + << " {" + << tit->operations[0].seg_id.multi_index + << ", " + << tit->operations[1].seg_id.multi_index + << "} {" + << tit->operations[0].seg_id.ring_index + << ", " + << tit->operations[1].seg_id.ring_index + << "} " + << geometry::dsv(tit->point) + << "]"; + } + std::cout << std::endl << std::endl; +} +#else +template +inline void debug_print_turns(TurnIterator, TurnIterator) +{} +#endif // BOOST_GEOMETRY_TEST_DEBUG + +}} // namespace detail::is_valid + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_DEBUG_PRINT_TURNS_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp b/boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp new file mode 100644 index 0000000000..6f1c263646 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp @@ -0,0 +1,68 @@ +// 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_DEBUG_VALIDITY_PHASE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_DEBUG_VALIDITY_PHASE_HPP + +#ifdef GEOMETRY_TEST_DEBUG +#include + +#include +#include +#endif + + +namespace boost { namespace geometry +{ + +namespace detail { namespace is_valid +{ + +template ::type> +struct debug_validity_phase +{ + static inline void apply(int) + { + } +}; + +#ifdef BOOST_GEOMETRY_TEST_DEBUG +template +struct debug_validity_phase +{ + static inline void apply(int phase) + { + switch (phase) + { + case 1: + std::cout << "checking exterior ring..." << std::endl; + break; + case 2: + std::cout << "checking interior rings..." << std::endl; + break; + case 3: + std::cout << "computing and analyzing turns..." << std::endl; + break; + case 4: + std::cout << "checking if holes are inside the exterior ring..." + << std::endl; + break; + case 5: + std::cout << "checking connectivity of interior..." << std::endl; + break; + } + } +}; +#endif + +}} // namespace detail::is_valid + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_DEBUG_VALIDITY_PHASE_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp b/boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp new file mode 100644 index 0000000000..dd0922bb2b --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp @@ -0,0 +1,70 @@ +// 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_HAS_DUPLICATES_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_DUPLICATES_HPP + +#include + +#include + +#include + +#include + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + +template +struct has_duplicates +{ + static inline bool apply(Range const& range) + { + typedef typename closeable_view::type view_type; + typedef typename boost::range_iterator::type iterator; + + view_type view(range); + + if ( boost::size(view) < 2 ) + { + return false; + } + + geometry::equal_to::type> equal; + + iterator it = boost::begin(view); + iterator next = ++boost::begin(view); + for (; next != boost::end(view); ++it, ++next) + { + if ( equal(*it, *next) ) + { + return true; + } + } + return false; + } +}; + + + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_DUPLICATES_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/has_spikes.hpp b/boost/geometry/algorithms/detail/is_valid/has_spikes.hpp new file mode 100644 index 0000000000..9b95017482 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/has_spikes.hpp @@ -0,0 +1,139 @@ +// 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_HAS_SPIKES_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_SPIKES_HPP + +#include + +#include + +#include + +#include + +#include + +#include +#include + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + +template +struct equal_to +{ + Point const& m_point; + + equal_to(Point const& point) + : m_point(point) + {} + + template + inline bool operator()(OtherPoint const& other) const + { + return geometry::equals(m_point, other); + } +}; + +template +struct not_equal_to +{ + Point const& m_point; + + not_equal_to(Point const& point) + : m_point(point) + {} + + template + inline bool operator()(OtherPoint const& other) const + { + return !geometry::equals(other, m_point); + } +}; + + + +template +struct has_spikes +{ + static inline bool apply(Range const& range) + { + typedef not_equal_to::type> not_equal; + + typedef typename closeable_view::type view_type; + typedef typename boost::range_iterator::type iterator; + + view_type const view(range); + + iterator prev = boost::begin(view); + + iterator cur = std::find_if(prev, boost::end(view), not_equal(*prev)); + if ( cur == boost::end(view) ) + { + // the range has only one distinct point, so it + // cannot have a spike + return false; + } + + iterator next = std::find_if(cur, boost::end(view), not_equal(*cur)); + if ( next == boost::end(view) ) + { + // the range has only two distinct points, so it + // cannot have a spike + return false; + } + + while ( next != boost::end(view) ) + { + if ( geometry::detail::point_is_spike_or_equal(*prev, + *next, + *cur) ) + { + return true; + } + prev = cur; + cur = next; + next = std::find_if(cur, boost::end(view), not_equal(*cur)); + } + + if ( geometry::equals(range::front(view), range::back(view)) ) + { + iterator cur = boost::begin(view); + typename boost::range_reverse_iterator + < + view_type const + >::type prev = std::find_if(boost::rbegin(view), + boost::rend(view), + not_equal(range::back(view))); + iterator next = + std::find_if(cur, boost::end(view), not_equal(*cur)); + return detail::point_is_spike_or_equal(*prev, *next, *cur); + } + + return false; + } +}; + + + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_SPIKES_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp b/boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp new file mode 100644 index 0000000000..220a67bcd1 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp @@ -0,0 +1,93 @@ +// 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_HAS_VALID_SELF_TURNS_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_VALID_SELF_TURNS_HPP + +#include + +#include +#include +#include + +#include +#include +#include + +#include + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + + +template +< + typename Geometry, + typename IsAcceptableTurn = is_acceptable_turn +> +class has_valid_self_turns +{ +private: + typedef typename point_type::type point_type; + + typedef typename geometry::rescale_policy_type + < + point_type + >::type rescale_policy_type; + + typedef detail::overlay::get_turn_info + < + detail::overlay::assign_null_policy + > turn_policy; + +public: + typedef detail::overlay::turn_info + < + point_type, + typename geometry::segment_ratio_type + < + point_type, + rescale_policy_type + >::type + > turn_type; + + // returns true if all turns are valid + template + static inline bool apply(Geometry const& geometry, Turns& turns) + { + rescale_policy_type robust_policy + = geometry::get_rescale_policy(geometry); + + detail::overlay::stateless_predicate_based_interrupt_policy + < + IsAcceptableTurn + > interrupt_policy; + + geometry::self_turns(geometry, + robust_policy, + turns, + interrupt_policy); + + return !interrupt_policy.has_intersections; + } +}; + + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_HAS_VALID_SELF_TURNS_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/implementation.hpp b/boost/geometry/algorithms/detail/is_valid/implementation.hpp new file mode 100644 index 0000000000..4a515a3073 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/implementation.hpp @@ -0,0 +1,21 @@ +// 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_IMPLEMENTATION_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_IMPLEMENTATION_HPP + +#include +#include +#include +#include +#include +#include +#include + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_IMPLEMENTATION_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/interface.hpp b/boost/geometry/algorithms/detail/is_valid/interface.hpp new file mode 100644 index 0000000000..4b232fd436 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/interface.hpp @@ -0,0 +1,78 @@ +// 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_INTERFACE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_INTERFACE_HPP + +#include +#include +#include + +#include + +#include + + +namespace boost { namespace geometry +{ + + +namespace resolve_variant { + +template +struct is_valid +{ + static inline bool apply(Geometry const& geometry) + { + concept::check(); + return dispatch::is_valid::apply(geometry); + } +}; + +template +struct is_valid > +{ + struct visitor : boost::static_visitor + { + template + bool operator()(Geometry const& geometry) const + { + return is_valid::apply(geometry); + } + }; + + static inline bool + apply(boost::variant const& geometry) + { + return boost::apply_visitor(visitor(), geometry); + } +}; + +} // namespace resolve_variant + + +/*! +\brief \brief_check{is valid (in the OGC sense)} +\ingroup is_valid +\tparam Geometry \tparam_geometry +\param geometry \param_geometry +\return \return_check{is valid (in the OGC sense)} + +\qbk{[include reference/algorithms/is_valid.qbk]} +*/ +template +inline bool is_valid(Geometry const& geometry) +{ + return resolve_variant::is_valid::apply(geometry); +} + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_INTERFACE_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp b/boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp new file mode 100644 index 0000000000..f9d926770e --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp @@ -0,0 +1,144 @@ +// 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_IS_ACCEPTABLE_TURN_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_IS_ACCEPTABLE_TURN_HPP + +#include + +#include +#include +#include + +#include + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + + +template +< + typename Geometry, + order_selector Order = geometry::point_order::value, + typename Tag = typename tag::type +> +struct acceptable_operation +{}; + +template +struct acceptable_operation +{ + static const detail::overlay::operation_type value = + detail::overlay::operation_union; +}; + +template +struct acceptable_operation +{ + static const detail::overlay::operation_type value = + detail::overlay::operation_intersection; +}; + +template +struct acceptable_operation +{ + static const detail::overlay::operation_type value = + detail::overlay::operation_intersection; +}; + +template +struct acceptable_operation +{ + static const detail::overlay::operation_type value = + detail::overlay::operation_union; +}; + + + + +template ::type> +struct is_acceptable_turn +{}; + +template +class is_acceptable_turn +{ +protected: + template + static inline bool check_turn(Turn const& turn, + Method method, + Operation operation) + { + return turn.method == method + && turn.operations[0].operation == operation + && turn.operations[1].operation == operation; + } + + +public: + template + static inline bool apply(Turn const& turn) + { + using namespace detail::overlay; + + if ( turn.operations[0].seg_id.ring_index + == turn.operations[1].seg_id.ring_index ) + { + return false; + } + + operation_type const op = acceptable_operation::value; + + return check_turn(turn, method_touch_interior, op) + || check_turn(turn, method_touch, op) + ; + } +}; + +template +class is_acceptable_turn + : is_acceptable_turn::type> +{ +private: + typedef typename boost::range_value::type polygon; + typedef is_acceptable_turn base; + +public: + template + static inline bool apply(Turn const& turn) + { + using namespace detail::overlay; + + if ( turn.operations[0].seg_id.multi_index + == turn.operations[1].seg_id.multi_index ) + { + return base::apply(turn); + } + + operation_type const op = acceptable_operation::value; + + return base::check_turn(turn, method_touch_interior, op) + || base::check_turn(turn, method_touch, op) + ; + } +}; + + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_IS_ACCEPTABLE_TURN_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/linear.hpp b/boost/geometry/algorithms/detail/is_valid/linear.hpp new file mode 100644 index 0000000000..244df9b035 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/linear.hpp @@ -0,0 +1,125 @@ +// 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_LINEAR_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP + +#include + +#include + +#include +#include +#include + +#include + +#include +#include +#include +#include + +#include + + +namespace boost { namespace geometry +{ + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + + +template +struct is_valid_linestring +{ + static inline bool apply(Linestring const& linestring) + { + std::size_t num_distinct = detail::num_distinct_consecutive_points + < + Linestring, + 3u, + true, + not_equal_to::type> + >::apply(linestring); + + if ( num_distinct < 2u ) + { + return false; + } + + return num_distinct == 2u + || AllowSpikes + || !has_spikes::apply(linestring); + } +}; + + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +// A linestring is a curve. +// A curve is 1-dimensional so it has to have at least two distinct +// points. +// A curve is simple if it does not pass through the same point twice, +// with the possible exception of its two endpoints +// +// There is an option here as to whether spikes are allowed for linestrings; +// here we pass this as an additional template parameter: allow_spikes +// If allow_spikes is set to true, spikes are allowed, false otherwise. +// By default, spikes are disallowed +// +// Reference: OGC 06-103r4 (6.1.6.1) +template +struct is_valid + : detail::is_valid::is_valid_linestring +{}; + + +// A MultiLinestring is a MultiCurve +// A MultiCurve is simple if all of its elements are simple and the +// only intersections between any two elements occur at Points that +// are on the boundaries of both elements. +// +// Reference: OGC 06-103r4 (6.1.8.1; Fig. 9) +template +struct is_valid +{ + static inline bool apply(MultiLinestring const& multilinestring) + { + return detail::check_iterator_range + < + detail::is_valid::is_valid_linestring + < + typename boost::range_value::type, + AllowSpikes + >, + false // do not allow empty multilinestring + >::apply(boost::begin(multilinestring), + boost::end(multilinestring)); + } +}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_LINEAR_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/multipolygon.hpp b/boost/geometry/algorithms/detail/is_valid/multipolygon.hpp new file mode 100644 index 0000000000..3d0ebb5f82 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/multipolygon.hpp @@ -0,0 +1,297 @@ +// 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_MULTIPOLYGON_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP + +#include +#include + +#include +#include + +#include +#include +#include +#include + +#include + +#include + +#include + +#include +#include + +#include +#include +#include + +#include +#include + +#include + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + + +template +class is_valid_multipolygon + : is_valid_polygon + < + typename boost::range_value::type, + AllowDuplicates, + true // check only the validity of rings + > +{ +private: + typedef is_valid_polygon + < + typename boost::range_value::type, + AllowDuplicates, + true + > base; + + + + template + static inline + bool are_polygon_interiors_disjoint(PolygonIterator polygons_first, + PolygonIterator polygons_beyond, + TurnIterator turns_first, + TurnIterator turns_beyond) + { + // collect all polygons that have turns + std::set multi_indices; + for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) + { + multi_indices.insert(tit->operations[0].seg_id.multi_index); + multi_indices.insert(tit->operations[1].seg_id.multi_index); + } + + // put polygon iterators without turns in a vector + std::vector polygon_iterators; + signed_index_type multi_index = 0; + for (PolygonIterator it = polygons_first; it != polygons_beyond; + ++it, ++multi_index) + { + if ( multi_indices.find(multi_index) == multi_indices.end() ) + { + polygon_iterators.push_back(it); + } + } + + typename base::item_visitor visitor; + + geometry::partition + < + geometry::model::box::type>, + typename base::expand_box, + typename base::overlaps_box + >::apply(polygon_iterators, visitor); + + return !visitor.items_overlap; + } + + + + class has_multi_index + { + public: + has_multi_index(signed_index_type multi_index) + : m_multi_index(multi_index) + {} + + template + inline bool operator()(Turn const& turn) const + { + return turn.operations[0].seg_id.multi_index == m_multi_index + && turn.operations[1].seg_id.multi_index == m_multi_index; + } + + private: + signed_index_type const m_multi_index; + }; + + + + template + struct has_property_per_polygon + { + template + static inline bool apply(PolygonIterator polygons_first, + PolygonIterator polygons_beyond, + TurnIterator turns_first, + TurnIterator turns_beyond) + { + signed_index_type multi_index = 0; + for (PolygonIterator it = polygons_first; it != polygons_beyond; + ++it, ++multi_index) + { + has_multi_index index_predicate(multi_index); + + typedef boost::filter_iterator + < + has_multi_index, TurnIterator + > filtered_turn_iterator; + + filtered_turn_iterator filtered_turns_first(index_predicate, + turns_first, + turns_beyond); + + filtered_turn_iterator filtered_turns_beyond(index_predicate, + turns_beyond, + turns_beyond); + + if ( !Predicate::apply(*it, + filtered_turns_first, + filtered_turns_beyond) ) + { + return false; + } + } + return true; + } + }; + + + + template + static inline bool have_holes_inside(PolygonIterator polygons_first, + PolygonIterator polygons_beyond, + TurnIterator turns_first, + TurnIterator turns_beyond) + { + return has_property_per_polygon + < + typename base::has_holes_inside + >::apply(polygons_first, polygons_beyond, + turns_first, turns_beyond); + } + + + + template + static inline bool have_connected_interior(PolygonIterator polygons_first, + PolygonIterator polygons_beyond, + TurnIterator turns_first, + TurnIterator turns_beyond) + { + return has_property_per_polygon + < + typename base::has_connected_interior + >::apply(polygons_first, polygons_beyond, + turns_first, turns_beyond); + } + + +public: + static inline bool apply(MultiPolygon const& multipolygon) + { + typedef debug_validity_phase debug_phase; + + // check validity of all polygons ring + debug_phase::apply(1); + + if ( !detail::check_iterator_range + < + base, + false // do not allow empty multi-polygons + >::apply(boost::begin(multipolygon), + boost::end(multipolygon)) ) + { + return false; + } + + + // compute turns and check if all are acceptable + debug_phase::apply(2); + + typedef has_valid_self_turns has_valid_turns; + + std::deque turns; + bool has_invalid_turns = !has_valid_turns::apply(multipolygon, turns); + debug_print_turns(turns.begin(), turns.end()); + + if ( has_invalid_turns ) + { + return false; + } + + + // check if each polygon's interior rings are inside the + // exterior and not one inside the other + debug_phase::apply(3); + + if ( !have_holes_inside(boost::begin(multipolygon), + boost::end(multipolygon), + turns.begin(), + turns.end()) ) + { + return false; + } + + + // check that each polygon's interior is connected + debug_phase::apply(4); + + if ( !have_connected_interior(boost::begin(multipolygon), + boost::end(multipolygon), + turns.begin(), + turns.end()) ) + { + return false; + } + + + // check if polygon interiors are disjoint + debug_phase::apply(5); + return are_polygon_interiors_disjoint(boost::begin(multipolygon), + boost::end(multipolygon), + turns.begin(), + turns.end()); + } +}; + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +// Not clear what the definition is. +// Right now we check that each element is simple (in fact valid), and +// that the MultiPolygon is also valid. +// +// Reference (for validity of MultiPolygons): OGC 06-103r4 (6.1.14) +template +struct is_valid + : detail::is_valid::is_valid_multipolygon +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_MULTIPOLYGON_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/pointlike.hpp b/boost/geometry/algorithms/detail/is_valid/pointlike.hpp new file mode 100644 index 0000000000..8a4818ef15 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/pointlike.hpp @@ -0,0 +1,62 @@ +// 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_POINTLIKE_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POINTLIKE_HPP + +#include + +#include + +#include + + +namespace boost { namespace geometry +{ + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + +// A point is always simple +template +struct is_valid +{ + static inline bool apply(Point const&) + { + return true; + } +}; + + + +// A MultiPoint is simple if no two Points in the MultiPoint are equal +// (have identical coordinate values in X and Y) +// +// Reference: OGC 06-103r4 (6.1.5) +template +struct is_valid +{ + static inline bool apply(MultiPoint const& multipoint) + { + return boost::size(multipoint) > 0; + } +}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POINTLIKE_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/polygon.hpp b/boost/geometry/algorithms/detail/is_valid/polygon.hpp new file mode 100644 index 0000000000..3a91999208 --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/polygon.hpp @@ -0,0 +1,376 @@ +// 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_POLYGON_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP + +#include + +#include +#include +#include +#include +#include + +#include +#include + +#include +#include +#include +#include + +#include + +#include + +#include + +#include +#include +#include +#include +#include + +#include +#include + +#include +#include +#include +#include + +#include +#include +#include + +#include + + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + + +template +< + typename Polygon, + bool AllowDuplicates, + bool CheckRingValidityOnly = false +> +class is_valid_polygon +{ +protected: + typedef debug_validity_phase debug_phase; + + + + template + static bool has_valid_interior_rings(InteriorRings const& interior_rings) + { + return + detail::check_iterator_range + < + detail::is_valid::is_valid_ring + < + typename boost::range_value::type, + AllowDuplicates, + false, // do not check self-intersections + true // indicate that the ring is interior + > + >::apply(boost::begin(interior_rings), + boost::end(interior_rings)); + } + + struct has_valid_rings + { + static inline bool apply(Polygon const& polygon) + { + typedef typename ring_type::type ring_type; + + // check validity of exterior ring + debug_phase::apply(1); + + if ( !detail::is_valid::is_valid_ring + < + ring_type, + AllowDuplicates, + false // do not check self intersections + >::apply(exterior_ring(polygon)) ) + { + return false; + } + + // check validity of interior rings + debug_phase::apply(2); + + return has_valid_interior_rings(geometry::interior_rings(polygon)); + } + }; + + + // structs from partition -- start + struct expand_box + { + template + static inline void apply(Box& total, Iterator const& it) + { + geometry::expand(total, geometry::return_envelope(*it)); + } + + }; + + struct overlaps_box + { + template + static inline bool apply(Box const& box, Iterator const& it) + { + return !geometry::disjoint(*it, box); + } + }; + + + struct item_visitor + { + bool items_overlap; + + item_visitor() : items_overlap(false) {} + + template + inline void apply(Item1 const& item1, Item2 const& item2) + { + if ( !items_overlap + && (geometry::within(*points_begin(*item1), *item2) + || geometry::within(*points_begin(*item2), *item1)) + ) + { + items_overlap = true; + } + } + }; + // structs for partition -- end + + + template + < + typename RingIterator, + typename ExteriorRing, + typename TurnIterator + > + static inline bool are_holes_inside(RingIterator rings_first, + RingIterator rings_beyond, + ExteriorRing const& exterior_ring, + TurnIterator turns_first, + TurnIterator turns_beyond) + { + // collect the interior ring indices that have turns with the + // exterior ring + std::set ring_indices; + for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) + { + if ( tit->operations[0].seg_id.ring_index == -1 ) + { + BOOST_ASSERT( tit->operations[1].seg_id.ring_index != -1 ); + ring_indices.insert(tit->operations[1].seg_id.ring_index); + } + else if ( tit->operations[1].seg_id.ring_index == -1 ) + { + BOOST_ASSERT( tit->operations[0].seg_id.ring_index != -1 ); + ring_indices.insert(tit->operations[0].seg_id.ring_index); + } + } + + signed_index_type ring_index = 0; + for (RingIterator it = rings_first; it != rings_beyond; + ++it, ++ring_index) + { + // do not examine interior rings that have turns with the + // exterior ring + if ( ring_indices.find(ring_index) == ring_indices.end() + && !geometry::covered_by(range::front(*it), exterior_ring) ) + { + return false; + } + } + + // collect all rings (exterior and/or interior) that have turns + for (TurnIterator tit = turns_first; tit != turns_beyond; ++tit) + { + ring_indices.insert(tit->operations[0].seg_id.ring_index); + ring_indices.insert(tit->operations[1].seg_id.ring_index); + } + + // put iterators for interior rings without turns in a vector + std::vector ring_iterators; + ring_index = 0; + for (RingIterator it = rings_first; it != rings_beyond; + ++it, ++ring_index) + { + if ( ring_indices.find(ring_index) == ring_indices.end() ) + { + ring_iterators.push_back(it); + } + } + + // call partition to check is interior rings are disjoint from + // each other + item_visitor visitor; + + geometry::partition + < + geometry::model::box::type>, + expand_box, + overlaps_box + >::apply(ring_iterators, visitor); + + return !visitor.items_overlap; + } + + template + < + typename InteriorRings, + typename ExteriorRing, + typename TurnIterator + > + static inline bool are_holes_inside(InteriorRings const& interior_rings, + ExteriorRing const& exterior_ring, + TurnIterator first, + TurnIterator beyond) + { + return are_holes_inside(boost::begin(interior_rings), + boost::end(interior_rings), + exterior_ring, + first, + beyond); + } + + struct has_holes_inside + { + template + static inline bool apply(Polygon const& polygon, + TurnIterator first, + TurnIterator beyond) + { + return are_holes_inside(geometry::interior_rings(polygon), + geometry::exterior_ring(polygon), + first, + beyond); + } + }; + + + + + struct has_connected_interior + { + template + static inline bool apply(Polygon const& polygon, + TurnIterator first, + TurnIterator beyond) + { + typedef typename std::iterator_traits + < + TurnIterator + >::value_type turn_type; + typedef complement_graph graph; + + graph g(geometry::num_interior_rings(polygon) + 1); + for (TurnIterator tit = first; tit != beyond; ++tit) + { + typename graph::vertex_handle v1 = g.add_vertex + ( tit->operations[0].seg_id.ring_index + 1 ); + typename graph::vertex_handle v2 = g.add_vertex + ( tit->operations[1].seg_id.ring_index + 1 ); + typename graph::vertex_handle vip = g.add_vertex(tit->point); + + g.add_edge(v1, vip); + g.add_edge(v2, vip); + } + + debug_print_complement_graph(std::cout, g); + + return !g.has_cycles(); + } + }; + +public: + static inline bool apply(Polygon const& polygon) + { + if ( !has_valid_rings::apply(polygon) ) + { + return false; + } + + if ( CheckRingValidityOnly ) + { + return true; + } + + // compute turns and check if all are acceptable + debug_phase::apply(3); + + typedef has_valid_self_turns has_valid_turns; + + std::deque turns; + bool has_invalid_turns = !has_valid_turns::apply(polygon, turns); + debug_print_turns(turns.begin(), turns.end()); + + if ( has_invalid_turns ) + { + return false; + } + + // check if all interior rings are inside the exterior ring + debug_phase::apply(4); + + if ( !has_holes_inside::apply(polygon, turns.begin(), turns.end()) ) + { + return false; + } + + // check whether the interior of the polygon is a connected set + debug_phase::apply(5); + + return has_connected_interior::apply(polygon, + turns.begin(), + turns.end()); + } +}; + + +}} // namespace detail::is_valid +#endif // DOXYGEN_NO_DETAIL + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +// A Polygon is always a simple geometric object provided that it is valid. +// +// Reference (for validity of Polygons): OGC 06-103r4 (6.1.11.1) +template +struct is_valid + : detail::is_valid::is_valid_polygon +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_POLYGON_HPP 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 +#include +#include + +#include +#include + +#include + +#include +#include + +#include +#include +#include +#include + +#include + +namespace boost { namespace geometry +{ + + +#ifndef DOXYGEN_NO_DETAIL +namespace detail { namespace is_valid +{ + + +// struct to check whether a ring is topologically closed +template +struct is_topologically_closed +{ + static inline bool apply(Ring const&) + { + return true; + } +}; + +template +struct is_topologically_closed +{ + static inline bool apply(Ring const& ring) + { + return geometry::equals(range::front(ring), range::back(ring)); + } +}; + + + +template +struct ring_area_predicate +{ + typedef std::greater type; +}; + +template +struct ring_area_predicate +{ + typedef std::less type; +}; + + + +template +struct is_properly_oriented +{ + typedef typename point_type::type point_type; + + typedef typename strategy::area::services::default_strategy + < + typename cs_tag::type, + point_type + >::type strategy_type; + + typedef detail::area::ring_area + < + order_as_direction::value>::value, + geometry::closure::value + > ring_area_type; + + typedef typename default_area_result::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::value; + + return + ( boost::size(ring) + >= core_detail::closure::minimum_ring_size::value ) + && is_topologically_closed::apply(ring) + && (AllowDuplicates || !has_duplicates::apply(ring)) + && !has_spikes::apply(ring) + && !(CheckSelfIntersections && geometry::intersects(ring)) + && is_properly_oriented::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 +struct is_valid + : detail::is_valid::is_valid_ring +{}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_RING_HPP diff --git a/boost/geometry/algorithms/detail/is_valid/segment.hpp b/boost/geometry/algorithms/detail/is_valid/segment.hpp new file mode 100644 index 0000000000..486289dabe --- /dev/null +++ b/boost/geometry/algorithms/detail/is_valid/segment.hpp @@ -0,0 +1,61 @@ +// 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_SEGMENT_HPP +#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_SEGMENT_HPP + +#include +#include + +#include +#include + +#include + + +namespace boost { namespace geometry +{ + + + +#ifndef DOXYGEN_NO_DISPATCH +namespace dispatch +{ + + +// A segment is a curve. +// A curve is simple if it does not pass through the same point twice, +// with the possible exception of its two endpoints +// A curve is 1-dimensional, hence we have to check is the two +// endpoints of the segment coincide, since in this case it is +// 0-dimensional. +// +// Reference: OGC 06-103r4 (6.1.6.1) +template +struct is_valid +{ + static inline bool apply(Segment const& segment) + { + typename point_type::type p[2]; + detail::assign_point_from_index<0>(segment, p[0]); + detail::assign_point_from_index<1>(segment, p[1]); + + return !geometry::equals(p[0], p[1]); + } +}; + + +} // namespace dispatch +#endif // DOXYGEN_NO_DISPATCH + + +}} // namespace boost::geometry + + +#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_SEGMENT_HPP -- cgit v1.2.3