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