summaryrefslogtreecommitdiff
path: root/boost/geometry/algorithms/detail/is_valid
diff options
context:
space:
mode:
authorChanho Park <chanho61.park@samsung.com>2014-12-11 18:55:56 +0900
committerChanho Park <chanho61.park@samsung.com>2014-12-11 18:55:56 +0900
commit08c1e93fa36a49f49325a07fe91ff92c964c2b6c (patch)
tree7a7053ceb8874b28ec4b868d4c49b500008a102e /boost/geometry/algorithms/detail/is_valid
parentbb4dd8289b351fae6b55e303f189127a394a1edd (diff)
downloadboost-08c1e93fa36a49f49325a07fe91ff92c964c2b6c.tar.gz
boost-08c1e93fa36a49f49325a07fe91ff92c964c2b6c.tar.bz2
boost-08c1e93fa36a49f49325a07fe91ff92c964c2b6c.zip
Imported Upstream version 1.57.0upstream/1.57.0
Diffstat (limited to 'boost/geometry/algorithms/detail/is_valid')
-rw-r--r--boost/geometry/algorithms/detail/is_valid/box.hpp86
-rw-r--r--boost/geometry/algorithms/detail/is_valid/complement_graph.hpp239
-rw-r--r--boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp70
-rw-r--r--boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp64
-rw-r--r--boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp68
-rw-r--r--boost/geometry/algorithms/detail/is_valid/has_duplicates.hpp70
-rw-r--r--boost/geometry/algorithms/detail/is_valid/has_spikes.hpp139
-rw-r--r--boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp93
-rw-r--r--boost/geometry/algorithms/detail/is_valid/implementation.hpp21
-rw-r--r--boost/geometry/algorithms/detail/is_valid/interface.hpp78
-rw-r--r--boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp144
-rw-r--r--boost/geometry/algorithms/detail/is_valid/linear.hpp125
-rw-r--r--boost/geometry/algorithms/detail/is_valid/multipolygon.hpp297
-rw-r--r--boost/geometry/algorithms/detail/is_valid/pointlike.hpp62
-rw-r--r--boost/geometry/algorithms/detail/is_valid/polygon.hpp376
-rw-r--r--boost/geometry/algorithms/detail/is_valid/ring.hpp173
-rw-r--r--boost/geometry/algorithms/detail/is_valid/segment.hpp61
17 files changed, 2166 insertions, 0 deletions
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 <cstddef>
+
+#include <boost/geometry/core/access.hpp>
+#include <boost/geometry/core/tags.hpp>
+#include <boost/geometry/core/coordinate_dimension.hpp>
+
+#include <boost/geometry/algorithms/dispatch/is_valid.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace is_valid
+{
+
+template <typename Box, std::size_t I>
+struct has_valid_corners
+{
+ static inline bool apply(Box const& box)
+ {
+ if ( geometry::get<geometry::max_corner, I-1>(box)
+ <=
+ geometry::get<geometry::min_corner, I-1>(box) )
+ {
+ return false;
+ }
+ return has_valid_corners<Box, I-1>::apply(box);
+ }
+};
+
+
+template <typename Box>
+struct has_valid_corners<Box, 0>
+{
+ 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 <typename Box>
+struct is_valid<Box, box_tag>
+ : detail::is_valid::has_valid_corners<Box, dimension<Box>::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 <cstddef>
+
+#include <set>
+#include <stack>
+#include <utility>
+#include <vector>
+
+#include <boost/assert.hpp>
+#include <boost/core/addressof.hpp>
+
+#include <boost/geometry/policies/compare.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+namespace detail { namespace is_valid
+{
+
+
+template <typename TurnPoint>
+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 <typename TurnPoint>
+class complement_graph
+{
+private:
+ typedef complement_graph_vertex<TurnPoint> vertex;
+ typedef std::set<vertex> 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<vertex_handle, vertex_handle_less> 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<bool> m_visited;
+ std::vector<signed_index_type> m_parent_id;
+ };
+
+
+ inline bool has_cycles(vertex_handle start_vertex,
+ has_cycles_dfs_data& data) const
+ {
+ std::stack<vertex_handle> 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<signed_index_type>((*nit)->id()) != data.parent_id(v) )
+ {
+ if ( data.visited(*nit) )
+ {
+ return true;
+ }
+ else
+ {
+ data.set_parent_id(*nit, static_cast<signed_index_type>(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<std::size_t>(id))).first;
+ }
+
+ // inserts an IP in the graph and returns its id
+ inline vertex_handle add_vertex(TurnPoint const& turn_point)
+ {
+ std::pair<vertex_handle, bool> 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 <typename OStream, typename TP>
+ friend inline
+ void debug_print_complement_graph(OStream&, complement_graph<TP> const&);
+
+private:
+ std::size_t m_num_rings, m_num_turns;
+ vertex_container m_vertices;
+ std::vector<neighbor_container> 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 <iostream>
+#endif
+
+namespace boost { namespace geometry
+{
+
+namespace detail { namespace is_valid
+{
+
+
+#ifdef BOOST_GEOMETRY_TEST_DEBUG
+template <typename OutputStream, typename TurnPoint>
+inline void
+debug_print_complement_graph(OutputStream& os,
+ complement_graph<TurnPoint> const& graph)
+{
+ typedef typename complement_graph<TurnPoint>::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 <typename OutputStream, typename TurnPoint>
+inline void debug_print_complement_graph(OutputStream&,
+ complement_graph<TurnPoint> 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 <iostream>
+
+#include <boost/geometry/io/dsv/write.hpp>
+#include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
+#endif
+
+
+namespace boost { namespace geometry
+{
+
+namespace detail { namespace is_valid
+{
+
+#ifdef BOOST_GEOMETRY_TEST_DEBUG
+template <typename TurnIterator>
+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 <typename TurnIterator>
+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 <iostream>
+
+#include <boost/geometry/core/tag.hpp>
+#include <boost/geometry/core/tags.hpp>
+#endif
+
+
+namespace boost { namespace geometry
+{
+
+namespace detail { namespace is_valid
+{
+
+template <typename Geometry, typename Tag = typename tag<Geometry>::type>
+struct debug_validity_phase
+{
+ static inline void apply(int)
+ {
+ }
+};
+
+#ifdef BOOST_GEOMETRY_TEST_DEBUG
+template <typename Polygon>
+struct debug_validity_phase<Polygon, polygon_tag>
+{
+ 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 <boost/range.hpp>
+
+#include <boost/geometry/core/closure.hpp>
+
+#include <boost/geometry/policies/compare.hpp>
+
+#include <boost/geometry/views/closeable_view.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace is_valid
+{
+
+template <typename Range, closure_selector Closure>
+struct has_duplicates
+{
+ static inline bool apply(Range const& range)
+ {
+ typedef typename closeable_view<Range const, Closure>::type view_type;
+ typedef typename boost::range_iterator<view_type const>::type iterator;
+
+ view_type view(range);
+
+ if ( boost::size(view) < 2 )
+ {
+ return false;
+ }
+
+ geometry::equal_to<typename boost::range_value<Range>::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 <algorithm>
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/point_type.hpp>
+
+#include <boost/geometry/util/range.hpp>
+
+#include <boost/geometry/views/closeable_view.hpp>
+
+#include <boost/geometry/algorithms/equals.hpp>
+#include <boost/geometry/algorithms/detail/point_is_spike_or_equal.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace is_valid
+{
+
+template <typename Point>
+struct equal_to
+{
+ Point const& m_point;
+
+ equal_to(Point const& point)
+ : m_point(point)
+ {}
+
+ template <typename OtherPoint>
+ inline bool operator()(OtherPoint const& other) const
+ {
+ return geometry::equals(m_point, other);
+ }
+};
+
+template <typename Point>
+struct not_equal_to
+{
+ Point const& m_point;
+
+ not_equal_to(Point const& point)
+ : m_point(point)
+ {}
+
+ template <typename OtherPoint>
+ inline bool operator()(OtherPoint const& other) const
+ {
+ return !geometry::equals(other, m_point);
+ }
+};
+
+
+
+template <typename Range, closure_selector Closure>
+struct has_spikes
+{
+ static inline bool apply(Range const& range)
+ {
+ typedef not_equal_to<typename point_type<Range>::type> not_equal;
+
+ typedef typename closeable_view<Range const, Closure>::type view_type;
+ typedef typename boost::range_iterator<view_type const>::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 <boost/geometry/core/point_type.hpp>
+
+#include <boost/geometry/policies/predicate_based_interrupt_policy.hpp>
+#include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
+#include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
+
+#include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+#include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
+
+#include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace is_valid
+{
+
+
+template
+<
+ typename Geometry,
+ typename IsAcceptableTurn = is_acceptable_turn<Geometry>
+>
+class has_valid_self_turns
+{
+private:
+ typedef typename point_type<Geometry>::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 <typename Turns>
+ static inline bool apply(Geometry const& geometry, Turns& turns)
+ {
+ rescale_policy_type robust_policy
+ = geometry::get_rescale_policy<rescale_policy_type>(geometry);
+
+ detail::overlay::stateless_predicate_based_interrupt_policy
+ <
+ IsAcceptableTurn
+ > interrupt_policy;
+
+ geometry::self_turns<turn_policy>(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 <boost/geometry/algorithms/detail/is_valid/pointlike.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/linear.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/polygon.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/multipolygon.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/ring.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/segment.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/box.hpp>
+
+#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 <boost/variant/static_visitor.hpp>
+#include <boost/variant/apply_visitor.hpp>
+#include <boost/variant/variant_fwd.hpp>
+
+#include <boost/geometry/geometries/concepts/check.hpp>
+
+#include <boost/geometry/algorithms/dispatch/is_valid.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+namespace resolve_variant {
+
+template <typename Geometry>
+struct is_valid
+{
+ static inline bool apply(Geometry const& geometry)
+ {
+ concept::check<Geometry const>();
+ return dispatch::is_valid<Geometry>::apply(geometry);
+ }
+};
+
+template <BOOST_VARIANT_ENUM_PARAMS(typename T)>
+struct is_valid<boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> >
+{
+ struct visitor : boost::static_visitor<bool>
+ {
+ template <typename Geometry>
+ bool operator()(Geometry const& geometry) const
+ {
+ return is_valid<Geometry>::apply(geometry);
+ }
+ };
+
+ static inline bool
+ apply(boost::variant<BOOST_VARIANT_ENUM_PARAMS(T)> 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 <typename Geometry>
+inline bool is_valid(Geometry const& geometry)
+{
+ return resolve_variant::is_valid<Geometry>::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 <boost/range.hpp>
+
+#include <boost/geometry/core/point_order.hpp>
+#include <boost/geometry/core/tag.hpp>
+#include <boost/geometry/core/tags.hpp>
+
+#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace is_valid
+{
+
+
+template
+<
+ typename Geometry,
+ order_selector Order = geometry::point_order<Geometry>::value,
+ typename Tag = typename tag<Geometry>::type
+>
+struct acceptable_operation
+{};
+
+template <typename Polygon>
+struct acceptable_operation<Polygon, counterclockwise, polygon_tag>
+{
+ static const detail::overlay::operation_type value =
+ detail::overlay::operation_union;
+};
+
+template <typename Polygon>
+struct acceptable_operation<Polygon, clockwise, polygon_tag>
+{
+ static const detail::overlay::operation_type value =
+ detail::overlay::operation_intersection;
+};
+
+template <typename MultiPolygon>
+struct acceptable_operation<MultiPolygon, counterclockwise, multi_polygon_tag>
+{
+ static const detail::overlay::operation_type value =
+ detail::overlay::operation_intersection;
+};
+
+template <typename MultiPolygon>
+struct acceptable_operation<MultiPolygon, clockwise, multi_polygon_tag>
+{
+ static const detail::overlay::operation_type value =
+ detail::overlay::operation_union;
+};
+
+
+
+
+template <typename Geometry, typename Tag = typename tag<Geometry>::type>
+struct is_acceptable_turn
+{};
+
+template <typename Polygon>
+class is_acceptable_turn<Polygon, polygon_tag>
+{
+protected:
+ template <typename Turn, typename Method, typename Operation>
+ 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 <typename Turn>
+ 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<Polygon>::value;
+
+ return check_turn(turn, method_touch_interior, op)
+ || check_turn(turn, method_touch, op)
+ ;
+ }
+};
+
+template <typename MultiPolygon>
+class is_acceptable_turn<MultiPolygon, multi_polygon_tag>
+ : is_acceptable_turn<typename boost::range_value<MultiPolygon>::type>
+{
+private:
+ typedef typename boost::range_value<MultiPolygon>::type polygon;
+ typedef is_acceptable_turn<polygon> base;
+
+public:
+ template <typename Turn>
+ 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<MultiPolygon>::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 <cstddef>
+
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/closure.hpp>
+#include <boost/geometry/core/point_type.hpp>
+#include <boost/geometry/core/tags.hpp>
+
+#include <boost/geometry/util/range.hpp>
+
+#include <boost/geometry/algorithms/equals.hpp>
+#include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/has_spikes.hpp>
+#include <boost/geometry/algorithms/detail/num_distinct_consecutive_points.hpp>
+
+#include <boost/geometry/algorithms/dispatch/is_valid.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace is_valid
+{
+
+
+template <typename Linestring, bool AllowSpikes>
+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<typename point_type<Linestring>::type>
+ >::apply(linestring);
+
+ if ( num_distinct < 2u )
+ {
+ return false;
+ }
+
+ return num_distinct == 2u
+ || AllowSpikes
+ || !has_spikes<Linestring, closed>::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 <typename Linestring, bool AllowSpikes>
+struct is_valid<Linestring, linestring_tag, AllowSpikes>
+ : detail::is_valid::is_valid_linestring<Linestring, AllowSpikes>
+{};
+
+
+// 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 <typename MultiLinestring, bool AllowSpikes>
+struct is_valid<MultiLinestring, multi_linestring_tag, AllowSpikes>
+{
+ static inline bool apply(MultiLinestring const& multilinestring)
+ {
+ return detail::check_iterator_range
+ <
+ detail::is_valid::is_valid_linestring
+ <
+ typename boost::range_value<MultiLinestring>::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 <deque>
+#include <vector>
+
+#include <boost/iterator/filter_iterator.hpp>
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/exterior_ring.hpp>
+#include <boost/geometry/core/interior_rings.hpp>
+#include <boost/geometry/core/ring_type.hpp>
+#include <boost/geometry/core/tags.hpp>
+
+#include <boost/geometry/util/range.hpp>
+
+#include <boost/geometry/geometries/box.hpp>
+
+#include <boost/geometry/algorithms/within.hpp>
+
+#include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
+#include <boost/geometry/algorithms/detail/partition.hpp>
+
+#include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/polygon.hpp>
+
+#include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp>
+
+#include <boost/geometry/algorithms/dispatch/is_valid.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace is_valid
+{
+
+
+template <typename MultiPolygon, bool AllowDuplicates>
+class is_valid_multipolygon
+ : is_valid_polygon
+ <
+ typename boost::range_value<MultiPolygon>::type,
+ AllowDuplicates,
+ true // check only the validity of rings
+ >
+{
+private:
+ typedef is_valid_polygon
+ <
+ typename boost::range_value<MultiPolygon>::type,
+ AllowDuplicates,
+ true
+ > base;
+
+
+
+ template <typename PolygonIterator, typename TurnIterator>
+ 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<signed_index_type> 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<PolygonIterator> 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<typename point_type<MultiPolygon>::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 <typename Turn>
+ 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 <typename Predicate>
+ struct has_property_per_polygon
+ {
+ template <typename PolygonIterator, typename TurnIterator>
+ 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 <typename PolygonIterator, typename TurnIterator>
+ 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 <typename PolygonIterator, typename TurnIterator>
+ 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<MultiPolygon> 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<MultiPolygon> has_valid_turns;
+
+ std::deque<typename has_valid_turns::turn_type> 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 <typename MultiPolygon, bool AllowSpikes, bool AllowDuplicates>
+struct is_valid<MultiPolygon, multi_polygon_tag, AllowSpikes, AllowDuplicates>
+ : detail::is_valid::is_valid_multipolygon<MultiPolygon, AllowDuplicates>
+{};
+
+
+} // 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 <boost/range.hpp>
+
+#include <boost/geometry/core/tags.hpp>
+
+#include <boost/geometry/algorithms/dispatch/is_valid.hpp>
+
+
+namespace boost { namespace geometry
+{
+
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+// A point is always simple
+template <typename Point>
+struct is_valid<Point, point_tag>
+{
+ 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 <typename MultiPoint>
+struct is_valid<MultiPoint, multi_point_tag>
+{
+ 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 <cstddef>
+
+#include <algorithm>
+#include <deque>
+#include <iterator>
+#include <set>
+#include <vector>
+
+#include <boost/assert.hpp>
+#include <boost/range.hpp>
+
+#include <boost/geometry/core/exterior_ring.hpp>
+#include <boost/geometry/core/interior_rings.hpp>
+#include <boost/geometry/core/ring_type.hpp>
+#include <boost/geometry/core/tags.hpp>
+
+#include <boost/geometry/util/range.hpp>
+
+#include <boost/geometry/geometries/box.hpp>
+
+#include <boost/geometry/iterators/point_iterator.hpp>
+
+#include <boost/geometry/algorithms/covered_by.hpp>
+#include <boost/geometry/algorithms/disjoint.hpp>
+#include <boost/geometry/algorithms/expand.hpp>
+#include <boost/geometry/algorithms/num_interior_rings.hpp>
+#include <boost/geometry/algorithms/within.hpp>
+
+#include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
+#include <boost/geometry/algorithms/detail/partition.hpp>
+
+#include <boost/geometry/algorithms/detail/is_valid/complement_graph.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/has_valid_self_turns.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/is_acceptable_turn.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/ring.hpp>
+
+#include <boost/geometry/algorithms/detail/is_valid/debug_print_turns.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/debug_validity_phase.hpp>
+#include <boost/geometry/algorithms/detail/is_valid/debug_complement_graph.hpp>
+
+#include <boost/geometry/algorithms/dispatch/is_valid.hpp>
+
+
+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<Polygon> debug_phase;
+
+
+
+ template <typename InteriorRings>
+ 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<InteriorRings>::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<Polygon>::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 <typename Box, typename Iterator>
+ static inline void apply(Box& total, Iterator const& it)
+ {
+ geometry::expand(total, geometry::return_envelope<Box>(*it));
+ }
+
+ };
+
+ struct overlaps_box
+ {
+ template <typename Box, typename Iterator>
+ 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 <typename Item1, typename Item2>
+ 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<signed_index_type> 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<RingIterator> 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<typename point_type<Polygon>::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 <typename TurnIterator>
+ 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 <typename TurnIterator>
+ static inline bool apply(Polygon const& polygon,
+ TurnIterator first,
+ TurnIterator beyond)
+ {
+ typedef typename std::iterator_traits
+ <
+ TurnIterator
+ >::value_type turn_type;
+ typedef complement_graph<typename turn_type::point_type> 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<Polygon> has_valid_turns;
+
+ std::deque<typename has_valid_turns::turn_type> 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 <typename Polygon, bool AllowSpikes, bool AllowDuplicates>
+struct is_valid<Polygon, polygon_tag, AllowSpikes, AllowDuplicates>
+ : detail::is_valid::is_valid_polygon<Polygon, AllowDuplicates>
+{};
+
+
+} // 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 <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
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 <boost/geometry/core/point_type.hpp>
+#include <boost/geometry/core/tags.hpp>
+
+#include <boost/geometry/algorithms/assign.hpp>
+#include <boost/geometry/algorithms/equals.hpp>
+
+#include <boost/geometry/algorithms/dispatch/is_valid.hpp>
+
+
+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 <typename Segment>
+struct is_valid<Segment, segment_tag>
+{
+ static inline bool apply(Segment const& segment)
+ {
+ typename point_type<Segment>::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