1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2014, 2018, 2019, Oracle and/or its affiliates. 4 5 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 6 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 7 8 // Licensed under the Boost Software License version 1.0. 9 // http://www.boost.org/users/license.html 10 11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP 12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP 13 14 #include <cstddef> 15 16 #include <set> 17 #include <stack> 18 #include <utility> 19 #include <vector> 20 21 #include <boost/core/addressof.hpp> 22 23 #include <boost/geometry/algorithms/detail/signed_size_type.hpp> 24 #include <boost/geometry/core/assert.hpp> 25 #include <boost/geometry/policies/compare.hpp> 26 27 28 namespace boost { namespace geometry 29 { 30 31 namespace detail { namespace is_valid 32 { 33 34 35 template <typename TurnPoint, typename CSTag> 36 class complement_graph_vertex 37 { 38 public: complement_graph_vertex(std::size_t id)39 complement_graph_vertex(std::size_t id) 40 : m_id(id) 41 , m_turn_point(NULL) 42 {} 43 complement_graph_vertex(TurnPoint const * turn_point,std::size_t expected_id)44 complement_graph_vertex(TurnPoint const* turn_point, 45 std::size_t expected_id) 46 : m_id(expected_id) 47 , m_turn_point(turn_point) 48 {} 49 id() const50 inline std::size_t id() const { return m_id; } 51 operator <(complement_graph_vertex const & other) const52 inline bool operator<(complement_graph_vertex const& other) const 53 { 54 if ( m_turn_point != NULL && other.m_turn_point != NULL ) 55 { 56 return geometry::less 57 < 58 TurnPoint, -1, CSTag 59 >()(*m_turn_point, *other.m_turn_point); 60 } 61 if ( m_turn_point == NULL && other.m_turn_point == NULL ) 62 { 63 return m_id < other.m_id; 64 } 65 return m_turn_point == NULL; 66 } 67 68 private: 69 // the value of m_turn_point determines the type of the vertex 70 // non-NULL: vertex corresponds to an IP 71 // NULL : vertex corresponds to a hole or outer space, and the id 72 // is the ring id of the corresponding ring of the polygon 73 std::size_t m_id; 74 TurnPoint const* m_turn_point; 75 }; 76 77 78 79 80 template <typename TurnPoint, typename CSTag> 81 class complement_graph 82 { 83 private: 84 typedef complement_graph_vertex<TurnPoint, CSTag> vertex; 85 typedef std::set<vertex> vertex_container; 86 87 public: 88 typedef typename vertex_container::const_iterator vertex_handle; 89 90 private: 91 struct vertex_handle_less 92 { operator ()boost::geometry::detail::is_valid::complement_graph::vertex_handle_less93 inline bool operator()(vertex_handle v1, vertex_handle v2) const 94 { 95 return v1->id() < v2->id(); 96 } 97 }; 98 99 typedef std::set<vertex_handle, vertex_handle_less> neighbor_container; 100 101 class has_cycles_dfs_data 102 { 103 public: has_cycles_dfs_data(std::size_t num_nodes)104 has_cycles_dfs_data(std::size_t num_nodes) 105 : m_visited(num_nodes, false) 106 , m_parent_id(num_nodes, -1) 107 {} 108 parent_id(vertex_handle v) const109 inline signed_size_type parent_id(vertex_handle v) const 110 { 111 return m_parent_id[v->id()]; 112 } 113 set_parent_id(vertex_handle v,signed_size_type id)114 inline void set_parent_id(vertex_handle v, signed_size_type id) 115 { 116 m_parent_id[v->id()] = id; 117 } 118 visited(vertex_handle v) const119 inline bool visited(vertex_handle v) const 120 { 121 return m_visited[v->id()]; 122 } 123 set_visited(vertex_handle v,bool value)124 inline void set_visited(vertex_handle v, bool value) 125 { 126 m_visited[v->id()] = value; 127 } 128 private: 129 std::vector<bool> m_visited; 130 std::vector<signed_size_type> m_parent_id; 131 }; 132 133 has_cycles(vertex_handle start_vertex,has_cycles_dfs_data & data) const134 inline bool has_cycles(vertex_handle start_vertex, 135 has_cycles_dfs_data& data) const 136 { 137 std::stack<vertex_handle> stack; 138 stack.push(start_vertex); 139 140 while ( !stack.empty() ) 141 { 142 vertex_handle v = stack.top(); 143 stack.pop(); 144 145 data.set_visited(v, true); 146 for (typename neighbor_container::const_iterator nit 147 = m_neighbors[v->id()].begin(); 148 nit != m_neighbors[v->id()].end(); ++nit) 149 { 150 if ( static_cast<signed_size_type>((*nit)->id()) != data.parent_id(v) ) 151 { 152 if ( data.visited(*nit) ) 153 { 154 return true; 155 } 156 else 157 { 158 data.set_parent_id(*nit, static_cast<signed_size_type>(v->id())); 159 stack.push(*nit); 160 } 161 } 162 } 163 } 164 return false; 165 } 166 167 public: 168 // num_rings: total number of rings, including the exterior ring complement_graph(std::size_t num_rings)169 complement_graph(std::size_t num_rings) 170 : m_num_rings(num_rings) 171 , m_num_turns(0) 172 , m_vertices() 173 , m_neighbors(num_rings) 174 {} 175 176 // inserts a ring vertex in the graph and returns its handle 177 // ring id's are zero-based (so the first interior ring has id 1) add_vertex(signed_size_type id)178 inline vertex_handle add_vertex(signed_size_type id) 179 { 180 return m_vertices.insert(vertex(static_cast<std::size_t>(id))).first; 181 } 182 183 // inserts an IP in the graph and returns its id add_vertex(TurnPoint const & turn_point)184 inline vertex_handle add_vertex(TurnPoint const& turn_point) 185 { 186 std::pair<vertex_handle, bool> res 187 = m_vertices.insert(vertex(boost::addressof(turn_point), 188 m_num_rings + m_num_turns) 189 ); 190 191 if ( res.second ) 192 { 193 // a new element is inserted 194 m_neighbors.push_back(neighbor_container()); 195 ++m_num_turns; 196 } 197 return res.first; 198 } 199 add_edge(vertex_handle v1,vertex_handle v2)200 inline void add_edge(vertex_handle v1, vertex_handle v2) 201 { 202 BOOST_GEOMETRY_ASSERT( v1 != m_vertices.end() ); 203 BOOST_GEOMETRY_ASSERT( v2 != m_vertices.end() ); 204 m_neighbors[v1->id()].insert(v2); 205 m_neighbors[v2->id()].insert(v1); 206 } 207 has_cycles() const208 inline bool has_cycles() const 209 { 210 // initialize all vertices as non-visited and with no parent set 211 // this is done by the constructor of has_cycles_dfs_data 212 has_cycles_dfs_data data(m_num_rings + m_num_turns); 213 214 // for each non-visited vertex, start a DFS from that vertex 215 for (vertex_handle it = m_vertices.begin(); 216 it != m_vertices.end(); ++it) 217 { 218 if ( !data.visited(it) && has_cycles(it, data) ) 219 { 220 return true; 221 } 222 } 223 return false; 224 } 225 226 #ifdef BOOST_GEOMETRY_TEST_DEBUG 227 template <typename OStream, typename TP> 228 friend inline 229 void debug_print_complement_graph(OStream&, complement_graph<TP> const&); 230 #endif // BOOST_GEOMETRY_TEST_DEBUG 231 232 private: 233 std::size_t m_num_rings, m_num_turns; 234 vertex_container m_vertices; 235 std::vector<neighbor_container> m_neighbors; 236 }; 237 238 239 }} // namespace detail::is_valid 240 241 }} // namespace boost::geometry 242 243 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_IS_VALID_COMPLEMENT_GRAPH_HPP 244