1 /**********************************************************
2 * Version $Id$
3 *********************************************************/
4
5 ///////////////////////////////////////////////////////////
6 // //
7 // SAGA //
8 // //
9 // System for Automated Geoscientific Analyses //
10 // //
11 // Application Programming Interface //
12 // //
13 // Library: SAGA_API //
14 // //
15 //-------------------------------------------------------//
16 // //
17 // shapes_search.cpp //
18 // //
19 // Copyright (C) 2005 by Olaf Conrad //
20 // //
21 //-------------------------------------------------------//
22 // //
23 // This file is part of 'SAGA - System for Automated //
24 // Geoscientific Analyses'. //
25 // //
26 // This library is free software; you can redistribute //
27 // it and/or modify it under the terms of the GNU Lesser //
28 // General Public License as published by the Free //
29 // Software Foundation, either version 2.1 of the //
30 // License, or (at your option) any later version. //
31 // //
32 // This library is distributed in the hope that it will //
33 // be useful, but WITHOUT ANY WARRANTY; without even the //
34 // implied warranty of MERCHANTABILITY or FITNESS FOR A //
35 // PARTICULAR PURPOSE. See the GNU Lesser General Public //
36 // License for more details. //
37 // //
38 // You should have received a copy of the GNU Lesser //
39 // General Public License along with this program; if //
40 // not, see <http://www.gnu.org/licenses/>. //
41 // //
42 //-------------------------------------------------------//
43 // //
44 // contact: Olaf Conrad //
45 // Institute of Geography //
46 // University of Goettingen //
47 // Goldschmidtstr. 5 //
48 // 37077 Goettingen //
49 // Germany //
50 // //
51 // e-mail: oconrad@saga-gis.org //
52 // //
53 ///////////////////////////////////////////////////////////
54
55 //---------------------------------------------------------
56
57
58 ///////////////////////////////////////////////////////////
59 // //
60 // //
61 // //
62 ///////////////////////////////////////////////////////////
63
64 //---------------------------------------------------------
65 #include "shapes.h"
66
67
68 ///////////////////////////////////////////////////////////
69 // //
70 // //
71 // //
72 ///////////////////////////////////////////////////////////
73
74 //---------------------------------------------------------
CSG_Shapes_Search(void)75 CSG_Shapes_Search::CSG_Shapes_Search(void)
76 {
77 _On_Construction();
78 }
79
80 //---------------------------------------------------------
CSG_Shapes_Search(CSG_Shapes * pPoints)81 CSG_Shapes_Search::CSG_Shapes_Search(CSG_Shapes *pPoints)
82 {
83 _On_Construction();
84
85 Create(pPoints);
86 }
87
88 //---------------------------------------------------------
_On_Construction(void)89 void CSG_Shapes_Search::_On_Construction(void)
90 {
91 m_pPoints = NULL;
92 m_nPoints = 0;
93 m_bDestroy = false;
94
95 m_nSelected = 0;
96 m_Selected = NULL;
97 m_Selected_Dst = NULL;
98 m_Selected_Buf = 0;
99
100 m_Pos = NULL;
101 }
102
103
104 ///////////////////////////////////////////////////////////
105 // //
106 // //
107 // //
108 ///////////////////////////////////////////////////////////
109
110 //---------------------------------------------------------
~CSG_Shapes_Search(void)111 CSG_Shapes_Search::~CSG_Shapes_Search(void)
112 {
113 Destroy();
114 }
115
116 //---------------------------------------------------------
Destroy(void)117 void CSG_Shapes_Search::Destroy(void)
118 {
119 if( m_nPoints > 0 )
120 {
121 SG_Free(m_Pos);
122 }
123
124 m_Pos = NULL;
125 m_Idx .Destroy();
126
127 //-----------------------------------------------------
128 if( m_bDestroy && m_pPoints )
129 {
130 delete(m_pPoints);
131 }
132
133 m_pPoints = NULL;
134 m_nPoints = 0;
135 m_bDestroy = false;
136
137 //-----------------------------------------------------
138 if( m_Selected )
139 {
140 SG_Free(m_Selected);
141 SG_Free(m_Selected_Dst);
142 }
143
144 m_Selected = NULL;
145 m_Selected_Dst = NULL;
146 m_nSelected = 0;
147 m_Selected_Buf = 0;
148
149 m_Selected_Idx .Destroy();
150 }
151
152
153 ///////////////////////////////////////////////////////////
154 // //
155 // //
156 // //
157 ///////////////////////////////////////////////////////////
158
159 //---------------------------------------------------------
Create(CSG_Shapes * pShapes)160 bool CSG_Shapes_Search::Create(CSG_Shapes *pShapes)
161 {
162 int iShape, iPart, iPoint;
163 CSG_Shape *pShape, *pPoint;
164 double *Value;
165
166 Destroy();
167
168 //-----------------------------------------------------
169 if( pShapes && pShapes->is_Valid() )
170 {
171 if( pShapes->Get_Type() == SHAPE_TYPE_Point )
172 {
173 m_bDestroy = false;
174 m_pPoints = pShapes;
175 }
176 else
177 {
178 m_bDestroy = true;
179 m_pPoints = SG_Create_Shapes(SHAPE_TYPE_Point, NULL, pShapes);
180
181 for(iShape=0; iShape<pShapes->Get_Count() && SG_UI_Process_Set_Progress(iShape, pShapes->Get_Count()); iShape++)
182 {
183 pShape = pShapes->Get_Shape(iShape);
184
185 for(iPart=0; iPart<pShape->Get_Part_Count(); iPart++)
186 {
187 for(iPoint=0; iPoint<pShape->Get_Point_Count(iPart); iPoint++)
188 {
189 pPoint = m_pPoints->Add_Shape(pShape);
190 pPoint->Add_Point(pShape->Get_Point(iPoint, iPart));
191 }
192 }
193 }
194 }
195
196 //-------------------------------------------------
197 if( m_pPoints->Get_Count() > 1 )
198 {
199 m_nPoints = m_pPoints->Get_Count();
200
201 Value = (double *)SG_Malloc(m_nPoints * sizeof(double));
202 m_Pos = (TSG_Point *)SG_Malloc(m_nPoints * sizeof(TSG_Point));
203
204 for(iPoint=0; iPoint<m_nPoints; iPoint++)
205 {
206 Value[iPoint] = m_pPoints->Get_Shape(iPoint)->Get_Point(0).x;
207 }
208
209 m_Idx.Create(m_nPoints, Value, true);
210
211 for(iPoint=0; iPoint<m_nPoints; iPoint++)
212 {
213 m_Pos[iPoint] = m_pPoints->Get_Shape(m_Idx[iPoint])->Get_Point(0);
214 }
215
216 SG_Free(Value);
217
218 return( true );
219 }
220 }
221
222 //-----------------------------------------------------
223 Destroy();
224
225 return( false );
226 }
227
228
229 ///////////////////////////////////////////////////////////
230 // //
231 // //
232 // //
233 ///////////////////////////////////////////////////////////
234
235 //---------------------------------------------------------
_Get_Index_Next(double Position)236 int CSG_Shapes_Search::_Get_Index_Next(double Position)
237 {
238 int i, iLo, iHi;
239
240 if( m_Pos[0].x > Position )
241 {
242 return( 0 );
243 }
244 else if( m_Pos[m_nPoints - 1].x < Position )
245 {
246 return( m_nPoints - 1 );
247 }
248
249 for(iLo=0, iHi=m_nPoints-1; iHi-iLo>1; )
250 {
251 i = iLo + (iHi - iLo) / 2;
252
253 if( m_Pos[i].x <= Position )
254 {
255 iLo = i;
256 }
257 else
258 {
259 iHi = i;
260 }
261 }
262
263 return( Position - m_Pos[iLo].x < m_Pos[iHi].x - Position ? iLo : iHi );
264 }
265
266
267 ///////////////////////////////////////////////////////////
268 // //
269 // //
270 // //
271 ///////////////////////////////////////////////////////////
272
273 //---------------------------------------------------------
Get_Point_Nearest(double x,double y)274 CSG_Shape * CSG_Shapes_Search::Get_Point_Nearest(double x, double y)
275 {
276 int ax, ix, iPoint_Min;
277 double dx, dy, Dist, Dist_Min;
278
279 //-----------------------------------------------------
280 iPoint_Min = -1;
281 ax = _Get_Index_Next(x);
282
283 //-----------------------------------------------------
284 for(ix=ax, Dist_Min=-1.0; ix<m_nPoints; ix++)
285 {
286 dy = m_Pos[ix].y - y;
287 dx = m_Pos[ix].x - x;
288
289 if( iPoint_Min >= 0 && Dist_Min < dx )
290 {
291 break;
292 }
293 else
294 {
295 Dist = sqrt(dx*dx + dy*dy);
296
297 if( iPoint_Min < 0 || Dist < Dist_Min )
298 {
299 iPoint_Min = m_Idx[ix];
300 Dist_Min = Dist;
301 }
302 }
303 }
304
305 //-----------------------------------------------------
306 for(ix=ax-1; ix>=0; ix--)
307 {
308 dy = m_Pos[ix].y - y;
309 dx = m_Pos[ix].x - x;
310
311 if( iPoint_Min >= 0 && Dist_Min < dx )
312 {
313 break;
314 }
315 else
316 {
317 Dist = sqrt(dx*dx + dy*dy);
318
319 if( iPoint_Min < 0 || Dist < Dist_Min )
320 {
321 iPoint_Min = m_Idx[ix];
322 Dist_Min = Dist;
323 }
324 }
325 }
326
327 return( iPoint_Min < 0 ? NULL : m_pPoints->Get_Shape(iPoint_Min) );
328 }
329
330
331 ///////////////////////////////////////////////////////////
332 // //
333 // //
334 // //
335 ///////////////////////////////////////////////////////////
336
337 //---------------------------------------------------------
Get_Point_Nearest(double x,double y,int Quadrant)338 CSG_Shape * CSG_Shapes_Search::Get_Point_Nearest(double x, double y, int Quadrant)
339 {
340 int iPoint;
341
342 iPoint = _Get_Point_Nearest(x, y, Quadrant);
343
344 return( iPoint >= 0 && iPoint < m_nPoints ? m_pPoints->Get_Shape(iPoint) : NULL );
345 }
346
347 //---------------------------------------------------------
_Get_Point_Nearest(double x,double y,int Quadrant)348 int CSG_Shapes_Search::_Get_Point_Nearest(double x, double y, int Quadrant)
349 {
350 int ax, ix, iPoint_Min;
351 double dx, dy, Dist, Dist_Min;
352
353 //-----------------------------------------------------
354 Dist_Min = -1.0;
355 iPoint_Min = -1;
356 ax = _Get_Index_Next(x);
357
358 switch( Quadrant )
359 {
360 //-----------------------------------------------------
361 case 0: // +x +y
362 if( m_Pos[ax].x < x )
363 {
364 ax++;
365 }
366
367 for(ix=ax; ix<m_nPoints; ix++)
368 {
369 if( (dy = m_Pos[ix].y - y) >= 0.0 )
370 {
371 dx = m_Pos[ix].x - x;
372
373 if( iPoint_Min >= 0 && Dist_Min < dx )
374 {
375 return( iPoint_Min );
376 }
377
378 Dist = sqrt(dx*dx + dy*dy);
379
380 if( iPoint_Min < 0 || Dist < Dist_Min )
381 {
382 iPoint_Min = m_Idx[ix];
383 Dist_Min = Dist;
384 }
385 }
386 }
387 break;
388
389 //-----------------------------------------------------
390 case 1: // +x -y
391 if( m_Pos[ax].x < x )
392 {
393 ax++;
394 }
395
396 for(ix=ax; ix<m_nPoints; ix++)
397 {
398 if( (dy = m_Pos[ix].y - y) <= 0.0 )
399 {
400 dx = m_Pos[ix].x - x;
401
402 if( iPoint_Min >= 0 && Dist_Min < dx )
403 {
404 return( iPoint_Min );
405 }
406
407 Dist = sqrt(dx*dx + dy*dy);
408
409 if( iPoint_Min < 0 || Dist < Dist_Min )
410 {
411 iPoint_Min = m_Idx[ix];
412 Dist_Min = Dist;
413 }
414 }
415 }
416 break;
417
418 //-----------------------------------------------------
419 case 2: // -x -y
420 if( m_Pos[ax].x > x )
421 {
422 ax--;
423 }
424
425 for(ix=ax; ix>=0; ix--)
426 {
427 if( (dy = m_Pos[ix].y - y) <= 0.0 )
428 {
429 dx = m_Pos[ix].x - x;
430
431 if( iPoint_Min >= 0 && Dist_Min < dx )
432 {
433 return( iPoint_Min );
434 }
435
436 Dist = sqrt(dx*dx + dy*dy);
437
438 if( iPoint_Min < 0 || Dist < Dist_Min )
439 {
440 iPoint_Min = m_Idx[ix];
441 Dist_Min = Dist;
442 }
443 }
444 }
445 break;
446
447 //-----------------------------------------------------
448 case 3: // -x +y
449 if( m_Pos[ax].x > x )
450 {
451 ax--;
452 }
453
454 for(ix=ax; ix>=0; ix--)
455 {
456 if( (dy = m_Pos[ix].y - y) >= 0.0 )
457 {
458 dx = m_Pos[ix].x - x;
459
460 if( iPoint_Min >= 0 && Dist_Min < dx )
461 {
462 return( iPoint_Min );
463 }
464
465 Dist = sqrt(dx*dx + dy*dy);
466
467 if( iPoint_Min < 0 || Dist < Dist_Min )
468 {
469 iPoint_Min = m_Idx[ix];
470 Dist_Min = Dist;
471 }
472 }
473 }
474 break;
475 }
476
477 //-----------------------------------------------------
478 return( iPoint_Min );
479 }
480
481
482 ///////////////////////////////////////////////////////////
483 // //
484 // //
485 // //
486 ///////////////////////////////////////////////////////////
487
488 //---------------------------------------------------------
_Select_Add(CSG_Shape * pPoint,double Distance)489 void CSG_Shapes_Search::_Select_Add(CSG_Shape *pPoint, double Distance)
490 {
491 if( m_nSelected >= m_Selected_Buf )
492 {
493 m_Selected_Buf += 8;
494
495 m_Selected = (CSG_Shape **)SG_Realloc(m_Selected , m_Selected_Buf * sizeof(CSG_Shape *));
496 m_Selected_Dst = (double *)SG_Realloc(m_Selected_Dst, m_Selected_Buf * sizeof(double ));
497 }
498
499 m_Selected [m_nSelected] = pPoint;
500 m_Selected_Dst[m_nSelected] = Distance;
501 m_nSelected++;
502 }
503
504 //---------------------------------------------------------
Select_Radius(double x,double y,double Radius,bool bSort,int MaxPoints,int iQuadrant)505 int CSG_Shapes_Search::Select_Radius(double x, double y, double Radius, bool bSort, int MaxPoints, int iQuadrant)
506 {
507 int xLeft, xRight;
508 double yBottom, yTop, Radius_2;
509
510 m_nSelected = 0;
511
512 Radius_2 = Radius*Radius;
513
514 switch( iQuadrant )
515 {
516 default: // all
517 xLeft = _Get_Index_Next(x - Radius);
518 xRight = _Get_Index_Next(x + Radius);
519 yBottom = -Radius;
520 yTop = Radius;
521 break;
522
523 case 0: // upper right
524 xLeft = _Get_Index_Next(x);
525 xRight = _Get_Index_Next(x + Radius);
526 yBottom = 0.0;
527 yTop = Radius;
528 break;
529
530 case 1: // lower right
531 xLeft = _Get_Index_Next(x);
532 xRight = _Get_Index_Next(x + Radius);
533 yBottom = -Radius;
534 yTop = 0.0;
535 break;
536
537 case 2: // upper left
538 xLeft = _Get_Index_Next(x - Radius);
539 xRight = _Get_Index_Next(x);
540 yBottom = 0.0;
541 yTop = Radius;
542 break;
543
544 case 3: // lower left
545 xLeft = _Get_Index_Next(x - Radius);
546 xRight = _Get_Index_Next(x);
547 yBottom = -Radius;
548 yTop = 0.0;
549 break;
550 }
551
552 for(int ix=xLeft; ix<=xRight; ix++)
553 {
554 double d = m_Pos[ix].y - y;
555
556 if( yBottom <= d && d < yTop && (d = d*d + SG_Get_Square(m_Pos[ix].x - x)) <= Radius_2 )
557 {
558 _Select_Add(m_pPoints->Get_Shape(m_Idx[ix]), d);
559 }
560 }
561
562 if( bSort || (MaxPoints > 0 && MaxPoints < m_nSelected) )
563 {
564 m_Selected_Idx.Create(m_nSelected, m_Selected_Dst, true);
565 }
566
567 return( MaxPoints <= 0 || MaxPoints > m_nSelected ? m_nSelected : MaxPoints );
568 }
569
570 //---------------------------------------------------------
Select_Quadrants(double x,double y,double Radius,int MaxPoints,int MinPoints)571 int CSG_Shapes_Search::Select_Quadrants(double x, double y, double Radius, int MaxPoints, int MinPoints)
572 {
573 if( MaxPoints <= 0 )
574 {
575 return( Select_Radius(x, y, Radius, true, MaxPoints) );
576 }
577
578 int iQuadrant, i, n, nTotal;
579
580 CSG_Shape **Selected = (CSG_Shape **)SG_Malloc(4 * MaxPoints * sizeof(CSG_Shape *));
581
582
583 for(iQuadrant=0, nTotal=0; iQuadrant<4; iQuadrant++)
584 {
585 n = Select_Radius(x, y, Radius, false, MaxPoints, iQuadrant);
586
587 if( n < MinPoints )
588 {
589 return( 0 );
590 }
591
592 for(i=0; i<n; i++)
593 {
594 Selected[nTotal + i] = Get_Selected_Point(i);
595 }
596
597 nTotal += n;
598 }
599
600
601 for(i=0, m_nSelected=0; i<nTotal; i++)
602 {
603 _Select_Add(Selected[i], -1.0);
604 }
605
606 SG_Free(Selected);
607
608 return( m_nSelected );
609 }
610
611
612 ///////////////////////////////////////////////////////////
613 // //
614 // //
615 // //
616 ///////////////////////////////////////////////////////////
617
618 //---------------------------------------------------------
619