detail/is_valid/complement_graph.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2014-2023, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0006 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0007 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0008
0009 // Licensed under the Boost Software License version 1.0.
0010 // http://www.boost.org/users/license.html
0011
0012 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP
0013 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP
0014
0015 #include <cstddef>
0016
0017 #include <set>
0018 #include <stack>
0019 #include <utility>
0020 #include <vector>
0021
0022 #include <boost/core/addressof.hpp>
0023
0024 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
0025 #include <boost/geometry/core/assert.hpp>
0026 #include <boost/geometry/policies/compare.hpp>
0027
0028
0029 namespace boost { namespace geometry
0030 {
0031
0032 namespace detail { namespace is_valid
0033 {
0034
0035
0036 template <typename TurnPoint, typename Strategy>
0037 class complement_graph_vertex
0038 {
0039 public:
0040     complement_graph_vertex(std::size_t id)
0041         : m_id(id)
0042         , m_turn_point(NULL)
0043     {}
0044
0045     complement_graph_vertex(TurnPoint const* turn_point,
0046                             std::size_t expected_id)
0047         : m_id(expected_id)
0048         , m_turn_point(turn_point)
0049     {}
0050
0051     inline std::size_t id() const { return m_id; }
0052
0053     inline bool operator<(complement_graph_vertex const& other) const
0054     {
0055         if ( m_turn_point != NULL && other.m_turn_point != NULL )
0056         {
0057             return geometry::less
0058                 <
0059                     TurnPoint, -1, Strategy
0060                 >()(*m_turn_point, *other.m_turn_point);
0061         }
0062         if ( m_turn_point == NULL && other.m_turn_point == NULL )
0063         {
0064             return m_id < other.m_id;
0065         }
0066         return m_turn_point == NULL;
0067     }
0068
0069 private:
0070     // the value of m_turn_point determines the type of the vertex
0071     // non-NULL: vertex corresponds to an IP
0072     // NULL    : vertex corresponds to a hole or outer space, and the id
0073     //           is the ring id of the corresponding ring of the polygon
0074     std::size_t m_id;
0075     TurnPoint const* m_turn_point;
0076 };
0077
0078
0079
0080
0081 template <typename TurnPoint, typename Strategy>
0082 class complement_graph
0083 {
0084 private:
0085     typedef complement_graph_vertex<TurnPoint, Strategy> vertex;
0086     typedef std::set<vertex> vertex_container;
0087
0088 public:
0089     typedef typename vertex_container::const_iterator vertex_handle;
0090
0091 private:
0092     struct vertex_handle_less
0093     {
0094         inline bool operator()(vertex_handle v1, vertex_handle v2) const
0095         {
0096             return v1->id() < v2->id();
0097         }
0098     };
0099
0100     typedef std::set<vertex_handle, vertex_handle_less> neighbor_container;
0101
0102     class has_cycles_dfs_data
0103     {
0104     public:
0105         has_cycles_dfs_data(std::size_t num_nodes)
0106             : m_visited(num_nodes, false)
0107             , m_parent_id(num_nodes, -1)
0108         {}
0109
0110         inline signed_size_type parent_id(vertex_handle v) const
0111         {
0112             return m_parent_id[v->id()];
0113         }
0114
0115         inline void set_parent_id(vertex_handle v, signed_size_type id)
0116         {
0117             m_parent_id[v->id()] = id;
0118         }
0119
0120         inline bool visited(vertex_handle v) const
0121         {
0122             return m_visited[v->id()];
0123         }
0124
0125         inline void set_visited(vertex_handle v, bool value)
0126         {
0127             m_visited[v->id()] = value;
0128         }
0129     private:
0130         std::vector<bool> m_visited;
0131         std::vector<signed_size_type> m_parent_id;
0132     };
0133
0134
0135     inline bool has_cycles(vertex_handle start_vertex,
0136                            has_cycles_dfs_data& data) const
0137     {
0138         std::stack<vertex_handle> stack;
0139         stack.push(start_vertex);
0140
0141         while ( !stack.empty() )
0142         {
0143             vertex_handle v = stack.top();
0144             stack.pop();
0145
0146             data.set_visited(v, true);
0147             for (typename neighbor_container::const_iterator nit
0148                      = m_neighbors[v->id()].begin();
0149                  nit != m_neighbors[v->id()].end(); ++nit)
0150             {
0151                 if ( static_cast<signed_size_type>((*nit)->id()) != data.parent_id(v) )
0152                 {
0153                     if ( data.visited(*nit) )
0154                     {
0155                         return true;
0156                     }
0157                     else
0158                     {
0159                         data.set_parent_id(*nit, static_cast<signed_size_type>(v->id()));
0160                         stack.push(*nit);
0161                     }
0162                 }
0163             }
0164         }
0165         return false;
0166     }
0167
0168 public:
0169     // num_rings: total number of rings, including the exterior ring
0170     complement_graph(std::size_t num_rings)
0171         : m_num_rings(num_rings)
0172         , m_num_turns(0)
0173         , m_vertices()
0174         , m_neighbors(num_rings)
0175     {}
0176
0177     // inserts a ring vertex in the graph and returns its handle
0178     // ring id's are zero-based (so the first interior ring has id 1)
0179     inline vertex_handle add_vertex(signed_size_type id)
0180     {
0181         return m_vertices.insert(vertex(static_cast<std::size_t>(id))).first;
0182     }
0183
0184     // inserts an IP in the graph and returns its id
0185     inline vertex_handle add_vertex(TurnPoint const& turn_point)
0186     {
0187         std::pair<vertex_handle, bool> res
0188             = m_vertices.insert(vertex(boost::addressof(turn_point),
0189                                        m_num_rings + m_num_turns)
0190                                 );
0191
0192         if ( res.second )
0193         {
0194             // a new element is inserted
0195             m_neighbors.push_back(neighbor_container());
0196             ++m_num_turns;
0197         }
0198         return res.first;
0199     }
0200
0201     inline void add_edge(vertex_handle v1, vertex_handle v2)
0202     {
0203         BOOST_GEOMETRY_ASSERT( v1 != m_vertices.end() );
0204         BOOST_GEOMETRY_ASSERT( v2 != m_vertices.end() );
0205         m_neighbors[v1->id()].insert(v2);
0206         m_neighbors[v2->id()].insert(v1);
0207     }
0208
0209     inline bool has_cycles() const
0210     {
0211         // initialize all vertices as non-visited and with no parent set
0212         // this is done by the constructor of has_cycles_dfs_data
0213         has_cycles_dfs_data data(m_num_rings + m_num_turns);
0214
0215         // for each non-visited vertex, start a DFS from that vertex
0216         for (vertex_handle it = m_vertices.begin();
0217              it != m_vertices.end(); ++it)
0218         {
0219             if ( !data.visited(it) && has_cycles(it, data) )
0220             {
0221                 return true;
0222             }
0223         }
0224         return false;
0225     }
0226
0227 #ifdef BOOST_GEOMETRY_TEST_DEBUG
0228     template <typename OutputStream>
0229     friend inline
0230     void debug_print_complement_graph(OutputStream&,
0231                                       complement_graph<TurnPoint, Strategy> const&);
0232 #endif // BOOST_GEOMETRY_TEST_DEBUG
0233
0234 private:
0235     std::size_t m_num_rings, m_num_turns;
0236     vertex_container m_vertices;
0237     std::vector<neighbor_container> m_neighbors;
0238 };
0239
0240
0241 }} // namespace detail::is_valid
0242
0243 }} // namespace boost::geometry
0244
0245 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP