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