SAGA API v9.10
Loading...
Searching...
No Matches
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//---------------------------------------------------------
61CSG_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//---------------------------------------------------------
68CSG_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//---------------------------------------------------------
81CSG_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//---------------------------------------------------------
100CSG_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//---------------------------------------------------------
114bool 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//---------------------------------------------------------
183CSG_PRQuadTree::CSG_PRQuadTree(void)
184{
185 m_pRoot = NULL;
186 m_nPoints = 0;
187 m_bPolar = false;
188}
189
190//---------------------------------------------------------
191CSG_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//---------------------------------------------------------
201CSG_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//---------------------------------------------------------
215
216//---------------------------------------------------------
217bool 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//---------------------------------------------------------
246bool 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//---------------------------------------------------------
277void 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//---------------------------------------------------------
297bool 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//---------------------------------------------------------
310bool 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//---------------------------------------------------------
321bool 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//---------------------------------------------------------
378inline 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//---------------------------------------------------------
392inline 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//---------------------------------------------------------
405inline 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//---------------------------------------------------------
411inline 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//---------------------------------------------------------
425inline 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//---------------------------------------------------------
461inline 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//---------------------------------------------------------
472CSG_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
477CSG_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//---------------------------------------------------------
483bool 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
488bool 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//---------------------------------------------------------
505CSG_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//---------------------------------------------------------
564inline 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//---------------------------------------------------------
570inline 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//---------------------------------------------------------
586inline 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//---------------------------------------------------------
607size_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//---------------------------------------------------------
613size_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//---------------------------------------------------------
619size_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//---------------------------------------------------------
656void 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( Selection.Get_uSize() < 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<Selection.Get_uSize(); 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//---------------------------------------------------------
748size_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//---------------------------------------------------------
754size_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<Selection.Get_uSize(); 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//---------------------------------------------------------
SG_UI_Process_Set_Progress
bool SG_UI_Process_Set_Progress(int Position, int Range)
Definition api_callback.cpp:255
TSG_Array_Growth::SG_ARRAY_GROWTH_3
@ SG_ARRAY_GROWTH_3
Definition api_core.h:295
sLong
signed long long sLong
Definition api_core.h:158
CSG_Array
Definition api_core.h:308
CSG_Array::Create
void * Create(const CSG_Array &Array)
Definition api_memory.cpp:250
CSG_Array::Set_Array
bool Set_Array(sLong nValues, bool bShrink=true)
Definition api_memory.cpp:310
CSG_Array::Inc_Array
bool Inc_Array(sLong nValues=1)
Definition api_memory.cpp:414
CSG_Array::Get_Value_Size
size_t Get_Value_Size(void) const
Definition api_core.h:326
CSG_Array::Get_Size
sLong Get_Size(void) const
Definition api_core.h:327
CSG_Array::Get_uSize
size_t Get_uSize(void) const
Definition api_core.h:328
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_Item
Definition shapes.h:911
CSG_PRQuadTree_Item::m_Extent
CSG_Rect m_Extent
Definition shapes.h:960
CSG_PRQuadTree_Item::is_Leaf
virtual bool is_Leaf(void) const
Definition shapes.h:914
CSG_PRQuadTree_Item::Get_xMax
double Get_xMax(void) const
Definition shapes.h:921
CSG_PRQuadTree_Item::Get_yMin
double Get_yMin(void) const
Definition shapes.h:922
CSG_PRQuadTree_Item::Get_yMax
double Get_yMax(void) const
Definition shapes.h:924
CSG_PRQuadTree_Item::CSG_PRQuadTree_Item
CSG_PRQuadTree_Item(const CSG_Rect &Extent, int Quadrant=-1)
Definition shapes.h:936
CSG_PRQuadTree_Item::Set_Extent
void Set_Extent(const CSG_Rect &Extent, int Quadrant=-1)
Definition shapes.h:940
CSG_PRQuadTree_Item::has_Statistics
virtual bool has_Statistics(void) const
Definition shapes.h:916
CSG_PRQuadTree_Item::Get_xMin
double Get_xMin(void) const
Definition shapes.h:919
CSG_PRQuadTree_Item::Contains
bool Contains(const CSG_Point &p) const
Definition shapes.h:927
CSG_PRQuadTree_Item::Get_Quadrant
int Get_Quadrant(const TSG_Point &p) const
Definition shapes.h:952
CSG_PRQuadTree_Item::asNode
class CSG_PRQuadTree_Node * asNode(void) const
Definition shapes.h:931
CSG_PRQuadTree_Leaf_List
Definition shapes.h:1000
CSG_PRQuadTree_Leaf
Definition shapes.h:966
CSG_PRQuadTree_Leaf::m_z
double m_z
Definition shapes.h:992
CSG_PRQuadTree_Leaf::Get_Z
double Get_Z(void) const
Definition shapes.h:976
CSG_PRQuadTree_Leaf::Get_Point
const TSG_Point & Get_Point(void) const
Definition shapes.h:973
CSG_PRQuadTree_Leaf::Get_X
double Get_X(void) const
Definition shapes.h:974
CSG_PRQuadTree_Leaf::Get_Y
double Get_Y(void) const
Definition shapes.h:975
CSG_PRQuadTree_Node_Statistics
Definition shapes.h:1073
CSG_PRQuadTree_Node_Statistics::m_z
CSG_Simple_Statistics m_z
Definition shapes.h:1099
CSG_PRQuadTree_Node_Statistics::m_x
CSG_Simple_Statistics m_x
Definition shapes.h:1099
CSG_PRQuadTree_Node_Statistics::m_y
CSG_Simple_Statistics m_y
Definition shapes.h:1099
CSG_PRQuadTree_Node
Definition shapes.h:1043
CSG_PRQuadTree_Node::Get_Child
CSG_PRQuadTree_Item * Get_Child(int Quadrant) const
Definition shapes.h:1050
CSG_PRQuadTree_Node::m_pChildren
CSG_PRQuadTree_Item * m_pChildren[4]
Definition shapes.h:1067
CSG_PRQuadTree_Node::Get_Z
virtual CSG_Simple_Statistics * Get_Z(void)
Definition shapes.h:1057
CSG_PRQuadTree_Node::~CSG_PRQuadTree_Node
virtual ~CSG_PRQuadTree_Node(void)
Definition quadtree.cpp:81
CSG_PRQuadTree_Node::Get_X
virtual CSG_Simple_Statistics * Get_X(void)
Definition shapes.h:1055
CSG_PRQuadTree_Node::CSG_PRQuadTree_Node
CSG_PRQuadTree_Node(const CSG_Rect &Extent, int Quadrant=-1)
Definition quadtree.cpp:61
CSG_PRQuadTree_Node::Get_Y
virtual CSG_Simple_Statistics * Get_Y(void)
Definition shapes.h:1056
CSG_PRQuadTree_Node::is_Node
virtual bool is_Node(void) const
Definition shapes.h:1048
CSG_PRQuadTree_Node::Add_Point
bool Add_Point(double x, double y, double z)
Definition quadtree.cpp:114
CSG_PRQuadTree::Get_Selected_Count
size_t Get_Selected_Count(void) const
Definition shapes.h:1142
CSG_PRQuadTree::CSG_PRQuadTree
CSG_PRQuadTree(void)
Definition quadtree.cpp:183
CSG_PRQuadTree::~CSG_PRQuadTree
virtual ~CSG_PRQuadTree(void)
Definition quadtree.cpp:211
CSG_PRQuadTree::Create
bool Create(const CSG_Rect &Extent, bool bStatistics=false)
Definition quadtree.cpp:217
CSG_PRQuadTree::Get_Nearest_Leaf
CSG_PRQuadTree_Leaf * Get_Nearest_Leaf(const TSG_Point &p, double &Distance) const
Definition quadtree.cpp:472
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_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::Add_Point
bool Add_Point(double x, double y, double z)
Definition quadtree.cpp:297
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_PRQuadTree::Destroy
void Destroy(void)
Definition quadtree.cpp:277
CSG_Points_3D
Definition geo_tools.h:322
CSG_Points_3D::Clear
bool Clear(void)
Definition geo_tools.h:328
CSG_Points_3D::Add
bool Add(double x, double y, double z)
Definition geo_classes.cpp:582
CSG_Points_3D::Get_Count
sLong Get_Count(void) const
Definition geo_tools.h:338
CSG_Rect
Definition geo_tools.h:474
CSG_Rect::Get_YRange
double Get_YRange(void) const
Definition geo_tools.h:511
CSG_Rect::Get_YCenter
double Get_YCenter(void) const
Definition geo_tools.h:521
CSG_Rect::Get_XRange
double Get_XRange(void) const
Definition geo_tools.h:510
CSG_Rect::Get_XCenter
double Get_XCenter(void) const
Definition geo_tools.h:520
CSG_Shape
Definition shapes.h:141
CSG_Shape::Get_Point_Count
virtual int Get_Point_Count(void) const =0
CSG_Shape::Get_Part_Count
virtual int Get_Part_Count(void) const =0
CSG_Shape::Get_Point
virtual TSG_Point Get_Point(int iPoint=0) const =0
CSG_Shapes
Definition shapes.h:772
CSG_Shapes::is_Valid
virtual bool is_Valid(void) const
Definition shapes.h:804
CSG_Shapes::Get_Extent
virtual const CSG_Rect & Get_Extent(void)
Definition shapes.h:810
CSG_Shapes::Get_Shape
virtual CSG_Shape * Get_Shape(const CSG_Point &Point, double Epsilon=0.)
Definition shapes.cpp:483
CSG_Simple_Statistics::Add_Value
void Add_Value(double Value, double Weight=1.)
Definition mat_tools.cpp:527
CSG_Table_Record::asDouble
double asDouble(int Field) const
Definition table_record.cpp:527
CSG_Table::Get_Count
sLong Get_Count(void) const
Definition table.h:400
SG_Get_Distance
double SG_Get_Distance(double ax, double ay, double bx, double by, bool bPolar)
Definition geo_functions.cpp:103
TSG_Point
struct SSG_Point TSG_Point
TSG_Rect
struct SSG_Rect TSG_Rect
SSG_Point::x
double x
Definition geo_tools.h:129
SSG_Point::y
double y
Definition geo_tools.h:129
SSG_Rect::xMin
double xMin
Definition geo_tools.h:468
SSG_Rect::xMax
double xMax
Definition geo_tools.h:468
SSG_Rect::yMin
double yMin
Definition geo_tools.h:468
SSG_Rect::yMax
double yMax
Definition geo_tools.h:468