SAGA API  v9.5
quadtree.cpp
Go to the documentation of this file.
1 
3 // //
4 // SAGA //
5 // //
6 // System for Automated Geoscientific Analyses //
7 // //
8 // Application Programming Interface //
9 // //
10 // Library: SAGA_API //
11 // //
12 //-------------------------------------------------------//
13 // //
14 // quadtree.cpp //
15 // //
16 // Copyright (C) 2009 by Olaf Conrad //
17 // //
18 //-------------------------------------------------------//
19 // //
20 // This file is part of 'SAGA - System for Automated //
21 // Geoscientific Analyses'. //
22 // //
23 // This library is free software; you can redistribute //
24 // it and/or modify it under the terms of the GNU Lesser //
25 // General Public License as published by the Free //
26 // Software Foundation, either version 2.1 of the //
27 // License, or (at your option) any later version. //
28 // //
29 // This library is distributed in the hope that it will //
30 // be useful, but WITHOUT ANY WARRANTY; without even the //
31 // implied warranty of MERCHANTABILITY or FITNESS FOR A //
32 // PARTICULAR PURPOSE. See the GNU Lesser General Public //
33 // License for more details. //
34 // //
35 // You should have received a copy of the GNU Lesser //
36 // General Public License along with this program; if //
37 // not, see <http://www.gnu.org/licenses/>. //
38 // //
39 //-------------------------------------------------------//
40 // //
41 // e-mail: oconrad@saga-gis.org //
42 // //
43 // contact: Olaf Conrad //
44 // Institute of Geography //
45 // University of Hamburg //
46 // Germany //
47 // //
49 
50 //---------------------------------------------------------
51 #include "shapes.h"
52 
53 
55 // //
56 // //
57 // //
59 
60 //---------------------------------------------------------
61 CSG_PRQuadTree_Node::CSG_PRQuadTree_Node(const CSG_Rect &Extent, int Quadrant)
62  : CSG_PRQuadTree_Item(Extent, Quadrant)
63 {
64  m_pChildren[0] = m_pChildren[1] = m_pChildren[2] = m_pChildren[3] = NULL;
65 }
66 
67 //---------------------------------------------------------
68 CSG_PRQuadTree_Node::CSG_PRQuadTree_Node(CSG_PRQuadTree_Leaf *pLeaf)
69  : CSG_PRQuadTree_Item(pLeaf->m_Extent)
70 {
71  m_pChildren[0] = m_pChildren[1] = m_pChildren[2] = m_pChildren[3] = NULL;
72 
73  int Quadrant = Get_Quadrant(pLeaf->Get_Point());
74 
75  pLeaf->Set_Extent(m_Extent, Quadrant);
76 
77  m_pChildren[Quadrant] = pLeaf;
78 }
79 
80 //---------------------------------------------------------
81 CSG_PRQuadTree_Node::~CSG_PRQuadTree_Node(void)
82 {
83  for(int i=0; i<4; i++)
84  {
85  if( m_pChildren[i] )
86  {
87  if( m_pChildren[i]->is_Leaf() )
88  {
89  delete((CSG_PRQuadTree_Leaf *)m_pChildren[i]);
90  }
91  else
92  {
93  delete((CSG_PRQuadTree_Node *)m_pChildren[i]);
94  }
95  }
96  }
97 }
98 
99 //---------------------------------------------------------
100 CSG_PRQuadTree_Item * CSG_PRQuadTree_Node::Get_Child(double x, double y)
101 {
102  for(int i=0; i<4; i++)
103  {
104  if( m_pChildren[i] && m_pChildren[i]->Contains(x, y) )
105  {
106  return( m_pChildren[i]->is_Node() ? m_pChildren[i]->asNode()->Get_Child(x, y) : m_pChildren[i] );
107  }
108  }
109 
110  return( this );
111 }
112 
113 //---------------------------------------------------------
114 bool CSG_PRQuadTree_Node::Add_Point(double x, double y, double z)
115 {
116  if( !Contains(x, y) )
117  {
118  return( false );
119  }
120 
121  if( has_Statistics() )
122  {
123  Get_X()->Add_Value(x);
124  Get_Y()->Add_Value(y);
125  Get_Z()->Add_Value(z);
126  }
127 
128  int Quadrant = Get_Quadrant(x, y);
129 
130  //-----------------------------------------------------
131  if( m_pChildren[Quadrant] == NULL )
132  {
133  m_pChildren[Quadrant] = new CSG_PRQuadTree_Leaf(m_Extent, Quadrant, x, y, z);
134 
135  return( true );
136  }
137 
138  //-----------------------------------------------------
139  if( m_pChildren[Quadrant]->is_Leaf() )
140  {
141  CSG_PRQuadTree_Leaf *pLeaf = m_pChildren[Quadrant]->asLeaf();
142 
143  if( x != pLeaf->Get_X() || y != pLeaf->Get_Y() )
144  {
145  if( has_Statistics() )
146  {
147  m_pChildren[Quadrant] = new CSG_PRQuadTree_Node_Statistics(pLeaf);
148  }
149  else
150  {
151  m_pChildren[Quadrant] = new CSG_PRQuadTree_Node(pLeaf);
152  }
153 
154  ((CSG_PRQuadTree_Node *)m_pChildren[Quadrant])->Add_Point(x, y, z);
155  }
156  else // if( x == pLeaf->Get_X() || y == pLeaf->Get_Y() ) // duplicate !!
157  {
158  if( !pLeaf->has_Statistics() )
159  {
160  m_pChildren[Quadrant] = new CSG_PRQuadTree_Leaf_List(pLeaf->m_Extent, -1, x, y, pLeaf->m_z);
161 
162  delete(pLeaf);
163  }
164 
165  ((CSG_PRQuadTree_Leaf_List *)m_pChildren[Quadrant])->Add_Value(z);
166  }
167 
168  return( true );
169  }
170 
171  //-----------------------------------------------------
172  return( ((CSG_PRQuadTree_Node *)m_pChildren[Quadrant])->Add_Point(x, y, z) ); // if( m_pChildren[i]->is_Node() )
173 }
174 
175 
177 // //
178 // //
179 // //
181 
182 //---------------------------------------------------------
183 CSG_PRQuadTree::CSG_PRQuadTree(void)
184 {
185  m_pRoot = NULL;
186  m_nPoints = 0;
187  m_bPolar = false;
188 }
189 
190 //---------------------------------------------------------
191 CSG_PRQuadTree::CSG_PRQuadTree(const TSG_Rect &Extent, bool bStatistics)
192 {
193  m_pRoot = NULL;
194  m_nPoints = 0;
195  m_bPolar = false;
196 
197  Create(Extent, bStatistics);
198 }
199 
200 //---------------------------------------------------------
201 CSG_PRQuadTree::CSG_PRQuadTree(CSG_Shapes *pShapes, int Attribute, bool bStatistics)
202 {
203  m_pRoot = NULL;
204  m_nPoints = 0;
205  m_bPolar = false;
206 
207  Create(pShapes, Attribute, bStatistics);
208 }
209 
210 //---------------------------------------------------------
211 CSG_PRQuadTree::~CSG_PRQuadTree(void)
212 {
213  Destroy();
214 }
215 
216 //---------------------------------------------------------
217 bool CSG_PRQuadTree::Create(const CSG_Rect &Extent, bool bStatistics)
218 {
219  Destroy();
220 
221  if( Extent.Get_XRange() > 0.0 && Extent.Get_YRange() > 0.0 )
222  {
223  double Size = (0.5 + 0.01) * (Extent.Get_XRange() > Extent.Get_YRange() ? Extent.Get_XRange() : Extent.Get_YRange());
224 
225  CSG_Rect r(
226  Extent.Get_XCenter() - Size, Extent.Get_YCenter() - Size,
227  Extent.Get_XCenter() + Size, Extent.Get_YCenter() + Size
228  );
229 
230  if( bStatistics )
231  {
232  m_pRoot = new CSG_PRQuadTree_Node_Statistics(r);
233  }
234  else
235  {
236  m_pRoot = new CSG_PRQuadTree_Node(r);
237  }
238 
239  return( true );
240  }
241 
242  return( false );
243 }
244 
245 //---------------------------------------------------------
246 bool CSG_PRQuadTree::Create(CSG_Shapes *pShapes, int Attribute, bool bStatistics)
247 {
248  Destroy();
249 
250  if( pShapes && pShapes->is_Valid() && Create(pShapes->Get_Extent(), bStatistics) )
251  {
252  for(sLong iShape=0; iShape<pShapes->Get_Count() && SG_UI_Process_Set_Progress(iShape, pShapes->Get_Count()); iShape++)
253  {
254  CSG_Shape *pShape = pShapes->Get_Shape(iShape);
255 
256  if( Attribute < 0 || !pShape->is_NoData(Attribute) )
257  {
258  double z = Attribute < 0 ? iShape : pShape->asDouble(Attribute);
259 
260  for(int iPart=0; iPart<pShape->Get_Part_Count(); iPart++)
261  {
262  for(int iPoint=0; iPoint<pShape->Get_Point_Count(iPart); iPoint++)
263  {
264  Add_Point(pShape->Get_Point(iPoint, iPart), z);
265  }
266  }
267  }
268  }
269 
270  return( m_nPoints > 0 );
271  }
272 
273  return( false );
274 }
275 
276 //---------------------------------------------------------
277 void CSG_PRQuadTree::Destroy(void)
278 {
279  if( m_pRoot )
280  {
281  delete(m_pRoot);
282 
283  m_pRoot = NULL;
284  }
285 
286  m_nPoints = 0;
287 
288  m_Selection.Destroy();
289 }
290 
291 
293 // //
295 
296 //---------------------------------------------------------
297 bool CSG_PRQuadTree::Add_Point(double x, double y, double z)
298 {
299  if( _Check_Root(x, y) && m_pRoot->Add_Point(x, y, z) )
300  {
301  m_nPoints++;
302 
303  return( true );
304  }
305 
306  return( false );
307 }
308 
309 //---------------------------------------------------------
310 bool CSG_PRQuadTree::Add_Point(const TSG_Point &p, double z)
311 {
312  return( Add_Point(p.x, p.y, z) );
313 }
314 
315 
317 // //
319 
320 //---------------------------------------------------------
321 bool CSG_PRQuadTree::_Check_Root(double x, double y)
322 {
323  if( !m_pRoot )
324  {
325  return( false );
326  }
327 
328  if( m_pRoot->Get_Extent().Contains(x, y) )
329  {
330  return( true );
331  }
332 
333  //-----------------------------------------------------
334  int Quadrant = y < m_pRoot->Get_yMin() // bottom / top ?
335  ? (x < m_pRoot->Get_xMin() ? 0 : 3) // bottom: left / right ?
336  : (x < m_pRoot->Get_xMin() ? 1 : 2); // top : left / right ?
337 
338  TSG_Rect Extent = m_pRoot->Get_Extent();
339 
340  switch( Quadrant )
341  {
342  case 0: Extent.xMin -= m_pRoot->Get_Size(); Extent.yMin -= m_pRoot->Get_Size(); break; // bottom left
343  case 1: Extent.xMin -= m_pRoot->Get_Size(); Extent.yMax += m_pRoot->Get_Size(); break; // top left
344  case 2: Extent.xMax += m_pRoot->Get_Size(); Extent.yMin -= m_pRoot->Get_Size(); break; // bottom right
345  case 3: Extent.xMax += m_pRoot->Get_Size(); Extent.yMax += m_pRoot->Get_Size(); break; // top right
346  }
347 
348  CSG_PRQuadTree_Node *pRoot;
349 
350  if( m_pRoot->has_Statistics() )
351  {
352  CSG_PRQuadTree_Node_Statistics *pNode = new CSG_PRQuadTree_Node_Statistics(Extent);
353 
354  pNode->m_x = ((CSG_PRQuadTree_Node_Statistics *)m_pRoot)->m_x;
355  pNode->m_y = ((CSG_PRQuadTree_Node_Statistics *)m_pRoot)->m_y;
356  pNode->m_z = ((CSG_PRQuadTree_Node_Statistics *)m_pRoot)->m_z;
357 
358  pRoot = pNode;
359  }
360  else
361  {
362  pRoot = new CSG_PRQuadTree_Node(Extent);
363  }
364 
365  pRoot->m_pChildren[Quadrant] = m_pRoot;
366 
367  m_pRoot = pRoot;
368 
369  return( _Check_Root(x, y) );
370 }
371 
372 
374 // //
376 
377 //---------------------------------------------------------
378 inline bool CSG_PRQuadTree::_Quadrant_Contains(double x, double y, int iQuadrant, const TSG_Point &p) const
379 {
380  switch( iQuadrant )
381  {
382  case 0: return( x < p.x && y < p.y ); // lower left
383  case 1: return( x < p.x && y >= p.y ); // upper left
384  case 2: return( x >= p.x && y >= p.y ); // upper right
385  case 3: return( x >= p.x && y < p.y ); // lower right
386  }
387 
388  return( true );
389 }
390 
391 //---------------------------------------------------------
392 inline bool CSG_PRQuadTree::_Radius_Contains(double x, double y, double r, const TSG_Point &p) const
393 {
394  double dx, dy;
395 
396  if( fabs(dx = x - p.x) <= r && fabs(dy = y - p.y) <= r )
397  {
398  return( dx*dx + dy*dy < r*r );
399  }
400 
401  return( false );
402 }
403 
404 //---------------------------------------------------------
405 inline bool CSG_PRQuadTree::_Radius_Contains(double x, double y, double r, int iQuadrant, const TSG_Point &p) const
406 {
407  return( _Quadrant_Contains(x, y, iQuadrant, p) && _Radius_Contains(x, y, r, p) );
408 }
409 
410 //---------------------------------------------------------
411 inline bool CSG_PRQuadTree::_Quadrant_Intersects(double x, double y, int iQuadrant, CSG_PRQuadTree_Item *pItem) const
412 {
413  switch( iQuadrant )
414  {
415  case 0: return( x < pItem->Get_xMax() && y < pItem->Get_yMax() ); // lower left
416  case 1: return( x < pItem->Get_xMax() && y >= pItem->Get_yMin() ); // upper left
417  case 2: return( x >= pItem->Get_xMin() && y >= pItem->Get_yMin() ); // upper right
418  case 3: return( x >= pItem->Get_xMin() && y < pItem->Get_yMax() ); // lower right
419  }
420 
421  return( true );
422 }
423 
424 //---------------------------------------------------------
425 inline bool CSG_PRQuadTree::_Radius_Intersects(double x, double y, double r, CSG_PRQuadTree_Item *pItem) const
426 {
427  if( r <= 0.0 )
428  {
429  return( true );
430  }
431 
432  if( pItem->Get_xMax() < x - r || pItem->Get_xMin() > x + r
433  || pItem->Get_yMax() < y - r || pItem->Get_yMin() > y + r )
434  {
435  return( false );
436  }
437 
438  if( (pItem->Get_xMin() <= x && x <= pItem->Get_xMax())
439  || (pItem->Get_yMin() <= y && y <= pItem->Get_yMax()) )
440  {
441  return( true );
442  }
443 
444  TSG_Point p;
445 
446  if( pItem->Get_xMax() < x )
447  {
448  p.x = pItem->Get_xMax();
449  p.y = pItem->Get_yMax() < y ? pItem->Get_yMax() : pItem->Get_yMin();
450  }
451  else // if( pItem->Get_xMin() >= x )
452  {
453  p.x = pItem->Get_xMin();
454  p.y = pItem->Get_yMax() < y ? pItem->Get_yMax() : pItem->Get_yMin();
455  }
456 
457  return( _Radius_Contains(x, y, r, p) );
458 }
459 
460 //---------------------------------------------------------
461 inline bool CSG_PRQuadTree::_Radius_Intersects(double x, double y, double r, int iQuadrant, CSG_PRQuadTree_Item *pItem) const
462 {
463  return( _Quadrant_Intersects(x, y, iQuadrant, pItem) && _Radius_Intersects(x, y, r, pItem) );
464 }
465 
466 
468 // //
470 
471 //---------------------------------------------------------
472 CSG_PRQuadTree_Leaf * CSG_PRQuadTree::Get_Nearest_Leaf(const TSG_Point &p, double &Distance) const
473 {
474  return( Get_Nearest_Leaf(p.x, p.y, Distance) );
475 }
476 
477 CSG_PRQuadTree_Leaf * CSG_PRQuadTree::Get_Nearest_Leaf(double x, double y, double &Distance) const
478 {
479  return( _Get_Nearest_Point(m_pRoot, x, y, Distance = -1) );
480 }
481 
482 //---------------------------------------------------------
483 bool CSG_PRQuadTree::Get_Nearest_Point(const TSG_Point &p, TSG_Point &Point, double &Value, double &Distance) const
484 {
485  return( Get_Nearest_Point(p.x, p.y, Point, Value, Distance) );
486 }
487 
488 bool CSG_PRQuadTree::Get_Nearest_Point(double x, double y, TSG_Point &Point, double &Value, double &Distance) const
489 {
490  CSG_PRQuadTree_Leaf *pLeaf = _Get_Nearest_Point(m_pRoot, x, y, Distance = -1);
491 
492  if( pLeaf )
493  {
494  Point.x = pLeaf->Get_X();
495  Point.y = pLeaf->Get_Y();
496  Value = pLeaf->Get_Z();
497 
498  return( true );
499  }
500 
501  return( false );
502 }
503 
504 //---------------------------------------------------------
505 CSG_PRQuadTree_Leaf * CSG_PRQuadTree::_Get_Nearest_Point(CSG_PRQuadTree_Item *pItem, double x, double y, double &Distance) const
506 {
507  CSG_PRQuadTree_Leaf *pLeaf, *pNearest = NULL;
508 
509  if( pItem )
510  {
511  if( pItem->is_Leaf() )
512  {
513  pLeaf = (CSG_PRQuadTree_Leaf *)pItem;
514 
515  double d = SG_Get_Distance(x, y, pLeaf->Get_X(), pLeaf->Get_Y(), m_bPolar);
516 
517  if( Distance < 0.0 || Distance > d )
518  {
519  Distance = d;
520  pNearest = pLeaf;
521  }
522  }
523  else // if( pItem->is_Node() )
524  {
525  int i;
526 
527  if( pItem->Contains(x, y) )
528  {
529  for(i=0; i<4; i++)
530  {
531  CSG_PRQuadTree_Item *pChild = ((CSG_PRQuadTree_Node *)pItem)->Get_Child(i);
532 
533  if( pChild && pChild->Contains(x, y) && (pLeaf = _Get_Nearest_Point(pChild, x, y, Distance)) != NULL )
534  {
535  pNearest = pLeaf;
536  }
537  }
538  }
539 
540  for(i=0; i<4; i++)
541  {
542  CSG_PRQuadTree_Item *pChild = ((CSG_PRQuadTree_Node *)pItem)->Get_Child(i);
543 
544  if( pChild && pChild->Contains(x, y) == false && (Distance < 0.0
545  || ( Distance > (x < pChild->Get_xCenter() ? pChild->Get_xMin() - x : x - pChild->Get_xMax())
546  && Distance > (y < pChild->Get_yCenter() ? pChild->Get_yMin() - y : y - pChild->Get_yMax()) ))
547  && (pLeaf = _Get_Nearest_Point(pChild, x, y, Distance)) != NULL )
548  {
549  pNearest = pLeaf;
550  }
551  }
552  }
553  }
554 
555  return( pNearest );
556 }
557 
558 
560 // //
562 
563 //---------------------------------------------------------
564 inline CSG_PRQuadTree::TLeaf * CSG_PRQuadTree::_Get_Selected(const CSG_Array &Selection, size_t i) const
565 {
566  return( (TLeaf *)Selection.Get_Entry(i) );
567 }
568 
569 //---------------------------------------------------------
570 inline bool CSG_PRQuadTree::_Add_Selected(CSG_Array &Selection, CSG_PRQuadTree_Leaf *pLeaf, double Distance) const
571 {
572  if( Selection.Inc_Array() )
573  {
574  TLeaf *pL = (TLeaf *)Selection.Get_Entry(Selection.Get_Size() - 1);
575 
576  pL->pLeaf = pLeaf;
577  pL->Distance = Distance;
578 
579  return( true );
580  }
581 
582  return( false );
583 }
584 
585 //---------------------------------------------------------
586 inline bool CSG_PRQuadTree::_Set_Selected(CSG_Array &Selection, size_t i, CSG_PRQuadTree_Leaf *pLeaf, double Distance) const
587 {
588  TLeaf *pL = (TLeaf *)Selection.Get_Entry(i);
589 
590  if( pL )
591  {
592  pL->pLeaf = pLeaf;
593  pL->Distance = Distance;
594 
595  return( true );
596  }
597 
598  return( false );
599 }
600 
601 
603 // //
605 
606 //---------------------------------------------------------
607 size_t CSG_PRQuadTree::Select_Nearest_Points(const TSG_Point &p, size_t maxPoints, double Radius, int iQuadrant)
608 {
609  return( Select_Nearest_Points(p.x, p.y, maxPoints, Radius, iQuadrant) );
610 }
611 
612 //---------------------------------------------------------
613 size_t CSG_PRQuadTree::Select_Nearest_Points(double x, double y, size_t maxPoints, double Radius, int iQuadrant)
614 {
615  return( _Select_Nearest_Points(m_Selection, x, y, maxPoints, Radius, iQuadrant) );
616 }
617 
618 //---------------------------------------------------------
619 size_t CSG_PRQuadTree::_Select_Nearest_Points(CSG_Array &Selection, double x, double y, size_t maxPoints, double Radius, int iQuadrant) const
620 {
621  if( Selection.Get_Value_Size() != sizeof(TLeaf) )
622  {
623  Selection.Create(sizeof(TLeaf), 0, TSG_Array_Growth::SG_ARRAY_GROWTH_3);
624  }
625  else
626  {
627  Selection.Set_Array(0, false);
628  }
629 
630  if( m_pRoot )
631  {
632  double Distance;
633 
634  if( maxPoints < 1 )
635  {
636  maxPoints = m_nPoints;
637  }
638 
639  if( iQuadrant != 4 )
640  {
641  _Select_Nearest_Points(Selection, m_pRoot, x, y, Distance = 0.0, Radius, maxPoints, iQuadrant);
642  }
643  else // if( iQuadrant == 4 ) // quadrant-wise search
644  {
645  for(iQuadrant=0; iQuadrant<4; iQuadrant++)
646  {
647  _Select_Nearest_Points(Selection, m_pRoot, x, y, Distance = 0.0, Radius, maxPoints, iQuadrant);
648  }
649  }
650  }
651 
652  return( Selection.Get_Size() );
653 }
654 
655 //---------------------------------------------------------
656 void CSG_PRQuadTree::_Select_Nearest_Points(CSG_Array &Selection, CSG_PRQuadTree_Item *pItem, double x, double y, double &Distance, double Radius, size_t maxPoints, int iQuadrant) const
657 {
658  //-----------------------------------------------------
659  if( pItem->is_Leaf() )
660  {
661  CSG_PRQuadTree_Leaf *pLeaf = (CSG_PRQuadTree_Leaf *)pItem;
662 
663  if( _Quadrant_Contains(x, y, iQuadrant, pLeaf->Get_Point()) == false )
664  {
665  return;
666  }
667 
668  double d = SG_Get_Distance(x, y, pLeaf->Get_X(), pLeaf->Get_Y(), m_bPolar);
669 
670  if( Radius > 0.0 && Radius < d )
671  {
672  return;
673  }
674 
675  //-------------------------------------------------
676  if( (int)Selection.Get_Size() < maxPoints )
677  {
678  if( Distance < d )
679  {
680  Distance = d;
681  }
682 
683  _Add_Selected(Selection, pLeaf, d);
684  }
685  else if( d < Distance )
686  {
687  for(size_t i=0; i<(int)Selection.Get_Size(); i++)
688  {
689  if( Distance <= _Get_Selected(Selection, i)->Distance )
690  {
691  _Set_Selected(Selection, i, pLeaf, d);
692 
693  break;
694  }
695  }
696 
697  Distance = d;
698 
699  for(size_t i=0; i<maxPoints; i++)
700  {
701  if( Distance < _Get_Selected(Selection, i)->Distance )
702  {
703  Distance = _Get_Selected(Selection, i)->Distance;
704  }
705  }
706  }
707  }
708 
709  //-----------------------------------------------------
710  else // if( pItem->is_Node() )
711  {
712  int i;
713 
714  CSG_PRQuadTree_Item *pChild;
715 
716  for(i=0; i<4; i++)
717  {
718  if( (pChild = ((CSG_PRQuadTree_Node *)pItem)->Get_Child(i)) != NULL && pChild->Contains(x, y) == true )
719  {
720  _Select_Nearest_Points(Selection, pChild, x, y, Distance, Radius, maxPoints, iQuadrant);
721  }
722  }
723 
724  for(i=0; i<4; i++)
725  {
726  if( (pChild = ((CSG_PRQuadTree_Node *)pItem)->Get_Child(i)) != NULL && pChild->Contains(x, y) == false )
727  {
728  if( _Radius_Intersects(x, y, Radius, iQuadrant, pChild) )
729  {
730  if( Get_Selected_Count() < maxPoints
731  || ( Distance > (x < pChild->Get_xCenter() ? pChild->Get_xMin() - x : x - pChild->Get_xMax())
732  && Distance > (y < pChild->Get_yCenter() ? pChild->Get_yMin() - y : y - pChild->Get_yMax()) ) )
733  {
734  _Select_Nearest_Points(Selection, pChild, x, y, Distance, Radius, maxPoints, iQuadrant);
735  }
736  }
737  }
738  }
739  }
740 }
741 
742 
744 // //
746 
747 //---------------------------------------------------------
748 size_t CSG_PRQuadTree::Get_Nearest_Points(CSG_Points_3D &Points, const TSG_Point &p, size_t maxPoints, double Radius, int iQuadrant) const
749 {
750  return( Get_Nearest_Points(Points, p.x, p.y, maxPoints, Radius, iQuadrant) );
751 }
752 
753 //---------------------------------------------------------
754 size_t CSG_PRQuadTree::Get_Nearest_Points(CSG_Points_3D &Points, double x, double y, size_t maxPoints, double Radius, int iQuadrant) const
755 {
756  CSG_Array Selection;
757 
758  _Select_Nearest_Points(Selection, x, y, maxPoints, Radius, iQuadrant);
759 
760  Points.Clear();
761 
762  for(size_t i=0; i<(int)Selection.Get_Size(); i++)
763  {
764  CSG_PRQuadTree_Leaf *pLeaf = _Get_Selected(Selection, i)->pLeaf;
765 
766  Points.Add(pLeaf->Get_X(), pLeaf->Get_Y(), pLeaf->Get_Z());
767  }
768 
769  return( Points.Get_Count() );
770 }
771 
772 
774 // //
775 // //
776 // //
778 
779 //---------------------------------------------------------
CSG_Rect
Definition: geo_tools.h:471
CSG_Table_Record::asDouble
double asDouble(int Field) const
Definition: table_record.cpp:527
CSG_Array::Set_Array
bool Set_Array(sLong nValues, bool bShrink=true)
Definition: api_memory.cpp:310
CSG_PRQuadTree::Destroy
void Destroy(void)
Definition: quadtree.cpp:277
CSG_Points_3D
Definition: geo_tools.h:320
CSG_Array::Get_Size
sLong Get_Size(void) const
Definition: api_core.h:327
CSG_Points_3D::Add
bool Add(double x, double y, double z)
Definition: geo_classes.cpp:582
CSG_PRQuadTree_Leaf_List
Definition: shapes.h:1004
CSG_PRQuadTree_Node_Statistics
Definition: shapes.h:1077
CSG_Shapes::Get_Shape
virtual CSG_Shape * Get_Shape(const CSG_Point &Point, double Epsilon=0.)
Definition: shapes.cpp:499
CSG_PRQuadTree_Node_Statistics::m_x
CSG_Simple_Statistics m_x
Definition: shapes.h:1103
CSG_PRQuadTree_Node::~CSG_PRQuadTree_Node
virtual ~CSG_PRQuadTree_Node(void)
Definition: quadtree.cpp:81
CSG_PRQuadTree::Get_Selected_Count
size_t Get_Selected_Count(void) const
Definition: shapes.h:1146
CSG_PRQuadTree::~CSG_PRQuadTree
virtual ~CSG_PRQuadTree(void)
Definition: quadtree.cpp:211
CSG_PRQuadTree_Node::Get_Child
CSG_PRQuadTree_Item * Get_Child(int Quadrant) const
Definition: shapes.h:1054
CSG_Points_3D::Get_Count
sLong Get_Count(void) const
Definition: geo_tools.h:336
CSG_PRQuadTree_Leaf::Get_Y
double Get_Y(void) const
Definition: shapes.h:979
SSG_Rect::xMax
double xMax
Definition: geo_tools.h:465
CSG_PRQuadTree_Item::Get_xCenter
double Get_xCenter(void) const
Definition: shapes.h:924
SSG_Point
Definition: geo_tools.h:128
CSG_Shapes::is_Valid
virtual bool is_Valid(void) const
Definition: shapes.h:807
CSG_Points_3D::Clear
bool Clear(void)
Definition: geo_tools.h:326
CSG_PRQuadTree_Node
Definition: shapes.h:1047
CSG_PRQuadTree::Create
bool Create(const CSG_Rect &Extent, bool bStatistics=false)
Definition: quadtree.cpp:217
CSG_PRQuadTree_Leaf::Get_Point
const TSG_Point & Get_Point(void) const
Definition: shapes.h:977
SSG_Rect::xMin
double xMin
Definition: geo_tools.h:465
CSG_Rect::Contains
bool Contains(double x, double y) const
Definition: geo_classes.cpp:870
SSG_Rect
Definition: geo_tools.h:464
CSG_Shape::Get_Point
virtual TSG_Point Get_Point(int iPoint=0) const =0
CSG_Shape::Get_Part_Count
virtual int Get_Part_Count(void) const =0
CSG_Rect::Get_XRange
double Get_XRange(void) const
Definition: geo_tools.h:507
CSG_PRQuadTree_Node::CSG_PRQuadTree_Node
CSG_PRQuadTree_Node(const CSG_Rect &Extent, int Quadrant=-1)
Definition: quadtree.cpp:61
CSG_PRQuadTree_Item::Contains
bool Contains(const CSG_Point &p) const
Definition: shapes.h:931
CSG_Array::Destroy
bool Destroy(void)
Definition: api_memory.cpp:291
CSG_PRQuadTree_Node::Get_Y
virtual CSG_Simple_Statistics * Get_Y(void)
Definition: shapes.h:1060
CSG_PRQuadTree_Node_Statistics::m_z
CSG_Simple_Statistics m_z
Definition: shapes.h:1103
CSG_Array::Get_Value_Size
size_t Get_Value_Size(void) const
Definition: api_core.h:326
SG_Get_Distance
double SG_Get_Distance(double ax, double ay, double bx, double by, bool bPolar)
Definition: geo_functions.cpp:103
CSG_PRQuadTree_Leaf::Get_X
double Get_X(void) const
Definition: shapes.h:978
sLong
signed long long sLong
Definition: api_core.h:158
CSG_PRQuadTree_Item::m_Extent
CSG_Rect m_Extent
Definition: shapes.h:964
CSG_PRQuadTree_Node::is_Node
virtual bool is_Node(void) const
Definition: shapes.h:1052
CSG_PRQuadTree_Item::is_Leaf
virtual bool is_Leaf(void) const
Definition: shapes.h:918
CSG_PRQuadTree::Select_Nearest_Points
size_t Select_Nearest_Points(const TSG_Point &p, size_t maxPoints, double Radius=0., int iQuadrant=-1)
Definition: quadtree.cpp:607
CSG_Table::Get_Count
sLong Get_Count(void) const
Definition: table.h:392
CSG_PRQuadTree::Get_Nearest_Points
size_t Get_Nearest_Points(CSG_Points_3D &Points, const TSG_Point &p, size_t maxPoints, double Radius=0., int iQuadrant=-1) const
Definition: quadtree.cpp:748
CSG_PRQuadTree_Node::Get_Z
virtual CSG_Simple_Statistics * Get_Z(void)
Definition: shapes.h:1061
CSG_PRQuadTree_Item::asNode
class CSG_PRQuadTree_Node * asNode(void) const
Definition: shapes.h:935
CSG_PRQuadTree_Leaf::Get_Z
double Get_Z(void) const
Definition: shapes.h:980
CSG_PRQuadTree_Item::Get_yMin
double Get_yMin(void) const
Definition: shapes.h:926
CSG_Array::Create
void * Create(const CSG_Array &Array)
Definition: api_memory.cpp:250
SSG_Rect::yMax
double yMax
Definition: geo_tools.h:465
CSG_Shapes::Get_Extent
virtual const CSG_Rect & Get_Extent(void)
Definition: shapes.h:813
CSG_PRQuadTree_Node::Get_X
virtual CSG_Simple_Statistics * Get_X(void)
Definition: shapes.h:1059
CSG_PRQuadTree_Node_Statistics::m_y
CSG_Simple_Statistics m_y
Definition: shapes.h:1103
CSG_PRQuadTree::CSG_PRQuadTree
CSG_PRQuadTree(void)
Definition: quadtree.cpp:183
CSG_PRQuadTree::Get_Nearest_Leaf
CSG_PRQuadTree_Leaf * Get_Nearest_Leaf(const TSG_Point &p, double &Distance) const
Definition: quadtree.cpp:472
CSG_Shape::Get_Point_Count
virtual int Get_Point_Count(void) const =0
CSG_PRQuadTree_Node::m_pChildren
CSG_PRQuadTree_Item * m_pChildren[4]
Definition: shapes.h:1071
CSG_Array::Inc_Array
bool Inc_Array(sLong nValues=1)
Definition: api_memory.cpp:414
CSG_PRQuadTree_Node::Add_Point
bool Add_Point(double x, double y, double z)
Definition: quadtree.cpp:114
CSG_Array
Definition: api_core.h:308
shapes.h
CSG_Simple_Statistics::Add_Value
void Add_Value(double Value, double Weight=1.)
Definition: mat_tools.cpp:527
CSG_PRQuadTree_Item::Set_Extent
void Set_Extent(const CSG_Rect &Extent, int Quadrant=-1)
Definition: shapes.h:944
CSG_PRQuadTree_Item::Get_Extent
const CSG_Rect & Get_Extent(void) const
Definition: shapes.h:922
CSG_PRQuadTree_Item::asLeaf
class CSG_PRQuadTree_Leaf * asLeaf(void) const
Definition: shapes.h:934
CSG_PRQuadTree_Item::Get_Size
double Get_Size(void) const
Definition: shapes.h:929
SG_UI_Process_Set_Progress
bool SG_UI_Process_Set_Progress(int Position, int Range)
Definition: api_callback.cpp:256
SSG_Point::x
double x
Definition: geo_tools.h:129
SSG_Rect::yMin
double yMin
Definition: geo_tools.h:465
CSG_Rect::Get_XCenter
double Get_XCenter(void) const
Definition: geo_tools.h:517
SSG_Point::y
double y
Definition: geo_tools.h:129
CSG_PRQuadTree::Get_Nearest_Point
bool Get_Nearest_Point(const TSG_Point &p, TSG_Point &Point, double &Value, double &Distance) const
Definition: quadtree.cpp:483
CSG_Rect::Get_YCenter
double Get_YCenter(void) const
Definition: geo_tools.h:518
CSG_PRQuadTree_Leaf::m_z
double m_z
Definition: shapes.h:996
CSG_Shapes
Definition: shapes.h:775
CSG_PRQuadTree_Item::has_Statistics
virtual bool has_Statistics(void) const
Definition: shapes.h:920
CSG_PRQuadTree_Item::Get_Quadrant
int Get_Quadrant(const TSG_Point &p) const
Definition: shapes.h:956
CSG_PRQuadTree_Item::Get_xMin
double Get_xMin(void) const
Definition: shapes.h:923
CSG_PRQuadTree_Item
Definition: shapes.h:915
CSG_Shape
Definition: shapes.h:141
CSG_PRQuadTree_Item::Get_yMax
double Get_yMax(void) const
Definition: shapes.h:928
CSG_Rect::Get_YRange
double Get_YRange(void) const
Definition: geo_tools.h:508
CSG_Array::Get_Entry
void * Get_Entry(sLong Index) const
Returns a pointer to the memory address of the requested variable. You have to type cast and derefere...
Definition: api_core.h:331
CSG_PRQuadTree_Leaf
Definition: shapes.h:970
CSG_PRQuadTree::Add_Point
bool Add_Point(double x, double y, double z)
Definition: quadtree.cpp:297
CSG_PRQuadTree_Item::Get_xMax
double Get_xMax(void) const
Definition: shapes.h:925