PCL
QuadTree.h
Go to the documentation of this file.
1 // ____ ______ __
2 // / __ \ / ____// /
3 // / /_/ // / / /
4 // / ____// /___ / /___ PixInsight Class Library
5 // /_/ \____//_____/ PCL 2.6.11
6 // ----------------------------------------------------------------------------
7 // pcl/QuadTree.h - Released 2024-05-07T15:27:32Z
8 // ----------------------------------------------------------------------------
9 // This file is part of the PixInsight Class Library (PCL).
10 // PCL is a multiplatform C++ framework for development of PixInsight modules.
11 //
12 // Copyright (c) 2003-2024 Pleiades Astrophoto S.L. All Rights Reserved.
13 //
14 // Redistribution and use in both source and binary forms, with or without
15 // modification, is permitted provided that the following conditions are met:
16 //
17 // 1. All redistributions of source code must retain the above copyright
18 // notice, this list of conditions and the following disclaimer.
19 //
20 // 2. All redistributions in binary form must reproduce the above copyright
21 // notice, this list of conditions and the following disclaimer in the
22 // documentation and/or other materials provided with the distribution.
23 //
24 // 3. Neither the names "PixInsight" and "Pleiades Astrophoto", nor the names
25 // of their contributors, may be used to endorse or promote products derived
26 // from this software without specific prior written permission. For written
27 // permission, please contact info@pixinsight.com.
28 //
29 // 4. All products derived from this software, in any form whatsoever, must
30 // reproduce the following acknowledgment in the end-user documentation
31 // and/or other materials provided with the product:
32 //
33 // "This product is based on software from the PixInsight project, developed
34 // by Pleiades Astrophoto and its contributors (https://pixinsight.com/)."
35 //
36 // Alternatively, if that is where third-party acknowledgments normally
37 // appear, this acknowledgment must be reproduced in the product itself.
38 //
39 // THIS SOFTWARE IS PROVIDED BY PLEIADES ASTROPHOTO AND ITS CONTRIBUTORS
40 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
41 // TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL PLEIADES ASTROPHOTO OR ITS
43 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
44 // EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, BUSINESS
45 // INTERRUPTION; PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; AND LOSS OF USE,
46 // DATA OR PROFITS) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
47 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
48 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
49 // POSSIBILITY OF SUCH DAMAGE.
50 // ----------------------------------------------------------------------------
51 
52 #ifndef __PCL_QuadTree_h
53 #define __PCL_QuadTree_h
54 
56 
57 #include <pcl/Defs.h>
58 
59 #include <pcl/Array.h>
60 #include <pcl/Rectangle.h>
61 #include <pcl/Vector.h>
62 
63 namespace pcl
64 {
65 
66 // ----------------------------------------------------------------------------
67 
68 /*
69  * Default bucket capacity for point region quadtree generation.
70  */
71 #define __PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY 40
72 
73 /*
74  * Default minimum allowed dimension of a quadtree node region.
75  */
76 #define __PCL_QUADTREE_DEFAULT_EPSILON 1.0e-08
77 
78 // ----------------------------------------------------------------------------
79 
122 template <class T>
123 class QuadTree
124 {
125 public:
126 
130  using point = T;
131 
135  using component = typename point::component;
136 
141 
145  using rectangle = DRect;
146 
151 
152  // -------------------------------------------------------------------------
153 
158  struct Node
159  {
160  rectangle rect = 0.0;
161  Node* nw = nullptr;
162  Node* ne = nullptr;
163  Node* sw = nullptr;
164  Node* se = nullptr;
165 
166 #ifdef __PCL_QUADTREE_STRUCTURAL_NODE_HAS_DATA
167  void* data = nullptr;
168 #endif
169 
173  Node() = default;
174 
178  Node( const rectangle& r )
179  : rect( r )
180  {
181  }
182 
192  bool IsLeaf() const
193  {
194  return nw == nullptr && ne == nullptr && sw == nullptr && se == nullptr;
195  }
196 
201  bool Intersects( const rectangle& r ) const
202  {
203  return rect.x1 >= r.x0 && rect.x0 <= r.x1 &&
204  rect.y1 >= r.y0 && rect.y0 <= r.y1;
205  }
206 
211  bool Includes( coordinate x, coordinate y ) const
212  {
213  return x >= rect.x0 && x <= rect.x1 &&
214  y >= rect.y0 && y <= rect.y1;
215  }
216 
221  bool Includes( const rectangle::point& p ) const
222  {
223  return Includes( p.x, p.y );
224  }
225 
230  {
231  return rectangle( rect.TopLeft(), rect.Center() );
232  }
233 
238  {
239  return rectangle( rect.CenterTop(), rect.CenterRight() );
240  }
241 
246  {
247  return rectangle( rect.CenterLeft(), rect.CenterBottom() );
248  }
249 
255  {
256  return rectangle( rect.Center(), rect.BottomRight() );
257  }
258  };
259 
260  // -------------------------------------------------------------------------
261 
266  struct LeafNode : public Node
267  {
276 
277 #ifndef __PCL_QUADTREE_STRUCTURAL_NODE_HAS_DATA
278 
287  void* data = nullptr;
288 
289 #endif
290 
295  LeafNode( const rectangle& r, const point_list& p )
296  : Node( r )
297  , points( p )
298  {
299  PCL_CHECK( !points.IsEmpty() )
300  }
301 
306  LeafNode( const rectangle& r, const point& p )
307  : Node( r )
308  {
309  points << p;
310  }
311 
316  int Length() const
317  {
318  return int( points.Length() );
319  }
320  };
321 
322  // -------------------------------------------------------------------------
323 
327  QuadTree() = default;
328 
346  QuadTree( const point_list& points,
347  int bucketCapacity = __PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY,
348  double epsilon = __PCL_QUADTREE_DEFAULT_EPSILON )
349  {
350  Build( points, bucketCapacity, epsilon );
351  }
352 
373  QuadTree( const rectangle& rect, const point_list& points,
374  int bucketCapacity = __PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY,
375  double epsilon = __PCL_QUADTREE_DEFAULT_EPSILON )
376  {
377  Build( rect, points, bucketCapacity, epsilon );
378  }
379 
385  QuadTree( const QuadTree& ) = delete;
386 
392  QuadTree& operator =( const QuadTree& ) = delete;
393 
398  : m_root( x.m_root )
399  , m_bucketCapacity( x.m_bucketCapacity )
400  , m_epsilon( x.m_epsilon )
401  , m_length( x.m_length )
402  {
403  x.m_root = nullptr;
404  x.m_length = 0;
405  }
406 
411  {
412  if ( &x != this )
413  {
414  DestroyTree( m_root );
415  m_root = x.m_root;
416  m_bucketCapacity = x.m_bucketCapacity;
417  m_epsilon = x.m_epsilon;
418  m_length = x.m_length;
419  x.m_root = nullptr;
420  x.m_length = 0;
421  }
422  return *this;
423  }
424 
429  {
430  Clear();
431  }
432 
436  void Clear()
437  {
438  DestroyTree( m_root );
439  m_root = nullptr;
440  m_length = 0;
441  }
442 
463  void Build( const point_list& points,
464  int bucketCapacity = __PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY,
465  double epsilon = __PCL_QUADTREE_DEFAULT_EPSILON )
466  {
467  Clear();
468  m_bucketCapacity = Max( 1, bucketCapacity );
469  m_epsilon = Max( 2*std::numeric_limits<coordinate>::epsilon(), epsilon );
470 
471  if ( !points.IsEmpty() )
472  {
473  component x = points[0][0];
474  component y = points[0][1];
475  rectangle rect( x, y, x, y );
476  for ( const point& p : points )
477  {
478  x = p[0];
479  y = p[1];
480  if ( x < rect.x0 )
481  rect.x0 = x;
482  if ( y < rect.y0 )
483  rect.y0 = y;
484  if ( x > rect.x1 )
485  rect.x1 = x;
486  if ( y > rect.y1 )
487  rect.y1 = y;
488  }
489  m_root = BuildTree( rect, points );
490  }
491  }
492 
518  void Build( const rectangle& rect, const point_list& points,
519  int bucketCapacity = __PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY,
520  double epsilon = __PCL_QUADTREE_DEFAULT_EPSILON )
521  {
522  Clear();
523  m_bucketCapacity = Max( 1, bucketCapacity );
524  m_epsilon = Max( 2*std::numeric_limits<coordinate>::epsilon(), epsilon );
525  if ( !points.IsEmpty() )
526  m_root = BuildTree( rect.Ordered(), points );
527  }
528 
537  point_list Search( const rectangle& rect ) const
538  {
539  point_list found;
540  SearchTree( found, rect.Ordered(), m_root );
541  return found;
542  }
543 
560  template <class F>
561  void Search( const rectangle& rect, F callback, void* data ) const
562  {
563  SearchTree( rect.Ordered(), callback, data, m_root );
564  }
565 
569  void Insert( const point& pt )
570  {
571  if ( m_root != nullptr )
572  InsertTree( pt, m_root );
573  else
574  {
575  component x = pt[0];
576  component y = pt[1];
577  m_root = new LeafNode( rectangle( x, y, x, y ), pt );
578  }
579  }
580 
584  void Delete( const point& pt )
585  {
586  DeleteTree( pt, m_root );
587  }
588 
593  void Delete( const rectangle& rect )
594  {
595  DeleteTree( rect.Ordered(), m_root );
596  }
597 
603  int BucketCapacity() const
604  {
605  return m_bucketCapacity;
606  }
607 
612  {
613  return m_length;
614  }
615 
619  bool IsEmpty() const
620  {
621  return m_root == nullptr;
622  }
623 
631  const Node* Root() const
632  {
633  return m_root;
634  }
635 
641  {
642  return m_root;
643  }
644 
651  {
652  return SearchLeafNode( p, m_root );
653  }
654 
661  {
662  return SearchLeafNode( p, m_root );
663  }
664 
674  const Node* NodeAt( rectangle::point p ) const
675  {
676  return SearchNode( p, m_root );
677  }
678 
689  {
690  return SearchNode( p, m_root );
691  }
692 
704  {
705  Node* node = SearchDeepestStructuralNodeAt( p, m_root );
706  if ( node != nullptr )
707  {
708  Node** leaf = nullptr;
709  if ( node->nw != nullptr && node->nw->Includes( p ) )
710  leaf = &node->nw;
711  else if ( node->ne != nullptr && node->ne->Includes( p ) )
712  leaf = &node->ne;
713  else if ( node->sw != nullptr && node->sw->Includes( p ) )
714  leaf = &node->sw;
715  else if ( node->se != nullptr && node->se->Includes( p ) )
716  leaf = &node->se;
717 
718  if ( leaf != nullptr ) // cannot be false!
719  {
720  Node* newNode = SplitLeafNode( *leaf );
721  if ( newNode != nullptr ) // should be true
722  {
723  delete static_cast<LeafNode*>( *leaf );
724  *leaf = newNode;
725  }
726  return newNode;
727  }
728  }
729 
730  return nullptr;
731  }
732 
752  template <class F>
753  static void Traverse( const Node* node, F f )
754  {
755  if ( node != nullptr )
756  if ( node->IsLeaf() )
757  f( node->rect,
758  static_cast<const LeafNode*>( node )->points,
759  static_cast<const LeafNode*>( node )->data );
760  else
761  {
762  Traverse( node->nw, f );
763  Traverse( node->ne, f );
764  Traverse( node->sw, f );
765  Traverse( node->se, f );
766  }
767  }
768 
788  template <class F>
789  static void Traverse( Node* node, F f )
790  {
791  if ( node != nullptr )
792  if ( node->IsLeaf() )
793  f( node->rect, static_cast<LeafNode*>( node )->points,
794  static_cast<LeafNode*>( node )->data );
795  else
796  {
797  Traverse( node->nw, f );
798  Traverse( node->ne, f );
799  Traverse( node->sw, f );
800  Traverse( node->se, f );
801  }
802  }
803 
813  template <class F>
814  void Traverse( F f ) const
815  {
816  Traverse( m_root, f );
817  }
818 
828  template <class F>
829  void Traverse( F f )
830  {
831  Traverse( m_root, f );
832  }
833 
838  static size_type NumberOfNodes( const Node* node )
839  {
840  size_type N = 0;
841  GetNumberOfNodes( N, node );
842  return N;
843  }
844 
850  {
851  return NumberOfNodes( m_root );
852  }
853 
858  static size_type NumberOfLeafNodes( const Node* node )
859  {
860  size_type N = 0;
861  GetNumberOfLeafNodes( N, node );
862  return N;
863  }
864 
869  {
870  return NumberOfLeafNodes( m_root );
871  }
872 
876  static int Height( const Node* node )
877  {
878  return TreeHeight( node, 0 );
879  }
880 
884  int Height() const
885  {
886  return Height( m_root );
887  }
888 
892  friend void Swap( QuadTree& x1, QuadTree& x2 )
893  {
894  pcl::Swap( x1.m_root, x2.m_root );
895  pcl::Swap( x1.m_bucketCapacity, x2.m_bucketCapacity );
896  pcl::Swap( x1.m_epsilon, x2.m_epsilon );
897  pcl::Swap( x1.m_length, x2.m_length );
898  }
899 
900 private:
901 
902  Node* m_root = nullptr;
903  int m_bucketCapacity = 0;
904  double m_epsilon = 0;
905  size_type m_length = 0;
906 
907  Node* NewLeafNode( const rectangle& rect, const point_list& points )
908  {
909  m_length += points.Length();
910  return new LeafNode( rect, points );
911  }
912 
913  LeafNode* SearchLeafNode( const rectangle::point& p, const Node* node ) const
914  {
915  if ( node != nullptr )
916  if ( node->Includes( p ) )
917  {
918  if ( node->IsLeaf() )
919  return const_cast<LeafNode*>( static_cast<const LeafNode*>( node ) );
920 
921  LeafNode* child = SearchLeafNode( p, node->nw );
922  if ( child == nullptr )
923  {
924  child = SearchLeafNode( p, node->ne );
925  if ( child == nullptr )
926  {
927  child = SearchLeafNode( p, node->sw );
928  if ( child == nullptr )
929  child = SearchLeafNode( p, node->se );
930  }
931  }
932  return child;
933  }
934 
935  return nullptr;
936  }
937 
938  Node* SearchNode( const rectangle::point& p, const Node* node ) const
939  {
940  if ( node != nullptr )
941  if ( node->Includes( p ) )
942  {
943  if ( node->IsLeaf() )
944  return const_cast<Node*>( node );
945 
946  Node* child = SearchNode( p, node->nw );
947  if ( child == nullptr )
948  {
949  child = SearchNode( p, node->ne );
950  if ( child == nullptr )
951  {
952  child = SearchNode( p, node->sw );
953  if ( child == nullptr )
954  {
955  child = SearchNode( p, node->se );
956  if ( child == nullptr )
957  return const_cast<Node*>( node );
958  }
959  }
960  }
961  return child;
962  }
963 
964  return nullptr;
965  }
966 
967  Node* SearchDeepestStructuralNodeAt( const rectangle::point& p, const Node* node ) const
968  {
969  if ( node != nullptr )
970  if ( !node->IsLeaf() )
971  if ( node->Includes( p ) )
972  {
973  Node* child = SearchDeepestStructuralNodeAt( p, node->nw );
974  if ( child == nullptr )
975  {
976  child = SearchDeepestStructuralNodeAt( p, node->ne );
977  if ( child == nullptr )
978  {
979  child = SearchDeepestStructuralNodeAt( p, node->sw );
980  if ( child == nullptr )
981  {
982  child = SearchDeepestStructuralNodeAt( p, node->se );
983  if ( child == nullptr )
984  return const_cast<Node*>( node );
985  }
986  }
987  }
988  return child;
989  }
990 
991  return nullptr;
992  }
993 
994  Node* BuildTree( const rectangle& rect, const point_list& points )
995  {
996  if ( points.IsEmpty() )
997  return nullptr;
998 
999  if ( points.Length() <= size_type( m_bucketCapacity ) )
1000  return NewLeafNode( rect, points );
1001 
1002  double x2 = (rect.x0 + rect.x1)/2;
1003  double y2 = (rect.y0 + rect.y1)/2;
1004  // Prevent geometrically degenerate subtrees. For safety, we enforce
1005  // minimum region dimensions larger than twice the machine epsilon for
1006  // the rectangle coordinate type.
1007  if ( x2 - rect.x0 < m_epsilon || rect.x1 - x2 < m_epsilon ||
1008  y2 - rect.y0 < m_epsilon || rect.y1 - y2 < m_epsilon )
1009  {
1010  return NewLeafNode( rect, points );
1011  }
1012 
1013  point_list nw, ne, sw, se;
1014  for ( const point& p : points )
1015  {
1016  component x = p[0];
1017  component y = p[1];
1018  if ( x <= x2 )
1019  {
1020  if ( y <= y2 )
1021  nw << p;
1022  else
1023  sw << p;
1024  }
1025  else
1026  {
1027  if ( y <= y2 )
1028  ne << p;
1029  else
1030  se << p;
1031  }
1032  }
1033 
1034  Node* node = new Node( rect );
1035  node->nw = BuildTree( rectangle( rect.x0, rect.y0, x2, y2 ), nw );
1036  node->ne = BuildTree( rectangle( x2, rect.y0, rect.x1, y2 ), ne );
1037  node->sw = BuildTree( rectangle( rect.x0, y2, x2, rect.y1 ), sw );
1038  node->se = BuildTree( rectangle( x2, y2, rect.x1, rect.y1 ), se );
1039 
1040  // Further degeneracies may result, e.g. if the point class is not
1041  // behaving as expected. Do not allow them.
1042  if ( node->IsLeaf() )
1043  {
1044  delete node;
1045  return NewLeafNode( rect, points );
1046  }
1047 
1048  return node;
1049  }
1050 
1051  Node* SplitLeafNode( const Node* node )
1052  {
1053  if ( node == nullptr || !node->IsLeaf() )
1054  return nullptr;
1055 
1056  double x2 = (node->rect.x0 + node->rect.x1)/2;
1057  double y2 = (node->rect.y0 + node->rect.y1)/2;
1058  // Prevent geometrically degenerate subtrees. For safety, we enforce
1059  // minimum region dimensions larger than twice the machine epsilon for
1060  // the rectangle coordinate type.
1061  if ( x2 - node->rect.x0 < m_epsilon || node->rect.x1 - x2 < m_epsilon ||
1062  y2 - node->rect.y0 < m_epsilon || node->rect.y1 - y2 < m_epsilon )
1063  {
1064  return nullptr;
1065  }
1066 
1067  const LeafNode* leaf = static_cast<const LeafNode*>( node );
1068  point_list nw, ne, sw, se;
1069  for ( const point& p : leaf->points )
1070  {
1071  component x = p[0];
1072  component y = p[1];
1073  if ( x <= x2 )
1074  {
1075  if ( y <= y2 )
1076  nw << p;
1077  else
1078  sw << p;
1079  }
1080  else
1081  {
1082  if ( y <= y2 )
1083  ne << p;
1084  else
1085  se << p;
1086  }
1087  }
1088 
1089  size_type savedLength = m_length;
1090  Node* newNode = new Node( node->rect );
1091  newNode->nw = BuildTree( rectangle( node->rect.x0, node->rect.y0, x2, y2 ), nw );
1092  newNode->ne = BuildTree( rectangle( x2, node->rect.y0, node->rect.x1, y2 ), ne );
1093  newNode->sw = BuildTree( rectangle( node->rect.x0, y2, x2, node->rect.y1 ), sw );
1094  newNode->se = BuildTree( rectangle( x2, y2, node->rect.x1, node->rect.y1 ), se );
1095  m_length = savedLength;
1096 
1097  // Further degeneracies may result, e.g. if the point class is not
1098  // behaving as expected. Do not allow them.
1099  if ( newNode->IsLeaf() )
1100  {
1101  delete newNode;
1102  return nullptr;
1103  }
1104 
1105  return newNode;
1106  }
1107 
1108  void SearchTree( point_list& found, const rectangle& rect, const Node* node ) const
1109  {
1110  if ( node != nullptr )
1111  if ( node->Intersects( rect ) )
1112  if ( node->IsLeaf() )
1113  {
1114  const LeafNode* leaf = static_cast<const LeafNode*>( node );
1115  for ( const point& p : leaf->points )
1116  {
1117  component x = p[0];
1118  if ( x >= rect.x0 )
1119  if ( x <= rect.x1 )
1120  {
1121  component y = p[1];
1122  if ( y >= rect.y0 )
1123  if ( y <= rect.y1 )
1124  found << p;
1125  }
1126  }
1127  }
1128  else
1129  {
1130  SearchTree( found, rect, node->nw );
1131  SearchTree( found, rect, node->ne );
1132  SearchTree( found, rect, node->sw );
1133  SearchTree( found, rect, node->se );
1134  }
1135  }
1136 
1137  template <class F>
1138  void SearchTree( const rectangle& rect, F callback, void* data, const Node* node ) const
1139  {
1140  if ( node != nullptr )
1141  if ( node->Intersects( rect ) )
1142  if ( node->IsLeaf() )
1143  {
1144  const LeafNode* leaf = static_cast<const LeafNode*>( node );
1145  for ( const point& p : leaf->points )
1146  {
1147  component x = p[0];
1148  if ( x >= rect.x0 )
1149  if ( x <= rect.x1 )
1150  {
1151  component y = p[1];
1152  if ( y >= rect.y0 )
1153  if ( y <= rect.y1 )
1154  callback( p, data );
1155  }
1156  }
1157  }
1158  else
1159  {
1160  SearchTree( rect, callback, data, node->nw );
1161  SearchTree( rect, callback, data, node->ne );
1162  SearchTree( rect, callback, data, node->sw );
1163  SearchTree( rect, callback, data, node->se );
1164  }
1165  }
1166 
1167  void InsertTree( const point& pt, Node*& node )
1168  {
1169  PCL_CHECK( node != nullptr )
1170 
1171  component x = pt[0];
1172  component y = pt[1];
1173 
1174  if ( x < node->rect.x0 )
1175  node->rect.x0 = x;
1176  else if ( x > node->rect.x1 )
1177  node->rect.x1 = x;
1178 
1179  if ( y < node->rect.y0 )
1180  node->rect.y0 = y;
1181  else if ( y > node->rect.y1 )
1182  node->rect.y1 = y;
1183 
1184  if ( node->IsLeaf() )
1185  {
1186  LeafNode* leaf = static_cast<LeafNode*>( node );
1187  if ( leaf->Length() < m_bucketCapacity )
1188  leaf->points << pt;
1189  else
1190  {
1191  rectangle rect = leaf->rect;
1192  double x2 = (rect.x0 + rect.x1)/2;
1193  double y2 = (rect.y0 + rect.y1)/2;
1194  // Prevent geometrically degenerate subtrees. For safety, we
1195  // enforce minimum region dimensions larger than twice the
1196  // machine epsilon for the rectangle coordinate type.
1197  if ( x2 - rect.x0 < m_epsilon || rect.x1 - x2 < m_epsilon ||
1198  y2 - rect.y0 < m_epsilon || rect.y1 - y2 < m_epsilon )
1199  {
1200  leaf->points << pt;
1201  }
1202  else
1203  {
1204  point_list nw, ne, sw, se;
1205  for ( const point& p : leaf->points )
1206  {
1207  component x = p[0];
1208  component y = p[1];
1209  if ( x <= x2 )
1210  {
1211  if ( y <= y2 )
1212  nw << p;
1213  else
1214  sw << p;
1215  }
1216  else
1217  {
1218  if ( y <= y2 )
1219  ne << p;
1220  else
1221  se << p;
1222  }
1223  }
1224 
1225  if ( x <= x2 )
1226  {
1227  if ( y <= y2 )
1228  nw << pt;
1229  else
1230  sw << pt;
1231  }
1232  else
1233  {
1234  if ( y <= y2 )
1235  ne << pt;
1236  else
1237  se << pt;
1238  }
1239 
1240  delete leaf;
1241 
1242  node = new Node( rect );
1243 
1244  if ( !nw.IsEmpty() )
1245  node->nw = new LeafNode( rectangle( rect.x0, rect.y0, x2, y2 ), nw );
1246  if ( !ne.IsEmpty() )
1247  node->ne = new LeafNode( rectangle( x2, rect.y0, rect.x1, y2 ), ne );
1248  if ( !sw.IsEmpty() )
1249  node->sw = new LeafNode( rectangle( rect.x0, y2, x2, rect.y1 ), sw );
1250  if ( !se.IsEmpty() )
1251  node->se = new LeafNode( rectangle( x2, y2, rect.x1, rect.y1 ), se );
1252  }
1253  }
1254 
1255  ++m_length;
1256  }
1257  else
1258  {
1259  rectangle rect = node->rect;
1260  double x2 = (rect.x0 + rect.x1)/2;
1261  double y2 = (rect.y0 + rect.y1)/2;
1262  if ( pt[0] <= x2 )
1263  {
1264  if ( pt[1] <= y2 )
1265  {
1266  if ( node->nw == nullptr )
1267  node->nw = new LeafNode( rectangle( rect.x0, rect.y0, x2, y2 ), pt );
1268  else
1269  InsertTree( pt, node->nw );
1270  }
1271  else
1272  {
1273  if ( node->sw == nullptr )
1274  node->sw = new LeafNode( rectangle( rect.x0, y2, x2, rect.y1 ), pt );
1275  else
1276  InsertTree( pt, node->sw );
1277  }
1278  }
1279  else
1280  {
1281  if ( pt[1] <= y2 )
1282  {
1283  if ( node->ne == nullptr )
1284  node->ne = new LeafNode( rectangle( x2, rect.y0, rect.x1, y2 ), pt );
1285  else
1286  InsertTree( pt, node->ne );
1287  }
1288  else
1289  {
1290  if ( node->se == nullptr )
1291  node->se = new LeafNode( rectangle( x2, y2, rect.x1, rect.y1 ), pt );
1292  else
1293  InsertTree( pt, node->se );
1294  }
1295  }
1296  }
1297  }
1298 
1299  void DeleteTree( const rectangle& rect, Node*& node )
1300  {
1301  if ( node != nullptr )
1302  if ( node->Intersects( rect ) )
1303  {
1304  if ( node->IsLeaf() )
1305  {
1306  LeafNode* leaf = static_cast<LeafNode*>( node );
1307  point_list points;
1308  for ( const point& p : leaf->points )
1309  {
1310  component x = p[0];
1311  if ( x >= rect.x0 )
1312  if ( x <= rect.x1 )
1313  {
1314  component y = p[1];
1315  if ( y >= rect.y0 )
1316  if ( y <= rect.y1 )
1317  {
1318  --m_length;
1319  continue;
1320  }
1321  }
1322  points << p;
1323  }
1324 
1325  if ( points.IsEmpty() )
1326  {
1327  delete leaf;
1328  node = nullptr;
1329  }
1330  else
1331  leaf->points = points;
1332  }
1333  else
1334  {
1335  DeleteTree( rect, node->nw );
1336  DeleteTree( rect, node->ne );
1337  DeleteTree( rect, node->sw );
1338  DeleteTree( rect, node->se );
1339 
1340  if ( node->IsLeaf() )
1341  {
1342  delete node;
1343  node = nullptr;
1344  }
1345  }
1346  }
1347  }
1348 
1349  void DeleteTree( const point& pt, Node*& node )
1350  {
1351  if ( node != nullptr )
1352  {
1353  component x = pt[0];
1354  component y = pt[1];
1355  if ( node->Includes( x, y ) )
1356  if ( node->IsLeaf() )
1357  {
1358  LeafNode* leaf = static_cast<LeafNode*>( node );
1359  point_list points;
1360  for ( const point& p : leaf->points )
1361  {
1362  if ( p[0] == x )
1363  if ( p[1] == y )
1364  {
1365  --m_length;
1366  continue;
1367  }
1368  points << p;
1369  }
1370 
1371  if ( points.IsEmpty() )
1372  {
1373  delete leaf;
1374  node = nullptr;
1375  }
1376  else
1377  leaf->points = points;
1378  }
1379  else
1380  {
1381  DeleteTree( pt, node->nw );
1382  DeleteTree( pt, node->ne );
1383  DeleteTree( pt, node->sw );
1384  DeleteTree( pt, node->se );
1385 
1386  if ( node->IsLeaf() )
1387  {
1388  delete node;
1389  node = nullptr;
1390  }
1391  }
1392  }
1393  }
1394 
1395  void DestroyTree( Node* node )
1396  {
1397  if ( node != nullptr )
1398  if ( node->IsLeaf() )
1399  delete static_cast<LeafNode*>( node );
1400  else
1401  {
1402  DestroyTree( node->nw );
1403  DestroyTree( node->ne );
1404  DestroyTree( node->sw );
1405  DestroyTree( node->se );
1406  delete node;
1407  }
1408  }
1409 
1410  static void GetNumberOfNodes( size_type& N, const Node* node )
1411  {
1412  if ( node != nullptr )
1413  {
1414  ++N;
1415  GetNumberOfNodes( N, node->nw );
1416  GetNumberOfNodes( N, node->ne );
1417  GetNumberOfNodes( N, node->sw );
1418  GetNumberOfNodes( N, node->se );
1419  }
1420  }
1421 
1422  static void GetNumberOfLeafNodes( size_type& N, const Node* node )
1423  {
1424  if ( node != nullptr )
1425  {
1426  if ( node->IsLeaf() )
1427  ++N;
1428  GetNumberOfLeafNodes( N, node->nw );
1429  GetNumberOfLeafNodes( N, node->ne );
1430  GetNumberOfLeafNodes( N, node->sw );
1431  GetNumberOfLeafNodes( N, node->se );
1432  }
1433  }
1434 
1435  static int TreeHeight( const Node* node, int h )
1436  {
1437  if ( node == nullptr )
1438  return h;
1439  return h + 1 + Max( Max( Max( TreeHeight( node->nw, h ),
1440  TreeHeight( node->ne, h ) ),
1441  TreeHeight( node->sw, h ) ),
1442  TreeHeight( node->se, h ) );
1443  }
1444 };
1445 
1446 // ----------------------------------------------------------------------------
1447 
1448 } // pcl
1449 
1450 #endif // __PCL_QuadTree_h
1451 
1452 // ----------------------------------------------------------------------------
1453 // EOF pcl/QuadTree.h - Released 2024-05-07T15:27:32Z
bool IsEmpty() const noexcept
Definition: Array.h:312
size_type Length() const noexcept
Definition: Array.h:266
A generic point in the two-dimensional space.
Definition: Point.h:100
component x
Abscissa (horizontal, or X-axis coordinate).
Definition: Point.h:111
component y
Ordinate (vertical, or Y-axis coordinate).
Definition: Point.h:112
A generic rectangle in the two-dimensional space.
Definition: Rectangle.h:314
point BottomRight() const noexcept
Definition: Rectangle.h:586
component x1
Horizontal coordinate of the lower right corner.
Definition: Rectangle.h:334
point CenterLeft() const noexcept
Definition: Rectangle.h:618
component y1
Vertical coordinate of the lower right corner.
Definition: Rectangle.h:335
point TopLeft() const noexcept
Definition: Rectangle.h:535
point Center() const noexcept
Definition: Rectangle.h:594
point CenterBottom() const noexcept
Definition: Rectangle.h:610
GenericPoint< component > point
Definition: Rectangle.h:325
component y0
Vertical coordinate of the upper left corner.
Definition: Rectangle.h:333
component x0
Horizontal coordinate of the upper left corner.
Definition: Rectangle.h:332
point CenterTop() const noexcept
Definition: Rectangle.h:602
point CenterRight() const noexcept
Definition: Rectangle.h:626
GenericRectangle Ordered() const noexcept
Definition: Rectangle.h:794
Bucket PR quadtree for two-dimensional point data.
Definition: QuadTree.h:124
void Traverse(F f)
Definition: QuadTree.h:829
DRect rectangle
Definition: QuadTree.h:145
QuadTree(const rectangle &rect, const point_list &points, int bucketCapacity=__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY, double epsilon=__PCL_QUADTREE_DEFAULT_EPSILON)
Definition: QuadTree.h:373
const LeafNode * LeafNodeAt(rectangle::point p) const
Definition: QuadTree.h:650
LeafNode * LeafNodeAt(rectangle::point p)
Definition: QuadTree.h:660
QuadTree(const QuadTree &)=delete
size_type NumberOfNodes() const
Definition: QuadTree.h:849
void Clear()
Definition: QuadTree.h:436
size_type NumberOfLeafNodes() const
Definition: QuadTree.h:868
static void Traverse(const Node *node, F f)
Definition: QuadTree.h:753
QuadTree & operator=(const QuadTree &)=delete
Node * Root()
Definition: QuadTree.h:640
const Node * NodeAt(rectangle::point p) const
Definition: QuadTree.h:674
void Delete(const rectangle &rect)
Definition: QuadTree.h:593
friend void Swap(QuadTree &x1, QuadTree &x2)
Definition: QuadTree.h:892
typename point::component component
Definition: QuadTree.h:135
bool IsEmpty() const
Definition: QuadTree.h:619
static int Height(const Node *node)
Definition: QuadTree.h:876
void Search(const rectangle &rect, F callback, void *data) const
Definition: QuadTree.h:561
QuadTree(QuadTree &&x)
Definition: QuadTree.h:397
void Traverse(F f) const
Definition: QuadTree.h:814
void Insert(const point &pt)
Definition: QuadTree.h:569
static size_type NumberOfNodes(const Node *node)
Definition: QuadTree.h:838
rectangle::component coordinate
Definition: QuadTree.h:150
size_type Length() const
Definition: QuadTree.h:611
Array< point > point_list
Definition: QuadTree.h:140
Node * NodeAt(rectangle::point p)
Definition: QuadTree.h:688
int BucketCapacity() const
Definition: QuadTree.h:603
void Build(const rectangle &rect, const point_list &points, int bucketCapacity=__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY, double epsilon=__PCL_QUADTREE_DEFAULT_EPSILON)
Definition: QuadTree.h:518
static void Traverse(Node *node, F f)
Definition: QuadTree.h:789
const Node * Root() const
Definition: QuadTree.h:631
void Delete(const point &pt)
Definition: QuadTree.h:584
Node * SplitAt(rectangle::point p)
Definition: QuadTree.h:703
static size_type NumberOfLeafNodes(const Node *node)
Definition: QuadTree.h:858
QuadTree(const point_list &points, int bucketCapacity=__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY, double epsilon=__PCL_QUADTREE_DEFAULT_EPSILON)
Definition: QuadTree.h:346
int Height() const
Definition: QuadTree.h:884
void Build(const point_list &points, int bucketCapacity=__PCL_QUADTREE_DEFAULT_BUCKET_CAPACITY, double epsilon=__PCL_QUADTREE_DEFAULT_EPSILON)
Definition: QuadTree.h:463
QuadTree()=default
point_list Search(const rectangle &rect) const
Definition: QuadTree.h:537
void Swap(GenericPoint< T > &p1, GenericPoint< T > &p2) noexcept
Definition: Point.h:1459
size_t size_type
Definition: Defs.h:609
constexpr const T & Max(const T &a, const T &b) noexcept
Definition: Utility.h:119
PCL root namespace.
Definition: AbstractImage.h:77
Quadtree leaf node structure.
Definition: QuadTree.h:267
int Length() const
Definition: QuadTree.h:316
LeafNode(const rectangle &r, const point &p)
Definition: QuadTree.h:306
LeafNode(const rectangle &r, const point_list &p)
Definition: QuadTree.h:295
Quadtree node structure.
Definition: QuadTree.h:159
rectangle NERect() const
Definition: QuadTree.h:237
Node(const rectangle &r)
Definition: QuadTree.h:178
rectangle NWRect() const
Definition: QuadTree.h:229
bool Includes(coordinate x, coordinate y) const
Definition: QuadTree.h:211
bool Includes(const rectangle::point &p) const
Definition: QuadTree.h:221
Node * se
South-East child node, representing the bottom-right subregion.
Definition: QuadTree.h:164
Node * ne
North-East child node, representing the top-right subregion.
Definition: QuadTree.h:162
rectangle SERect() const
Definition: QuadTree.h:254
rectangle SWRect() const
Definition: QuadTree.h:245
Node * nw
North-West child node, representing the top-left subregion.
Definition: QuadTree.h:161
rectangle rect
The rectangular region represented by this node.
Definition: QuadTree.h:160
Node * sw
South-West child node, representing the bottom-left subregion.
Definition: QuadTree.h:163
bool Intersects(const rectangle &r) const
Definition: QuadTree.h:201
bool IsLeaf() const
Definition: QuadTree.h:192