1 // Copyright (c) 2014 GeometryFactory 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Surface_mesh_shortest_path/include/CGAL/Surface_mesh_shortest_path/internal/Cone_tree.h $ 7 // $Id: Cone_tree.h 254d60f 2019-10-19T15:23:19+02:00 Sébastien Loriot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // Author(s) : Stephen Kiazyk 11 12 #ifndef CGAL_SURFACE_MESH_SHORTEST_PATH_INTERNAL_CONE_TREE_H 13 #define CGAL_SURFACE_MESH_SHORTEST_PATH_INTERNAL_CONE_TREE_H 14 15 #include <CGAL/license/Surface_mesh_shortest_path.h> 16 17 #include <vector> 18 19 #include <boost/graph/graph_traits.hpp> 20 #include <CGAL/boost/graph/iterator.h> 21 22 #include <CGAL/Surface_mesh_shortest_path/internal/Cone_expansion_event.h> 23 #include <CGAL/Surface_mesh_shortest_path/internal/misc_functions.h> 24 25 #include <CGAL/number_utils.h> 26 27 namespace CGAL { 28 namespace Surface_mesh_shortest_paths_3 { 29 namespace internal { 30 31 template<class Traits> 32 class Cone_tree_node 33 { 34 public: 35 enum Node_type 36 { 37 ROOT = 0, 38 FACE_SOURCE = 1, 39 EDGE_SOURCE = 2, 40 VERTEX_SOURCE = 3, 41 INTERVAL = 4 42 }; 43 44 private: 45 typedef typename Traits::Triangle_mesh Triangle_mesh; 46 typedef typename Traits::FT FT; 47 typedef typename Traits::Point_2 Point_2; 48 typedef typename Traits::Triangle_2 Triangle_2; 49 typedef typename Traits::Segment_2 Segment_2; 50 typedef typename Traits::Ray_2 Ray_2; 51 typedef typename boost::graph_traits<Triangle_mesh> Graph_traits; 52 typedef typename Graph_traits::face_descriptor face_descriptor; 53 typedef typename Graph_traits::halfedge_descriptor halfedge_descriptor; 54 typedef typename Graph_traits::vertex_descriptor vertex_descriptor; 55 typedef typename Surface_mesh_shortest_paths_3::internal::Cone_expansion_event<Traits> Cone_expansion_event; 56 57 private: 58 // These could be pulled back into a 'context' class to save space 59 const Traits& m_traits; 60 const Triangle_mesh& m_graph; 61 62 const halfedge_descriptor m_entryEdge; 63 64 const Point_2 m_sourceImage; 65 const Triangle_2 m_layoutFace; 66 const FT m_pseudoSourceDistance; 67 68 const Point_2 m_windowLeft; 69 const Point_2 m_windowRight; 70 71 std::size_t m_level; 72 std::size_t m_treeId; 73 74 const Node_type m_nodeType; 75 76 Cone_tree_node* m_leftChild; 77 std::vector<Cone_tree_node*> m_middleChildren; 78 Cone_tree_node* m_rightChild; 79 80 Cone_tree_node* m_parent; 81 82 public: 83 Cone_expansion_event* m_pendingLeftSubtree; 84 Cone_expansion_event* m_pendingRightSubtree; 85 Cone_expansion_event* m_pendingMiddleSubtree; 86 87 private: on_child_link(Cone_tree_node * child)88 void on_child_link(Cone_tree_node* child) 89 { 90 child->m_parent = this; 91 child->m_level = m_level + 1; 92 child->m_treeId = m_treeId; 93 } 94 95 public: Cone_tree_node(const Traits & traits,const Triangle_mesh & g,const std::size_t treeId)96 Cone_tree_node(const Traits& traits, 97 const Triangle_mesh& g, 98 const std::size_t treeId) 99 : m_traits(traits) 100 , m_graph(g) 101 , m_sourceImage(Point_2(CGAL::ORIGIN)) 102 , m_layoutFace(Point_2(CGAL::ORIGIN),Point_2(CGAL::ORIGIN),Point_2(CGAL::ORIGIN)) 103 , m_pseudoSourceDistance(0.0) 104 , m_level(0) 105 , m_treeId(treeId) 106 , m_nodeType(ROOT) 107 , m_leftChild(nullptr) 108 , m_rightChild(nullptr) 109 , m_pendingLeftSubtree(nullptr) 110 , m_pendingRightSubtree(nullptr) 111 , m_pendingMiddleSubtree(nullptr) 112 { 113 } 114 Cone_tree_node(const Traits & traits,const Triangle_mesh & g,const std::size_t treeId,const halfedge_descriptor entryEdge)115 Cone_tree_node(const Traits& traits, 116 const Triangle_mesh& g, 117 const std::size_t treeId, 118 const halfedge_descriptor entryEdge) 119 : m_traits(traits) 120 , m_graph(g) 121 , m_entryEdge(entryEdge) 122 , m_sourceImage(Point_2(CGAL::ORIGIN)) 123 , m_layoutFace(Point_2(CGAL::ORIGIN),Point_2(CGAL::ORIGIN),Point_2(CGAL::ORIGIN)) 124 , m_pseudoSourceDistance(0.0) 125 , m_level(0) 126 , m_treeId(treeId) 127 , m_nodeType(ROOT) 128 , m_leftChild(nullptr) 129 , m_rightChild(nullptr) 130 , m_pendingLeftSubtree(nullptr) 131 , m_pendingRightSubtree(nullptr) 132 , m_pendingMiddleSubtree(nullptr) 133 { 134 } 135 136 Cone_tree_node(const Traits& traits, 137 const Triangle_mesh& g, 138 const halfedge_descriptor entryEdge, 139 const Triangle_2& layoutFace, 140 const Point_2& sourceImage, 141 const FT& pseudoSourceDistance, 142 const Point_2& windowLeft, 143 const Point_2& windowRight, 144 const Node_type nodeType = INTERVAL) m_traits(traits)145 : m_traits(traits) 146 , m_graph(g) 147 , m_entryEdge(entryEdge) 148 , m_sourceImage(sourceImage) 149 , m_layoutFace(layoutFace) 150 , m_pseudoSourceDistance(pseudoSourceDistance) 151 , m_windowLeft(windowLeft) 152 , m_windowRight(windowRight) 153 , m_nodeType(nodeType) 154 , m_leftChild(nullptr) 155 , m_rightChild(nullptr) 156 , m_pendingLeftSubtree(nullptr) 157 , m_pendingRightSubtree(nullptr) 158 , m_pendingMiddleSubtree(nullptr) 159 { 160 } 161 tree_id()162 std::size_t tree_id() const 163 { 164 return m_treeId; 165 } 166 level()167 std::size_t level() const 168 { 169 return m_level; 170 } 171 is_source_node()172 bool is_source_node() const 173 { 174 return m_nodeType == FACE_SOURCE || m_nodeType == EDGE_SOURCE || m_nodeType == VERTEX_SOURCE; 175 } 176 is_vertex_node()177 bool is_vertex_node() const 178 { 179 return m_nodeType == VERTEX_SOURCE; 180 } 181 is_root_node()182 bool is_root_node() const 183 { 184 return m_nodeType == ROOT; 185 } 186 layout_face()187 const Triangle_2& layout_face() const 188 { 189 return m_layoutFace; 190 } 191 current_face()192 face_descriptor current_face() const 193 { 194 return face(m_entryEdge, m_graph); 195 } 196 is_null_face()197 bool is_null_face() const 198 { 199 return current_face() == Graph_traits::null_face(); 200 } 201 edge_face_index()202 std::size_t edge_face_index() const 203 { 204 return edge_index(entry_edge(), m_graph); 205 } 206 entry_edge()207 halfedge_descriptor entry_edge() const 208 { 209 return m_entryEdge; 210 } 211 left_child_edge()212 halfedge_descriptor left_child_edge() const 213 { 214 return opposite(prev(m_entryEdge, m_graph), m_graph); 215 } 216 right_child_edge()217 halfedge_descriptor right_child_edge() const 218 { 219 return opposite(next(m_entryEdge, m_graph), m_graph); 220 } 221 target_vertex()222 vertex_descriptor target_vertex() const 223 { 224 return target(next(m_entryEdge, m_graph), m_graph); 225 } 226 source_image()227 const Point_2& source_image() const 228 { 229 return m_sourceImage; 230 } 231 node_type()232 Node_type node_type() const 233 { 234 return m_nodeType; 235 } 236 distance_to_root(const Point_2 & point)237 FT distance_to_root(const Point_2& point) const 238 { 239 typename Traits::Compute_squared_distance_2 csd2(m_traits.compute_squared_distance_2_object()); 240 return CGAL::approximate_sqrt(csd2(point, m_sourceImage)) + m_pseudoSourceDistance; 241 } 242 distance_from_source_to_root()243 FT distance_from_source_to_root() const 244 { 245 return m_pseudoSourceDistance; 246 } 247 distance_from_target_to_root()248 FT distance_from_target_to_root() const 249 { 250 return distance_to_root(target_point()); 251 } 252 left_boundary()253 Ray_2 left_boundary() const 254 { 255 return Ray_2(source_image(), m_windowLeft); 256 } 257 right_boundary()258 Ray_2 right_boundary() const 259 { 260 return Ray_2(source_image(), m_windowRight); 261 } 262 window_left()263 const Point_2& window_left() const 264 { 265 return m_windowLeft; 266 } 267 window_right()268 const Point_2& window_right() const 269 { 270 return m_windowRight; 271 } 272 ray_to_target_vertex()273 Ray_2 ray_to_target_vertex() const 274 { 275 return Ray_2(source_image(), target_point()); 276 } 277 inside_window(const Point_2 & point)278 bool inside_window(const Point_2& point) const 279 { 280 typename Traits::Orientation_2 orientation_2(m_traits.orientation_2_object()); 281 282 Point_2 sourceImagePoint(source_image()); 283 CGAL::Orientation leftOrientation = orientation_2(sourceImagePoint, m_windowLeft, point); 284 CGAL::Orientation rightOrientation = orientation_2(sourceImagePoint, m_windowRight, point); 285 286 return (leftOrientation == CGAL::RIGHT_TURN || leftOrientation == CGAL::COLLINEAR) && 287 (rightOrientation == CGAL::LEFT_TURN || rightOrientation == CGAL::COLLINEAR); 288 } 289 target_point()290 Point_2 target_point() const 291 { 292 typename Traits::Construct_vertex_2 cv2(m_traits.construct_vertex_2_object()); 293 return cv2(m_layoutFace, 2); 294 } 295 is_target_vertex_inside_window()296 bool is_target_vertex_inside_window() const 297 { 298 return inside_window(target_point()); 299 } 300 has_left_side()301 bool has_left_side() const 302 { 303 if (is_source_node()) 304 { 305 return true; 306 } 307 308 return (m_traits.orientation_2_object()(source_image(), m_windowLeft, target_point()) != CGAL::LEFT_TURN); 309 } 310 has_right_side()311 bool has_right_side() const 312 { 313 return (m_traits.orientation_2_object()(source_image(), m_windowRight, target_point()) != CGAL::RIGHT_TURN); 314 } 315 left_child_base_segment()316 Segment_2 left_child_base_segment() const 317 { 318 typename Traits::Construct_vertex_2 cv2(m_traits.construct_vertex_2_object()); 319 // reversed to maintain consistent triangle winding on the child 320 return Segment_2(cv2(m_layoutFace, 0), cv2(m_layoutFace, 2)); 321 } 322 right_child_base_segment()323 Segment_2 right_child_base_segment() const 324 { 325 typename Traits::Construct_vertex_2 cv2(m_traits.construct_vertex_2_object()); 326 // reversed to maintain consistent triangle winding on the child 327 return Segment_2(cv2(m_layoutFace, 2), cv2(m_layoutFace, 1)); 328 } 329 entry_segment()330 Segment_2 entry_segment() const 331 { 332 typename Traits::Construct_vertex_2 cv2(m_traits.construct_vertex_2_object()); 333 return Segment_2(cv2(m_layoutFace, 0), cv2(m_layoutFace, 1)); 334 } 335 has_middle_children()336 bool has_middle_children() const 337 { 338 return m_middleChildren.size() > 0; 339 } 340 num_middle_children()341 std::size_t num_middle_children() const 342 { 343 return m_middleChildren.size(); 344 } 345 get_middle_child(const std::size_t i)346 Cone_tree_node* get_middle_child(const std::size_t i) const 347 { 348 return m_middleChildren.at(i); 349 } 350 push_middle_child(Cone_tree_node * child)351 void push_middle_child(Cone_tree_node* child) 352 { 353 if (m_pendingMiddleSubtree != nullptr) 354 { 355 m_pendingMiddleSubtree->m_cancelled = true; 356 m_pendingMiddleSubtree = nullptr; 357 } 358 359 m_middleChildren.push_back(child); 360 on_child_link(child); 361 } 362 pop_middle_child()363 Cone_tree_node* pop_middle_child() 364 { 365 Cone_tree_node* temp = m_middleChildren.back(); 366 m_middleChildren.pop_back(); 367 return temp; 368 } 369 set_left_child(Cone_tree_node * child)370 void set_left_child(Cone_tree_node* child) 371 { 372 if (m_pendingLeftSubtree != nullptr) 373 { 374 m_pendingLeftSubtree->m_cancelled = true; 375 m_pendingLeftSubtree = nullptr; 376 } 377 378 m_leftChild = child; 379 on_child_link(child); 380 } 381 get_left_child()382 Cone_tree_node* get_left_child() const 383 { 384 return m_leftChild; 385 } 386 remove_left_child()387 Cone_tree_node* remove_left_child() 388 { 389 Cone_tree_node* temp = m_leftChild; 390 m_leftChild = nullptr; 391 return temp; 392 } 393 set_right_child(Cone_tree_node * child)394 void set_right_child(Cone_tree_node* child) 395 { 396 if (m_pendingRightSubtree != nullptr) 397 { 398 m_pendingRightSubtree->m_cancelled = true; 399 m_pendingRightSubtree = nullptr; 400 } 401 402 m_rightChild = child; 403 on_child_link(child); 404 } 405 get_right_child()406 Cone_tree_node* get_right_child() const 407 { 408 return m_rightChild; 409 } 410 remove_right_child()411 Cone_tree_node* remove_right_child() 412 { 413 Cone_tree_node* temp = m_rightChild; 414 m_rightChild = nullptr; 415 return temp; 416 } 417 parent()418 Cone_tree_node* parent() const 419 { 420 return m_parent; 421 } 422 is_left_child()423 bool is_left_child() const 424 { 425 return m_parent != nullptr && m_parent->m_leftChild == this; 426 } 427 is_right_child()428 bool is_right_child() const 429 { 430 return m_parent != nullptr && m_parent->m_rightChild == this; 431 } 432 }; 433 434 } // namespace internal 435 } // namespace Surface_mesh_shortest_paths_3 436 } // namespace CGAL 437 438 #endif // CGAL_SURFACE_MESH_SHORTEST_PATH_INTERNAL_CONE_TREE_H 439