1 // Copyright (c) 2002,2011 Utrecht University (The Netherlands). 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/Spatial_searching/include/CGAL/Kd_tree_node.h $ 7 // $Id: Kd_tree_node.h bd08ba8 2020-04-27T11:26:43+02:00 Simon Giraudot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Authors : Hans Tangelder (<hanst@cs.uu.nl>) 12 13 #ifndef CGAL_KD_TREE_NODE_H 14 #define CGAL_KD_TREE_NODE_H 15 16 #include <CGAL/license/Spatial_searching.h> 17 18 19 20 #include <CGAL/Splitters.h> 21 #include <CGAL/Compact_container.h> 22 #include <CGAL/Has_member.h> 23 #include <CGAL/internal/Search_helpers.h> 24 #include <boost/cstdint.hpp> 25 26 namespace CGAL { 27 28 CGAL_GENERATE_MEMBER_DETECTOR(contains_point_given_as_coordinates); 29 30 template <class SearchTraits, class Splitter, class UseExtendedNode, class EnablePointsCache> 31 class Kd_tree; 32 33 template < class TreeTraits, class Splitter, class UseExtendedNode, class EnablePointsCache > 34 class Kd_tree_node { 35 36 friend class Kd_tree<TreeTraits, Splitter, UseExtendedNode, EnablePointsCache>; 37 38 typedef Kd_tree<TreeTraits, Splitter, UseExtendedNode, EnablePointsCache> Kdt; 39 40 typedef typename Kdt::Node_handle Node_handle; 41 typedef typename Kdt::Node_const_handle Node_const_handle; 42 typedef typename Kdt::Internal_node_handle Internal_node_handle; 43 typedef typename Kdt::Internal_node_const_handle Internal_node_const_handle; 44 typedef typename Kdt::Leaf_node_handle Leaf_node_handle; 45 typedef typename Kdt::Leaf_node_const_handle Leaf_node_const_handle; 46 typedef typename TreeTraits::Point_d Point_d; 47 48 typedef typename TreeTraits::FT FT; 49 typedef typename Kdt::Separator Separator; 50 typedef typename Kdt::Point_d_iterator Point_d_iterator; 51 typedef typename Kdt::iterator iterator; 52 typedef typename Kdt::D D; 53 54 bool leaf; 55 56 public : Kd_tree_node(bool leaf)57 Kd_tree_node(bool leaf) : leaf(leaf) { } 58 is_leaf()59 bool is_leaf() const { return leaf; } 60 61 std::size_t num_items()62 num_items() const 63 { 64 if (is_leaf()){ 65 Leaf_node_const_handle node = 66 static_cast<Leaf_node_const_handle>(this); 67 return node->size(); 68 } 69 else { 70 Internal_node_const_handle node = 71 static_cast<Internal_node_const_handle>(this); 72 return node->lower()->num_items() + node->upper()->num_items(); 73 } 74 } 75 76 std::size_t num_nodes()77 num_nodes() const 78 { 79 if (is_leaf()) return 1; 80 else { 81 Internal_node_const_handle node = 82 static_cast<Internal_node_const_handle>(this); 83 return node->lower()->num_nodes() + node->upper()->num_nodes(); 84 } 85 } 86 87 int depth(const int current_max_depth)88 depth(const int current_max_depth) const 89 { 90 if (is_leaf()){ 91 return current_max_depth; 92 } 93 else { 94 Internal_node_const_handle node = 95 static_cast<Internal_node_const_handle>(this); 96 return 97 (std::max)( node->lower()->depth(current_max_depth + 1), 98 node->upper()->depth(current_max_depth + 1)); 99 } 100 } 101 102 int depth()103 depth() const 104 { 105 return depth(1); 106 } 107 108 template <class OutputIterator> 109 OutputIterator tree_items(OutputIterator it)110 tree_items(OutputIterator it) const { 111 if (is_leaf()) { 112 Leaf_node_const_handle node = 113 static_cast<Leaf_node_const_handle>(this); 114 if (node->size()>0) 115 for (iterator i=node->begin(); i != node->end(); i++) 116 {*it=*i; ++it;} 117 } 118 else { 119 Internal_node_const_handle node = 120 static_cast<Internal_node_const_handle>(this); 121 it=node->lower()->tree_items(it); 122 it=node->upper()->tree_items(it); 123 } 124 return it; 125 } 126 127 128 boost::optional<Point_d> any_tree_item()129 any_tree_item() const { 130 boost::optional<Point_d> result = boost::none; 131 if (is_leaf()) { 132 Leaf_node_const_handle node = 133 static_cast<Leaf_node_const_handle>(this); 134 if (node->size()>0){ 135 return boost::make_optional(*(node->begin())); 136 } 137 } 138 else { 139 Internal_node_const_handle node = 140 static_cast<Internal_node_const_handle>(this); 141 result = node->lower()->any_tree_item(); 142 if(! result){ 143 result = node->upper()->any_tree_item(); 144 } 145 } 146 return result; 147 } 148 149 150 void indent(int d)151 indent(int d) const 152 { 153 for(int i = 0; i < d; i++){ 154 std::cout << " "; 155 } 156 } 157 158 159 void 160 print(int d = 0) const 161 { 162 if (is_leaf()) { 163 Leaf_node_const_handle node = 164 static_cast<Leaf_node_const_handle>(this); 165 indent(d); 166 std::cout << "leaf" << std::endl; 167 if (node->size()>0) 168 for (iterator i=node->begin(); i != node->end(); i++) 169 {indent(d);std::cout << *i << std::endl;} 170 } 171 else { 172 Internal_node_const_handle node = 173 static_cast<Internal_node_const_handle>(this); 174 indent(d); 175 std::cout << "lower tree" << std::endl; 176 node->lower()->print(d+1); 177 indent(d); 178 std::cout << "separator: dim = " << node->cutting_dimension() << " val = " << node->cutting_value() << std::endl; 179 indent(d); 180 std::cout << "upper tree" << std::endl; 181 node->upper()->print(d+1); 182 } 183 } 184 185 186 template <class OutputIterator, class FuzzyQueryItem> 187 OutputIterator search(OutputIterator it,const FuzzyQueryItem & q,Kd_tree_rectangle<FT,D> & b,typename Kdt::const_iterator tree_points_begin,typename std::vector<FT>::const_iterator cache_begin,int dim)188 search(OutputIterator it, const FuzzyQueryItem& q, 189 Kd_tree_rectangle<FT,D>& b, 190 typename Kdt::const_iterator tree_points_begin, 191 typename std::vector<FT>::const_iterator cache_begin, 192 int dim) const 193 { 194 if (is_leaf()) { 195 Leaf_node_const_handle node = 196 static_cast<Leaf_node_const_handle>(this); 197 if (node->size() > 0) 198 { 199 typename internal::Has_points_cache<Kdt, internal::has_Enable_points_cache<Kdt>::type::value>::type dummy; 200 it = search_in_leaf(node, q, tree_points_begin, cache_begin, dim, it, dummy); 201 } 202 } 203 else { 204 Internal_node_const_handle node = 205 static_cast<Internal_node_const_handle>(this); 206 // after splitting b denotes the lower part of b 207 Kd_tree_rectangle<FT,D> b_upper(b); 208 node->split_bbox(b, b_upper); 209 210 if (q.outer_range_contains(b)) 211 it=node->lower()->tree_items(it); 212 else 213 if (q.inner_range_intersects(b)) 214 it=node->lower()->search(it,q,b,tree_points_begin,cache_begin,dim); 215 if (q.outer_range_contains(b_upper)) 216 it=node->upper()->tree_items(it); 217 else 218 if (q.inner_range_intersects(b_upper)) 219 it=node->upper()->search(it,q,b_upper,tree_points_begin,cache_begin,dim); 220 }; 221 return it; 222 } 223 224 225 template <class FuzzyQueryItem> 226 boost::optional<Point_d> search_any_point(const FuzzyQueryItem & q,Kd_tree_rectangle<FT,D> & b,typename Kdt::const_iterator tree_points_begin,typename std::vector<FT>::const_iterator cache_begin,int dim)227 search_any_point(const FuzzyQueryItem& q, 228 Kd_tree_rectangle<FT,D>& b, 229 typename Kdt::const_iterator tree_points_begin, 230 typename std::vector<FT>::const_iterator cache_begin, 231 int dim) const 232 { 233 boost::optional<Point_d> result = boost::none; 234 if (is_leaf()) { 235 Leaf_node_const_handle node = 236 static_cast<Leaf_node_const_handle>(this); 237 if (node->size()>0) 238 { 239 typename internal::Has_points_cache<Kdt, internal::has_Enable_points_cache<Kdt>::type::value>::type dummy; 240 result = search_any_point_in_leaf(node, q, tree_points_begin, cache_begin, dim, dummy); 241 } 242 } 243 else { 244 Internal_node_const_handle node = 245 static_cast<Internal_node_const_handle>(this); 246 // after splitting b denotes the lower part of b 247 Kd_tree_rectangle<FT,D> b_upper(b); 248 node->split_bbox(b, b_upper); 249 250 if (q.inner_range_intersects(b)) { 251 result = node->lower()->search_any_point(q,b,tree_points_begin,cache_begin,dim); 252 if(result) 253 return result; 254 } 255 if (q.inner_range_intersects(b_upper)) 256 result = node->upper()->search_any_point(q,b_upper,tree_points_begin,cache_begin,dim); 257 } 258 return result; 259 } 260 261 private: 262 263 // If contains_point_given_as_coordinates does not exist in `FuzzyQueryItem` 264 template <typename FuzzyQueryItem> contains(const FuzzyQueryItem & q,Point_d const & p,typename std::vector<FT>::const_iterator,typename std::vector<FT>::const_iterator,Tag_false)265 bool contains( 266 const FuzzyQueryItem& q, 267 Point_d const& p, 268 typename std::vector<FT>::const_iterator /*it_coord_begin*/, 269 typename std::vector<FT>::const_iterator /*it_coord_end*/, 270 Tag_false /*has_contains_point_given_as_coordinates*/) const 271 { 272 return q.contains(p); 273 } 274 // ... or if it exists 275 template <typename FuzzyQueryItem> contains(const FuzzyQueryItem & q,Point_d const &,typename std::vector<FT>::const_iterator it_coord_begin,typename std::vector<FT>::const_iterator it_coord_end,Tag_true)276 bool contains( 277 const FuzzyQueryItem& q, 278 Point_d const& /*p*/, 279 typename std::vector<FT>::const_iterator it_coord_begin, 280 typename std::vector<FT>::const_iterator it_coord_end, 281 Tag_true /*has_contains_point_given_as_coordinates*/) const 282 { 283 return q.contains_point_given_as_coordinates(it_coord_begin, it_coord_end); 284 } 285 286 // With cache 287 template<class FuzzyQueryItem, class OutputIterator> search_in_leaf(Leaf_node_const_handle node,const FuzzyQueryItem & q,typename Kdt::const_iterator tree_points_begin,typename std::vector<FT>::const_iterator cache_begin,int dim,OutputIterator oit,Tag_true)288 OutputIterator search_in_leaf( 289 Leaf_node_const_handle node, 290 const FuzzyQueryItem &q, 291 typename Kdt::const_iterator tree_points_begin, 292 typename std::vector<FT>::const_iterator cache_begin, 293 int dim, 294 OutputIterator oit, 295 Tag_true /*has_points_cache*/) const 296 { 297 typename Kdt::iterator it_node_point = node->begin(), it_node_point_end = node->end(); 298 typename std::vector<FT>::const_iterator cache_point_it = cache_begin + dim*(it_node_point - tree_points_begin); 299 for (; it_node_point != it_node_point_end; ++it_node_point, cache_point_it += dim) 300 { 301 Boolean_tag<has_contains_point_given_as_coordinates<FuzzyQueryItem>::value> dummy; 302 if (contains(q, *it_node_point, cache_point_it, cache_point_it + dim, dummy)) 303 *oit++ = *it_node_point; 304 } 305 return oit; 306 } 307 308 // Without cache 309 template<class FuzzyQueryItem, class OutputIterator> search_in_leaf(Leaf_node_const_handle node,const FuzzyQueryItem & q,typename Kdt::const_iterator,typename std::vector<FT>::const_iterator,int,OutputIterator oit,Tag_false)310 OutputIterator search_in_leaf( 311 Leaf_node_const_handle node, 312 const FuzzyQueryItem &q, 313 typename Kdt::const_iterator /*tree_points_begin*/, 314 typename std::vector<FT>::const_iterator /*cache_begin*/, 315 int /*dim*/, 316 OutputIterator oit, 317 Tag_false /*has_points_cache*/) const 318 { 319 for (iterator i = node->begin(); i != node->end(); ++i) 320 { 321 if (q.contains(*i)) 322 *oit++ = *i; 323 } 324 return oit; 325 } 326 327 // With cache 328 template<class FuzzyQueryItem> search_any_point_in_leaf(Leaf_node_const_handle node,const FuzzyQueryItem & q,typename Kdt::const_iterator tree_points_begin,typename std::vector<FT>::const_iterator cache_begin,int dim,Tag_true)329 boost::optional<Point_d> search_any_point_in_leaf( 330 Leaf_node_const_handle node, 331 const FuzzyQueryItem &q, 332 typename Kdt::const_iterator tree_points_begin, 333 typename std::vector<FT>::const_iterator cache_begin, 334 int dim, 335 Tag_true /*has_points_cache*/) const 336 { 337 boost::optional<Point_d> result = boost::none; 338 typename Kdt::iterator it_node_point = node->begin(), it_node_point_end = node->end(); 339 typename std::vector<FT>::const_iterator cache_point_it = cache_begin + dim*(it_node_point - tree_points_begin); 340 for (; it_node_point != it_node_point_end; ++it_node_point, cache_point_it += dim) 341 { 342 Boolean_tag<has_contains_point_given_as_coordinates<FuzzyQueryItem>::value> dummy; 343 if (contains(q, *it_node_point, cache_point_it, cache_point_it + dim, dummy)) 344 { 345 result = *it_node_point; 346 break; 347 } 348 } 349 return result; 350 } 351 352 // Without cache 353 template<class FuzzyQueryItem> search_any_point_in_leaf(Leaf_node_const_handle node,const FuzzyQueryItem & q,typename Kdt::const_iterator,typename std::vector<FT>::const_iterator,int,Tag_false)354 boost::optional<Point_d> search_any_point_in_leaf( 355 Leaf_node_const_handle node, 356 const FuzzyQueryItem &q, 357 typename Kdt::const_iterator /*tree_points_begin*/, 358 typename std::vector<FT>::const_iterator /*cache_begin*/, 359 int /*dim*/, 360 Tag_false /*has_points_cache*/) const 361 { 362 boost::optional<Point_d> result = boost::none; 363 for (iterator i = node->begin(); i != node->end(); ++i) 364 { 365 if (q.contains(*i)) 366 { 367 result = *i; 368 break; 369 } 370 } 371 return result; 372 } 373 }; 374 375 376 template < class TreeTraits, class Splitter, class UseExtendedNode, class EnablePointsCache > 377 class Kd_tree_leaf_node : public Kd_tree_node< TreeTraits, Splitter, UseExtendedNode, EnablePointsCache >{ 378 379 friend class Kd_tree<TreeTraits, Splitter, UseExtendedNode, EnablePointsCache>; 380 381 typedef typename Kd_tree<TreeTraits, Splitter, UseExtendedNode, EnablePointsCache>::iterator iterator; 382 typedef Kd_tree_node< TreeTraits, Splitter, UseExtendedNode, EnablePointsCache> Base; 383 typedef typename TreeTraits::Point_d Point_d; 384 385 private: 386 387 // private variables for leaf nodes 388 boost::int32_t n; // denotes number of items in a leaf node 389 iterator data; // iterator to data in leaf node 390 391 392 public: 393 394 // default constructor Kd_tree_leaf_node()395 Kd_tree_leaf_node() 396 : Base(true) 397 {} 398 Kd_tree_leaf_node(unsigned int n_)399 Kd_tree_leaf_node(unsigned int n_ ) 400 : Base(true), n(n_) 401 {} 402 403 // members for all nodes 404 405 // members for leaf nodes only 406 inline 407 unsigned int size()408 size() const 409 { 410 return n; 411 } 412 413 inline 414 iterator begin()415 begin() const 416 { 417 return data; 418 } 419 420 inline 421 iterator end()422 end() const 423 { 424 return data + n; 425 } 426 427 inline 428 void drop_last_point()429 drop_last_point() 430 { 431 --n; 432 } 433 434 }; //leaf node 435 436 437 438 template < class TreeTraits, class Splitter, class UseExtendedNode, class EnablePointsCache> 439 class Kd_tree_internal_node : public Kd_tree_node< TreeTraits, Splitter, UseExtendedNode, EnablePointsCache >{ 440 441 friend class Kd_tree<TreeTraits, Splitter, UseExtendedNode, EnablePointsCache>; 442 443 typedef Kd_tree<TreeTraits, Splitter, UseExtendedNode, EnablePointsCache> Kdt; 444 445 typedef Kd_tree_node< TreeTraits, Splitter, UseExtendedNode, EnablePointsCache> Base; 446 typedef typename Kdt::Node_handle Node_handle; 447 typedef typename Kdt::Node_const_handle Node_const_handle; 448 449 typedef typename TreeTraits::FT FT; 450 typedef typename Kdt::Separator Separator; 451 typedef typename Kdt::D D; 452 453 private: 454 455 // private variables for internal nodes 456 boost::int32_t cut_dim; 457 FT cut_val; 458 Node_handle lower_ch, upper_ch; 459 460 461 // private variables for extended internal nodes 462 FT upper_low_val; 463 FT upper_high_val; 464 FT lower_low_val; 465 FT lower_high_val; 466 467 468 public: 469 470 // default constructor Kd_tree_internal_node()471 Kd_tree_internal_node() 472 : Base(false), cut_dim(-1), cut_val(0) 473 , lower_ch (nullptr), upper_ch (nullptr) 474 , upper_low_val(0), upper_high_val(0) 475 , lower_low_val(0), lower_high_val(0) 476 {} 477 478 // members for internal node and extended internal node 479 480 inline 481 Node_const_handle lower()482 lower() const 483 { 484 return lower_ch; 485 } 486 487 inline 488 Node_const_handle upper()489 upper() const 490 { 491 return upper_ch; 492 } 493 494 inline 495 Node_handle lower()496 lower() 497 { 498 return lower_ch; 499 } 500 501 inline 502 Node_handle upper()503 upper() 504 { 505 return upper_ch; 506 } 507 508 inline 509 void set_lower(Node_handle nh)510 set_lower(Node_handle nh) 511 { 512 lower_ch = nh; 513 } 514 515 inline 516 void set_upper(Node_handle nh)517 set_upper(Node_handle nh) 518 { 519 upper_ch = nh; 520 } 521 522 // inline Separator& separator() {return sep; } 523 // use instead 524 inline set_separator(Separator & sep)525 void set_separator(Separator& sep){ 526 cut_dim = sep.cutting_dimension(); 527 cut_val = sep.cutting_value(); 528 } 529 530 inline 531 FT cutting_value()532 cutting_value() const 533 { 534 return cut_val; 535 } 536 537 inline 538 int cutting_dimension()539 cutting_dimension() const 540 { 541 return cut_dim; 542 } 543 544 // members for extended internal node only 545 inline 546 FT upper_low_value()547 upper_low_value() const 548 { 549 return upper_low_val; 550 } 551 552 inline 553 FT upper_high_value()554 upper_high_value() const 555 { 556 return upper_high_val; 557 } 558 559 inline 560 FT lower_low_value()561 lower_low_value() const 562 { 563 return lower_low_val; 564 } 565 566 inline 567 FT lower_high_value()568 lower_high_value() const 569 { 570 return lower_high_val; 571 } 572 573 /*Separator& 574 separator() 575 { 576 return Separator(cutting_dimension,cutting_value); 577 }*/ 578 split_bbox(Kd_tree_rectangle<FT,D> & l,Kd_tree_rectangle<FT,D> & u)579 void split_bbox(Kd_tree_rectangle<FT,D>& l, Kd_tree_rectangle<FT,D>& u) const { 580 l.lower()[cut_dim]=lower_low_val; 581 l.upper()[cut_dim]=lower_high_val; 582 u.lower()[cut_dim]=upper_low_val; 583 u.upper()[cut_dim]=upper_high_val; 584 } 585 };//internal node 586 587 template < class TreeTraits, class Splitter, class EnablePointsCache> 588 class Kd_tree_internal_node<TreeTraits,Splitter,Tag_false,EnablePointsCache> 589 : public Kd_tree_node< TreeTraits, Splitter, Tag_false, EnablePointsCache > 590 { 591 friend class Kd_tree<TreeTraits, Splitter, Tag_false, EnablePointsCache>; 592 593 typedef Kd_tree<TreeTraits, Splitter, Tag_false, EnablePointsCache> Kdt; 594 595 typedef Kd_tree_node< TreeTraits, Splitter, Tag_false, EnablePointsCache> Base; 596 typedef typename Kdt::Node_handle Node_handle; 597 typedef typename Kdt::Node_const_handle Node_const_handle; 598 599 typedef typename TreeTraits::FT FT; 600 typedef typename Kdt::Separator Separator; 601 typedef typename Kdt::D D; 602 603 private: 604 605 // private variables for internal nodes 606 boost::uint8_t cut_dim; 607 FT cut_val; 608 609 Node_handle lower_ch, upper_ch; 610 611 public: 612 613 // default constructor Kd_tree_internal_node()614 Kd_tree_internal_node() 615 : Base(false) 616 {} 617 618 // members for internal node and extended internal node 619 620 inline 621 Node_const_handle lower()622 lower() const 623 { 624 return lower_ch; 625 } 626 627 inline 628 Node_const_handle upper()629 upper() const 630 { 631 return upper_ch; 632 } 633 634 inline 635 Node_handle lower()636 lower() 637 { 638 return lower_ch; 639 } 640 641 inline 642 Node_handle upper()643 upper() 644 { 645 return upper_ch; 646 } 647 648 inline 649 void set_lower(Node_handle nh)650 set_lower(Node_handle nh) 651 { 652 lower_ch = nh; 653 } 654 655 inline 656 void set_upper(Node_handle nh)657 set_upper(Node_handle nh) 658 { 659 upper_ch = nh; 660 } 661 662 // inline Separator& separator() {return sep; } 663 // use instead 664 665 inline set_separator(Separator & sep)666 void set_separator(Separator& sep){ 667 cut_dim = static_cast<boost::uint8_t>(sep.cutting_dimension()); 668 cut_val = sep.cutting_value(); 669 } 670 671 inline 672 FT cutting_value()673 cutting_value() const 674 { 675 return cut_val; 676 } 677 678 inline 679 int cutting_dimension()680 cutting_dimension() const 681 { 682 return cut_dim; 683 } 684 685 /* Separator& 686 separator() 687 { 688 return Separator(cutting_dimension,cutting_value); 689 }*/ 690 split_bbox(Kd_tree_rectangle<FT,D> & l,Kd_tree_rectangle<FT,D> & u)691 void split_bbox(Kd_tree_rectangle<FT,D>& l, Kd_tree_rectangle<FT,D>& u) const { 692 l.upper()[cut_dim]=cut_val; 693 u.lower()[cut_dim]=cut_val; 694 } 695 };//internal node 696 697 698 699 } // namespace CGAL 700 #endif // CGAL_KDTREE_NODE_H 701