PCL
QuadTree.h
Go to the documentation of this file.
1 // ____ ______ __
2 // / __ \ / ____// /
3 // / /_/ // / / /
4 // / ____// /___ / /___ PixInsight Class Library
5 // /_/ \____//_____/ PCL 2.1.19
6 // ----------------------------------------------------------------------------
7 // pcl/QuadTree.h - Released 2019-11-07T10:59:34Z
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-2019 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 (http://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 
110 template <class T>
111 class QuadTree
112 {
113 public:
114 
118  typedef T point;
119 
123  typedef typename point::component component;
124 
129 
133  typedef DRect rectangle;
134 
138  typedef rectangle::component coordinate;
139 
140  // -------------------------------------------------------------------------
141 
146  struct Node
147  {
148  rectangle rect;
149  Node* nw = nullptr;
150  Node* ne = nullptr;
151  Node* sw = nullptr;
152  Node* se = nullptr;
153 
157  Node( const rectangle& r = rectangle( 0.0 ) ) : rect( r )
158  {
159  }
160 
170  bool IsLeaf() const
171  {
172  return nw == nullptr && ne == nullptr && sw == nullptr && se == nullptr;
173  }
174 
179  bool Intersects( const rectangle& r ) const
180  {
181  return rect.x1 >= r.x0 && rect.x0 <= r.x1 &&
182  rect.y1 >= r.y0 && rect.y0 <= r.y1;
183  }
184 
189  bool Includes( coordinate x, coordinate y ) const
190  {
191  return x >= rect.x0 && x <= rect.x1 &&
192  y >= rect.y0 && y <= rect.y1;
193  }
194 
199  bool Includes( const rectangle::point& p ) const
200  {
201  return Includes( p.x, p.y );
202  }
203 
207  rectangle NWRect() const
208  {
209  return rectangle( rect.TopLeft(), rect.Center() );
210  }
211 
215  rectangle NERect() const
216  {
217  return rectangle( rect.CenterTop(), rect.CenterRight() );
218  }
219 
223  rectangle SWRect() const
224  {
225  return rectangle( rect.CenterLeft(), rect.CenterBottom() );
226  }
227 
232  rectangle SERect() const
233  {
234  return rectangle( rect.Center(), rect.BottomRight() );
235  }
236  };
237 
238  // -------------------------------------------------------------------------
239 
244  struct LeafNode : public Node
245  {
253  point_list points;
254 
263  void* data = nullptr;
264 
269  LeafNode( const rectangle& r, const point_list& p ) : Node( r ), points( p )
270  {
271  PCL_CHECK( !points.IsEmpty() )
272  }
273 
278  int Length() const
279  {
280  return int( points.Length() );
281  }
282  };
283 
284  // -------------------------------------------------------------------------
285 
289  QuadTree() = default;
290 
303  QuadTree( const point_list& points, int bucketCapacity = 40 )
304  {
305  Build( points, bucketCapacity );
306  }
307 
323  QuadTree( const rectangle& rect, const point_list& points, int bucketCapacity = 40 )
324  {
325  Build( rect, points, bucketCapacity );
326  }
327 
333  QuadTree( const QuadTree& ) = delete;
334 
340  QuadTree& operator =( const QuadTree& ) = delete;
341 
346  m_root( x.m_root ), m_bucketCapacity( x.m_bucketCapacity ), m_length( x.m_length )
347  {
348  x.m_root = nullptr;
349  x.m_length = 0;
350  }
351 
356  {
357  if ( &x != this )
358  {
359  DestroyTree( m_root );
360  m_root = x.m_root;
361  m_bucketCapacity = x.m_bucketCapacity;
362  m_length = x.m_length;
363  x.m_root = nullptr;
364  x.m_length = 0;
365  }
366  return *this;
367  }
368 
373  {
374  Clear();
375  }
376 
380  void Clear()
381  {
382  DestroyTree( m_root );
383  m_root = nullptr;
384  m_length = 0;
385  }
386 
402  void Build( const point_list& points, int bucketCapacity = 40 )
403  {
404  Clear();
405  m_bucketCapacity = Max( 1, bucketCapacity );
406 
407  if ( !points.IsEmpty() )
408  {
409  component x = points[0][0];
410  component y = points[0][1];
411  rectangle rect( x, y, x, y );
412  for ( const point& p : points )
413  {
414  x = p[0];
415  y = p[1];
416  if ( x < rect.x0 )
417  rect.x0 = x;
418  if ( y < rect.y0 )
419  rect.y0 = y;
420  if ( x > rect.x1 )
421  rect.x1 = x;
422  if ( y > rect.y1 )
423  rect.y1 = y;
424  }
425  m_root = BuildTree( rect, points );
426  }
427  }
428 
449  void Build( const rectangle& rect, const point_list& points, int bucketCapacity = 40 )
450  {
451  Clear();
452  m_bucketCapacity = Max( 1, bucketCapacity );
453  if ( !points.IsEmpty() )
454  m_root = BuildTree( rect.Ordered(), points );
455  }
456 
465  point_list Search( const rectangle& rect ) const
466  {
467  point_list found;
468  SearchTree( found, rect.Ordered(), m_root );
469  return found;
470  }
471 
488  template <class F>
489  void Search( const rectangle& rect, F callback, void* data ) const
490  {
491  SearchTree( rect.Ordered(), callback, data, m_root );
492  }
493 
497  void Insert( const point& pt )
498  {
499  InsertTree( pt, m_root );
500  }
501 
505  void Delete( const point& pt )
506  {
507  DeleteTree( pt, m_root );
508  }
509 
514  void Delete( const rectangle& rect )
515  {
516  DeleteTree( rect.Ordered(), m_root );
517  }
518 
524  int BucketCapacity() const
525  {
526  return m_bucketCapacity;
527  }
528 
533  {
534  return m_length;
535  }
536 
540  bool IsEmpty() const
541  {
542  return m_root == nullptr;
543  }
544 
552  const Node* Root() const
553  {
554  return m_root;
555  }
556 
562  {
563  return m_root;
564  }
565 
571  const LeafNode* LeafNodeAt( rectangle::point p ) const
572  {
573  return SearchLeafNode( p, m_root );
574  }
575 
581  LeafNode* LeafNodeAt( rectangle::point p )
582  {
583  return SearchLeafNode( p, m_root );
584  }
585 
595  const Node* NodeAt( rectangle::point p ) const
596  {
597  return SearchNode( p, m_root );
598  }
599 
609  Node* NodeAt( rectangle::point p )
610  {
611  return SearchNode( p, m_root );
612  }
613 
633  template <class F>
634  static void Traverse( const Node* node, F f )
635  {
636  if ( node != nullptr )
637  if ( node->IsLeaf() )
638  f( node->rect,
639  static_cast<const LeafNode*>( node )->points,
640  static_cast<const LeafNode*>( node )->data );
641  else
642  {
643  Traverse( node->nw, f );
644  Traverse( node->ne, f );
645  Traverse( node->sw, f );
646  Traverse( node->se, f );
647  }
648  }
649 
669  template <class F>
670  static void Traverse( Node* node, F f )
671  {
672  if ( node != nullptr )
673  if ( node->IsLeaf() )
674  f( node->rect, static_cast<LeafNode*>( node )->points,
675  static_cast<LeafNode*>( node )->data );
676  else
677  {
678  Traverse( node->nw, f );
679  Traverse( node->ne, f );
680  Traverse( node->sw, f );
681  Traverse( node->se, f );
682  }
683  }
684 
694  template <class F>
695  void Traverse( F f ) const
696  {
697  Traverse( m_root, f );
698  }
699 
709  template <class F>
710  void Traverse( F f )
711  {
712  Traverse( m_root, f );
713  }
714 
718  friend void Swap( QuadTree& x1, QuadTree& x2 )
719  {
720  pcl::Swap( x1.m_root, x2.m_root );
721  pcl::Swap( x1.m_bucketCapacity, x2.m_bucketCapacity );
722  pcl::Swap( x1.m_length, x2.m_length );
723  }
724 
725 private:
726 
727  Node* m_root = nullptr;
728  int m_bucketCapacity = 0;
729  size_type m_length = 0;
730 
731  Node* NewLeafNode( const rectangle& rect, const point_list& points )
732  {
733  m_length += points.Length();
734  return new LeafNode( rect, points );
735  }
736 
737  LeafNode* SearchLeafNode( const rectangle::point& p, const Node* node ) const
738  {
739  if ( node != nullptr )
740  if ( node->Includes( p ) )
741  {
742  if ( node->IsLeaf() )
743  return const_cast<LeafNode*>( static_cast<const LeafNode*>( node ) );
744 
745  LeafNode* child = SearchLeafNode( p, node->nw );
746  if ( child == nullptr )
747  {
748  child = SearchLeafNode( p, node->ne );
749  if ( child == nullptr )
750  {
751  child = SearchLeafNode( p, node->sw );
752  if ( child == nullptr )
753  child = SearchLeafNode( p, node->se );
754  }
755  }
756  return child;
757  }
758 
759  return nullptr;
760  }
761 
762  Node* SearchNode( const rectangle::point& p, const Node* node ) const
763  {
764  if ( node != nullptr )
765  if ( node->Includes( p ) )
766  {
767  if ( node->IsLeaf() )
768  return const_cast<Node*>( node );
769 
770  Node* child = SearchNode( p, node->nw );
771  if ( child == nullptr )
772  {
773  child = SearchNode( p, node->ne );
774  if ( child == nullptr )
775  {
776  child = SearchNode( p, node->sw );
777  if ( child == nullptr )
778  {
779  child = SearchNode( p, node->se );
780  if ( child == nullptr )
781  return const_cast<Node*>( node );
782  }
783  }
784  }
785  return child;
786  }
787 
788  return nullptr;
789  }
790 
791  Node* BuildTree( const rectangle& rect, const point_list& points )
792  {
793  if ( points.IsEmpty() )
794  return nullptr;
795 
796  if ( points.Length() <= size_type( m_bucketCapacity ) )
797  return NewLeafNode( rect, points );
798 
799  double x2 = (rect.x0 + rect.x1)/2;
800  double y2 = (rect.y0 + rect.y1)/2;
801  // Prevent geometrically degenerate subtrees. For safety, we enforce
802  // minimum region dimensions larger than twice the machine epsilon for
803  // the rectangle coordinate type.
804  if ( x2 - rect.x0 < 2*std::numeric_limits<coordinate>::epsilon() ||
805  rect.x1 - x2 < 2*std::numeric_limits<coordinate>::epsilon() ||
806  y2 - rect.y0 < 2*std::numeric_limits<coordinate>::epsilon() ||
807  rect.y1 - y2 < 2*std::numeric_limits<coordinate>::epsilon() )
808  {
809  return NewLeafNode( rect, points );
810  }
811 
812  point_list nw, ne, sw, se;
813  for ( const point& p : points )
814  {
815  component x = p[0];
816  component y = p[1];
817  if ( x <= x2 )
818  {
819  if ( y <= y2 )
820  nw << p;
821  else
822  sw << p;
823  }
824  else
825  {
826  if ( y <= y2 )
827  ne << p;
828  else
829  se << p;
830  }
831  }
832 
833  Node* node = new Node( rect );
834  node->nw = BuildTree( rectangle( rect.x0, rect.y0, x2, y2 ), nw );
835  node->ne = BuildTree( rectangle( x2, rect.y0, rect.x1, y2 ), ne );
836  node->sw = BuildTree( rectangle( rect.x0, y2, x2, rect.y1 ), sw );
837  node->se = BuildTree( rectangle( x2, y2, rect.x1, rect.y1 ), se );
838 
839  // Further degeneracies may result, e.g. if the point class is not
840  // behaving as expected. Do not allow them.
841  if ( node->IsLeaf() )
842  {
843  delete node;
844  return NewLeafNode( rect, points );
845  }
846 
847  return node;
848  }
849 
850  void SearchTree( point_list& found, const rectangle& rect, const Node* node ) const
851  {
852  if ( node != nullptr )
853  if ( node->Intersects( rect ) )
854  if ( node->IsLeaf() )
855  {
856  const LeafNode* leaf = static_cast<const LeafNode*>( node );
857  for ( const point& p : leaf->points )
858  {
859  component x = p[0];
860  if ( x >= rect.x0 )
861  if ( x <= rect.x1 )
862  {
863  component y = p[1];
864  if ( y >= rect.y0 )
865  if ( y <= rect.y1 )
866  found << p;
867  }
868  }
869  }
870  else
871  {
872  SearchTree( found, rect, node->nw );
873  SearchTree( found, rect, node->ne );
874  SearchTree( found, rect, node->sw );
875  SearchTree( found, rect, node->se );
876  }
877  }
878 
879  template <class F>
880  void SearchTree( const rectangle& rect, F callback, void* data, const Node* node ) const
881  {
882  if ( node != nullptr )
883  if ( node->Intersects( rect ) )
884  if ( node->IsLeaf() )
885  {
886  const LeafNode* leaf = static_cast<const LeafNode*>( node );
887  for ( const point& p : leaf->points )
888  {
889  component x = p[0];
890  if ( x >= rect.x0 )
891  if ( x <= rect.x1 )
892  {
893  component y = p[1];
894  if ( y >= rect.y0 )
895  if ( y <= rect.y1 )
896  callback( p, data );
897  }
898  }
899  }
900  else
901  {
902  SearchTree( rect, callback, data, node->nw );
903  SearchTree( rect, callback, data, node->ne );
904  SearchTree( rect, callback, data, node->sw );
905  SearchTree( rect, callback, data, node->se );
906  }
907  }
908 
909  void InsertTree( const point& pt, Node*& node )
910  {
911  if ( node != nullptr )
912  {
913  component x = pt[0];
914  component y = pt[1];
915 
916  if ( x < node->rect.x0 )
917  node->rect.x0 = x;
918  else if ( x > node->rect.x1 )
919  node->rect.x1 = x;
920 
921  if ( y < node->rect.y0 )
922  node->rect.y0 = y;
923  else if ( y > node->rect.y1 )
924  node->rect.y1 = y;
925 
926  if ( node->IsLeaf() )
927  {
928  LeafNode* leaf = static_cast<LeafNode*>( node );
929  if ( leaf->Length() < m_bucketCapacity )
930  leaf->points << pt;
931  else
932  {
933  rectangle rect = leaf->rect;
934  double x2 = (rect.x0 + rect.x1)/2;
935  double y2 = (rect.y0 + rect.y1)/2;
936  // Prevent geometrically degenerate subtrees. For safety, we
937  // enforce minimum region dimensions larger than twice the
938  // machine epsilon for the rectangle coordinate type.
939  if ( x2 - rect.x0 < 2*std::numeric_limits<coordinate>::epsilon() ||
940  rect.x1 - x2 < 2*std::numeric_limits<coordinate>::epsilon() ||
941  y2 - rect.y0 < 2*std::numeric_limits<coordinate>::epsilon() ||
942  rect.y1 - y2 < 2*std::numeric_limits<coordinate>::epsilon() )
943  {
944  leaf->points << pt;
945  }
946  else
947  {
948  point_list nw, ne, sw, se;
949  for ( const point& p : leaf->points )
950  {
951  component x = p[0];
952  component y = p[1];
953  if ( x <= x2 )
954  {
955  if ( y <= y2 )
956  nw << p;
957  else
958  sw << p;
959  }
960  else
961  {
962  if ( y <= y2 )
963  ne << p;
964  else
965  se << p;
966  }
967  }
968 
969  if ( x <= x2 )
970  {
971  if ( y <= y2 )
972  nw << pt;
973  else
974  sw << pt;
975  }
976  else
977  {
978  if ( y <= y2 )
979  ne << pt;
980  else
981  se << pt;
982  }
983 
984  delete leaf;
985 
986  node = new Node( rect );
987 
988  if ( !nw.IsEmpty() )
989  node->nw = new LeafNode( rectangle( rect.x0, rect.y0, x2, y2 ), nw );
990  if ( !ne.IsEmpty() )
991  node->ne = new LeafNode( rectangle( x2, rect.y0, rect.x1, y2 ), ne );
992  if ( !sw.IsEmpty() )
993  node->sw = new LeafNode( rectangle( rect.x0, y2, x2, rect.y1 ), sw );
994  if ( !se.IsEmpty() )
995  node->se = new LeafNode( rectangle( x2, y2, rect.x1, rect.y1 ), se );
996  }
997  }
998 
999  ++m_length;
1000  }
1001  else
1002  {
1003  double x2 = (node->rect.x0 + node->rect.x1)/2;
1004  double y2 = (node->rect.y0 + node->rect.y1)/2;
1005  if ( pt[0] <= x2 )
1006  {
1007  if ( pt[1] <= y2 )
1008  InsertTree( pt, node->nw );
1009  else
1010  InsertTree( pt, node->sw );
1011  }
1012  else
1013  {
1014  if ( pt[1] <= y2 )
1015  InsertTree( pt, node->ne );
1016  else
1017  InsertTree( pt, node->se );
1018  }
1019  }
1020  }
1021  }
1022 
1023  void DeleteTree( const rectangle& rect, Node*& node )
1024  {
1025  if ( node != nullptr )
1026  if ( node->Intersects( rect ) )
1027  {
1028  if ( node->IsLeaf() )
1029  {
1030  LeafNode* leaf = static_cast<LeafNode*>( node );
1031  point_list points;
1032  for ( const point& p : leaf->points )
1033  {
1034  component x = p[0];
1035  if ( x >= rect.x0 )
1036  if ( x <= rect.x1 )
1037  {
1038  component y = p[1];
1039  if ( y >= rect.y0 )
1040  if ( y <= rect.y1 )
1041  {
1042  --m_length;
1043  continue;
1044  }
1045  }
1046  points << p;
1047  }
1048 
1049  if ( points.IsEmpty() )
1050  {
1051  delete leaf;
1052  node = nullptr;
1053  }
1054  else
1055  leaf->points = points;
1056  }
1057  else
1058  {
1059  DeleteTree( rect, node->nw );
1060  DeleteTree( rect, node->ne );
1061  DeleteTree( rect, node->sw );
1062  DeleteTree( rect, node->se );
1063 
1064  if ( node->IsLeaf() )
1065  {
1066  delete node;
1067  node = nullptr;
1068  }
1069  }
1070  }
1071  }
1072 
1073  void DeleteTree( const point& pt, Node*& node )
1074  {
1075  if ( node != nullptr )
1076  {
1077  component x = pt[0];
1078  component y = pt[1];
1079  if ( node->Includes( x, y ) )
1080  if ( node->IsLeaf() )
1081  {
1082  LeafNode* leaf = static_cast<LeafNode*>( node );
1083  point_list points;
1084  for ( const point& p : leaf->points )
1085  {
1086  if ( p[0] == x )
1087  if ( p[1] == y )
1088  continue;
1089  points << p;
1090  }
1091 
1092  if ( points.IsEmpty() )
1093  {
1094  delete leaf;
1095  node = nullptr;
1096  }
1097  else
1098  leaf->points = points;
1099  }
1100  else
1101  {
1102  DeleteTree( pt, node->nw );
1103  DeleteTree( pt, node->ne );
1104  DeleteTree( pt, node->sw );
1105  DeleteTree( pt, node->se );
1106 
1107  if ( node->IsLeaf() )
1108  {
1109  delete node;
1110  node = nullptr;
1111  }
1112  }
1113  }
1114  }
1115 
1116  void DestroyTree( Node* node )
1117  {
1118  if ( node != nullptr )
1119  if ( node->IsLeaf() )
1120  delete static_cast<LeafNode*>( node );
1121  else
1122  {
1123  DestroyTree( node->nw );
1124  DestroyTree( node->ne );
1125  DestroyTree( node->sw );
1126  DestroyTree( node->se );
1127  delete node;
1128  }
1129  }
1130 };
1131 
1132 // ----------------------------------------------------------------------------
1133 
1134 } // pcl
1135 
1136 #endif // __PCL_QuadTree_h
1137 
1138 // ----------------------------------------------------------------------------
1139 // EOF pcl/QuadTree.h - Released 2019-11-07T10:59:34Z
bool IsEmpty() const
Definition: Array.h:311
int Length() const
Definition: QuadTree.h:278
void Search(const rectangle &rect, F callback, void *data) const
Definition: QuadTree.h:489
QuadTree()=default
rectangle SWRect() const
Definition: QuadTree.h:223
void Swap(GenericPoint< T > &p1, GenericPoint< T > &p2)
Definition: Point.h:1402
LeafNode * LeafNodeAt(rectangle::point p)
Definition: QuadTree.h:581
void Delete(const point &pt)
Definition: QuadTree.h:505
LeafNode(const rectangle &r, const point_list &p)
Definition: QuadTree.h:269
DRect rectangle
Definition: QuadTree.h:133
rectangle::component coordinate
Definition: QuadTree.h:138
rectangle SERect() const
Definition: QuadTree.h:232
int BucketCapacity() const
Definition: QuadTree.h:524
Node * sw
South-West child node, representing the bottom-left subregion.
Definition: QuadTree.h:151
PCL root namespace.
Definition: AbstractImage.h:76
friend void Swap(QuadTree &x1, QuadTree &x2)
Definition: QuadTree.h:718
Array< point > point_list
Definition: QuadTree.h:128
point::component component
Definition: QuadTree.h:123
void Build(const point_list &points, int bucketCapacity=40)
Definition: QuadTree.h:402
rectangle NWRect() const
Definition: QuadTree.h:207
static void Traverse(const Node *node, F f)
Definition: QuadTree.h:634
rectangle NERect() const
Definition: QuadTree.h:215
void Clear()
Definition: QuadTree.h:380
rectangle rect
The rectangular region represented by this node.
Definition: QuadTree.h:148
void Traverse(F f) const
Definition: QuadTree.h:695
size_t size_type
Definition: Defs.h:543
QuadTree(const rectangle &rect, const point_list &points, int bucketCapacity=40)
Definition: QuadTree.h:323
64-bit floating-point rectangle in the R^2 space.
void Delete(const rectangle &rect)
Definition: QuadTree.h:514
size_type Length() const
Definition: QuadTree.h:532
constexpr const T & Max(const T &a, const T &b)
Definition: Utility.h:119
Node * Root()
Definition: QuadTree.h:561
Node * NodeAt(rectangle::point p)
Definition: QuadTree.h:609
bool IsEmpty() const
Definition: QuadTree.h:540
Quadtree node structure.
Definition: QuadTree.h:146
Node * nw
North-West child node, representing the top-left subregion.
Definition: QuadTree.h:149
bool Intersects(const rectangle &r) const
Definition: QuadTree.h:179
Quadtree leaf node structure.
Definition: QuadTree.h:244
static void Traverse(Node *node, F f)
Definition: QuadTree.h:670
QuadTree(QuadTree &&x)
Definition: QuadTree.h:345
const Node * NodeAt(rectangle::point p) const
Definition: QuadTree.h:595
size_type Length() const
Definition: Array.h:265
Bucket PR quadtree for two-dimensional point data.
Definition: QuadTree.h:111
const Node * Root() const
Definition: QuadTree.h:552
Node(const rectangle &r=rectangle(0.0))
Definition: QuadTree.h:157
QuadTree(const point_list &points, int bucketCapacity=40)
Definition: QuadTree.h:303
void Insert(const point &pt)
Definition: QuadTree.h:497
void Build(const rectangle &rect, const point_list &points, int bucketCapacity=40)
Definition: QuadTree.h:449
bool IsLeaf() const
Definition: QuadTree.h:170
Node * se
South-East child node, representing the bottom-right subregion.
Definition: QuadTree.h:152
point_list Search(const rectangle &rect) const
Definition: QuadTree.h:465
const LeafNode * LeafNodeAt(rectangle::point p) const
Definition: QuadTree.h:571
void Traverse(F f)
Definition: QuadTree.h:710
bool Includes(coordinate x, coordinate y) const
Definition: QuadTree.h:189
Node * ne
North-East child node, representing the top-right subregion.
Definition: QuadTree.h:150
QuadTree & operator=(const QuadTree &)=delete
bool Includes(const rectangle::point &p) const
Definition: QuadTree.h:199