source: TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/shapelib/shptree.c @ 2194

Subversion URL: http://proj.badc.rl.ac.uk/svn/ndg/TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/shapelib/shptree.c@2194
Revision 2194, 26.8 KB checked in by lawrence, 13 years ago (diff)

Adding various specs and 3rd party code of interest for the CSML
services development.

Line 
1/******************************************************************************
2 * $Id: shptree.c,v 1.9 2003/01/28 15:53:41 warmerda Exp $
3 *
4 * Project:  Shapelib
5 * Purpose:  Implementation of quadtree building and searching functions.
6 * Author:   Frank Warmerdam, warmerdam@pobox.com
7 *
8 ******************************************************************************
9 * Copyright (c) 1999, Frank Warmerdam
10 *
11 * This software is available under the following "MIT Style" license,
12 * or at the option of the licensee under the LGPL (see LICENSE.LGPL).  This
13 * option is discussed in more detail in shapelib.html.
14 *
15 * --
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining a
18 * copy of this software and associated documentation files (the "Software"),
19 * to deal in the Software without restriction, including without limitation
20 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
21 * and/or sell copies of the Software, and to permit persons to whom the
22 * Software is furnished to do so, subject to the following conditions:
23 *
24 * The above copyright notice and this permission notice shall be included
25 * in all copies or substantial portions of the Software.
26 *
27 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
28 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
29 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
30 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
31 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
32 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
33 * DEALINGS IN THE SOFTWARE.
34 ******************************************************************************
35 *
36 * $Log: shptree.c,v $
37 * Revision 1.9  2003/01/28 15:53:41  warmerda
38 * Avoid build warnings.
39 *
40 * Revision 1.8  2002/05/07 13:07:45  warmerda
41 * use qsort() - patch from Bernhard Herzog
42 *
43 * Revision 1.7  2002/01/15 14:36:07  warmerda
44 * updated email address
45 *
46 * Revision 1.6  2001/05/23 13:36:52  warmerda
47 * added use of SHPAPI_CALL
48 *
49 * Revision 1.5  1999/11/05 14:12:05  warmerda
50 * updated license terms
51 *
52 * Revision 1.4  1999/06/02 18:24:21  warmerda
53 * added trimming code
54 *
55 * Revision 1.3  1999/06/02 17:56:12  warmerda
56 * added quad'' subnode support for trees
57 *
58 * Revision 1.2  1999/05/18 19:11:11  warmerda
59 * Added example searching capability
60 *
61 * Revision 1.1  1999/05/18 17:49:20  warmerda
62 * New
63 *
64 */
65
66static char rcsid[] = 
67  "$Id: shptree.c,v 1.9 2003/01/28 15:53:41 warmerda Exp $";
68
69#include "shapefil.h"
70
71#include <math.h>
72#include <assert.h>
73#include <stdlib.h>
74#include <string.h>
75
76#ifndef TRUE
77#  define TRUE 1
78#  define FALSE 0
79#endif
80
81
82/* -------------------------------------------------------------------- */
83/*      If the following is 0.5, nodes will be split in half.  If it    */
84/*      is 0.6 then each subnode will contain 60% of the parent         */
85/*      node, with 20% representing overlap.  This can be help to       */
86/*      prevent small objects on a boundary from shifting too high      */
87/*      up the tree.                                                    */
88/* -------------------------------------------------------------------- */
89
90#define SHP_SPLIT_RATIO 0.55
91
92/************************************************************************/
93/*                             SfRealloc()                              */
94/*                                                                      */
95/*      A realloc cover function that will access a NULL pointer as     */
96/*      a valid input.                                                  */
97/************************************************************************/
98
99static void * SfRealloc( void * pMem, int nNewSize )
100
101{
102    if( pMem == NULL )
103        return( (void *) malloc(nNewSize) );
104    else
105        return( (void *) realloc(pMem,nNewSize) );
106}
107
108/************************************************************************/
109/*                          SHPTreeNodeInit()                           */
110/*                                                                      */
111/*      Initialize a tree node.                                         */
112/************************************************************************/
113
114static SHPTreeNode *SHPTreeNodeCreate( double * padfBoundsMin,
115                                       double * padfBoundsMax )
116
117{
118    SHPTreeNode *psTreeNode;
119
120    psTreeNode = (SHPTreeNode *) malloc(sizeof(SHPTreeNode));
121
122    psTreeNode->nShapeCount = 0;
123    psTreeNode->panShapeIds = NULL;
124    psTreeNode->papsShapeObj = NULL;
125
126    psTreeNode->nSubNodes = 0;
127
128    if( padfBoundsMin != NULL )
129        memcpy( psTreeNode->adfBoundsMin, padfBoundsMin, sizeof(double) * 4 );
130
131    if( padfBoundsMax != NULL )
132        memcpy( psTreeNode->adfBoundsMax, padfBoundsMax, sizeof(double) * 4 );
133
134    return psTreeNode;
135}
136
137
138/************************************************************************/
139/*                           SHPCreateTree()                            */
140/************************************************************************/
141
142SHPTree SHPAPI_CALL1(*)
143SHPCreateTree( SHPHandle hSHP, int nDimension, int nMaxDepth,
144               double *padfBoundsMin, double *padfBoundsMax )
145
146{
147    SHPTree     *psTree;
148
149    if( padfBoundsMin == NULL && hSHP == NULL )
150        return NULL;
151
152/* -------------------------------------------------------------------- */
153/*      Allocate the tree object                                        */
154/* -------------------------------------------------------------------- */
155    psTree = (SHPTree *) malloc(sizeof(SHPTree));
156
157    psTree->hSHP = hSHP;
158    psTree->nMaxDepth = nMaxDepth;
159    psTree->nDimension = nDimension;
160
161/* -------------------------------------------------------------------- */
162/*      If no max depth was defined, try to select a reasonable one     */
163/*      that implies approximately 8 shapes per node.                   */
164/* -------------------------------------------------------------------- */
165    if( psTree->nMaxDepth == 0 && hSHP != NULL )
166    {
167        int     nMaxNodeCount = 1;
168        int     nShapeCount;
169
170        SHPGetInfo( hSHP, &nShapeCount, NULL, NULL, NULL );
171        while( nMaxNodeCount*4 < nShapeCount )
172        {
173            psTree->nMaxDepth += 1;
174            nMaxNodeCount = nMaxNodeCount * 2;
175        }
176    }
177
178/* -------------------------------------------------------------------- */
179/*      Allocate the root node.                                         */
180/* -------------------------------------------------------------------- */
181    psTree->psRoot = SHPTreeNodeCreate( padfBoundsMin, padfBoundsMax );
182
183/* -------------------------------------------------------------------- */
184/*      Assign the bounds to the root node.  If none are passed in,     */
185/*      use the bounds of the provided file otherwise the create        */
186/*      function will have already set the bounds.                      */
187/* -------------------------------------------------------------------- */
188    if( padfBoundsMin == NULL )
189    {
190        SHPGetInfo( hSHP, NULL, NULL,
191                    psTree->psRoot->adfBoundsMin, 
192                    psTree->psRoot->adfBoundsMax );
193    }
194
195/* -------------------------------------------------------------------- */
196/*      If we have a file, insert all it's shapes into the tree.        */
197/* -------------------------------------------------------------------- */
198    if( hSHP != NULL )
199    {
200        int     iShape, nShapeCount;
201       
202        SHPGetInfo( hSHP, &nShapeCount, NULL, NULL, NULL );
203
204        for( iShape = 0; iShape < nShapeCount; iShape++ )
205        {
206            SHPObject   *psShape;
207           
208            psShape = SHPReadObject( hSHP, iShape );
209            SHPTreeAddShapeId( psTree, psShape );
210            SHPDestroyObject( psShape );
211        }
212    }       
213
214    return psTree;
215}
216
217/************************************************************************/
218/*                         SHPDestroyTreeNode()                         */
219/************************************************************************/
220
221static void SHPDestroyTreeNode( SHPTreeNode * psTreeNode )
222
223{
224    int         i;
225   
226    for( i = 0; i < psTreeNode->nSubNodes; i++ )
227    {
228        if( psTreeNode->apsSubNode[i] != NULL )
229            SHPDestroyTreeNode( psTreeNode->apsSubNode[i] );
230    }
231   
232    if( psTreeNode->panShapeIds != NULL )
233        free( psTreeNode->panShapeIds );
234
235    if( psTreeNode->papsShapeObj != NULL )
236    {
237        for( i = 0; i < psTreeNode->nShapeCount; i++ )
238        {
239            if( psTreeNode->papsShapeObj[i] != NULL )
240                SHPDestroyObject( psTreeNode->papsShapeObj[i] );
241        }
242
243        free( psTreeNode->papsShapeObj );
244    }
245
246    free( psTreeNode );
247}
248
249/************************************************************************/
250/*                           SHPDestroyTree()                           */
251/************************************************************************/
252
253void SHPAPI_CALL
254SHPDestroyTree( SHPTree * psTree )
255
256{
257    SHPDestroyTreeNode( psTree->psRoot );
258    free( psTree );
259}
260
261/************************************************************************/
262/*                       SHPCheckBoundsOverlap()                        */
263/*                                                                      */
264/*      Do the given boxes overlap at all?                              */
265/************************************************************************/
266
267int SHPAPI_CALL
268SHPCheckBoundsOverlap( double * padfBox1Min, double * padfBox1Max,
269                       double * padfBox2Min, double * padfBox2Max,
270                       int nDimension )
271
272{
273    int         iDim;
274
275    for( iDim = 0; iDim < nDimension; iDim++ )
276    {
277        if( padfBox2Max[iDim] < padfBox1Min[iDim] )
278            return FALSE;
279       
280        if( padfBox1Max[iDim] < padfBox2Min[iDim] )
281            return FALSE;
282    }
283
284    return TRUE;
285}
286
287/************************************************************************/
288/*                      SHPCheckObjectContained()                       */
289/*                                                                      */
290/*      Does the given shape fit within the indicated extents?          */
291/************************************************************************/
292
293static int SHPCheckObjectContained( SHPObject * psObject, int nDimension,
294                           double * padfBoundsMin, double * padfBoundsMax )
295
296{
297    if( psObject->dfXMin < padfBoundsMin[0]
298        || psObject->dfXMax > padfBoundsMax[0] )
299        return FALSE;
300   
301    if( psObject->dfYMin < padfBoundsMin[1]
302        || psObject->dfYMax > padfBoundsMax[1] )
303        return FALSE;
304
305    if( nDimension == 2 )
306        return TRUE;
307   
308    if( psObject->dfZMin < padfBoundsMin[2]
309        || psObject->dfZMax < padfBoundsMax[2] )
310        return FALSE;
311       
312    if( nDimension == 3 )
313        return TRUE;
314
315    if( psObject->dfMMin < padfBoundsMin[3]
316        || psObject->dfMMax < padfBoundsMax[3] )
317        return FALSE;
318
319    return TRUE;
320}
321
322/************************************************************************/
323/*                         SHPTreeSplitBounds()                         */
324/*                                                                      */
325/*      Split a region into two subregion evenly, cutting along the     */
326/*      longest dimension.                                              */
327/************************************************************************/
328
329void SHPAPI_CALL
330SHPTreeSplitBounds( double *padfBoundsMinIn, double *padfBoundsMaxIn,
331                    double *padfBoundsMin1, double * padfBoundsMax1,
332                    double *padfBoundsMin2, double * padfBoundsMax2 )
333
334{
335/* -------------------------------------------------------------------- */
336/*      The output bounds will be very similar to the input bounds,     */
337/*      so just copy over to start.                                     */
338/* -------------------------------------------------------------------- */
339    memcpy( padfBoundsMin1, padfBoundsMinIn, sizeof(double) * 4 );
340    memcpy( padfBoundsMax1, padfBoundsMaxIn, sizeof(double) * 4 );
341    memcpy( padfBoundsMin2, padfBoundsMinIn, sizeof(double) * 4 );
342    memcpy( padfBoundsMax2, padfBoundsMaxIn, sizeof(double) * 4 );
343   
344/* -------------------------------------------------------------------- */
345/*      Split in X direction.                                           */
346/* -------------------------------------------------------------------- */
347    if( (padfBoundsMaxIn[0] - padfBoundsMinIn[0])
348                                > (padfBoundsMaxIn[1] - padfBoundsMinIn[1]) )
349    {
350        double  dfRange = padfBoundsMaxIn[0] - padfBoundsMinIn[0];
351
352        padfBoundsMax1[0] = padfBoundsMinIn[0] + dfRange * SHP_SPLIT_RATIO;
353        padfBoundsMin2[0] = padfBoundsMaxIn[0] - dfRange * SHP_SPLIT_RATIO;
354    }
355
356/* -------------------------------------------------------------------- */
357/*      Otherwise split in Y direction.                                 */
358/* -------------------------------------------------------------------- */
359    else
360    {
361        double  dfRange = padfBoundsMaxIn[1] - padfBoundsMinIn[1];
362
363        padfBoundsMax1[1] = padfBoundsMinIn[1] + dfRange * SHP_SPLIT_RATIO;
364        padfBoundsMin2[1] = padfBoundsMaxIn[1] - dfRange * SHP_SPLIT_RATIO;
365    }
366}
367
368/************************************************************************/
369/*                       SHPTreeNodeAddShapeId()                        */
370/************************************************************************/
371
372static int
373SHPTreeNodeAddShapeId( SHPTreeNode * psTreeNode, SHPObject * psObject,
374                       int nMaxDepth, int nDimension )
375
376{
377    int         i;
378   
379/* -------------------------------------------------------------------- */
380/*      If there are subnodes, then consider wiether this object        */
381/*      will fit in them.                                               */
382/* -------------------------------------------------------------------- */
383    if( nMaxDepth > 1 && psTreeNode->nSubNodes > 0 )
384    {
385        for( i = 0; i < psTreeNode->nSubNodes; i++ )
386        {
387            if( SHPCheckObjectContained(psObject, nDimension,
388                                      psTreeNode->apsSubNode[i]->adfBoundsMin,
389                                      psTreeNode->apsSubNode[i]->adfBoundsMax))
390            {
391                return SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[i],
392                                              psObject, nMaxDepth-1,
393                                              nDimension );
394            }
395        }
396    }
397
398/* -------------------------------------------------------------------- */
399/*      Otherwise, consider creating four subnodes if could fit into    */
400/*      them, and adding to the appropriate subnode.                    */
401/* -------------------------------------------------------------------- */
402#if MAX_SUBNODE == 4
403    else if( nMaxDepth > 1 && psTreeNode->nSubNodes == 0 )
404    {
405        double  adfBoundsMinH1[4], adfBoundsMaxH1[4];
406        double  adfBoundsMinH2[4], adfBoundsMaxH2[4];
407        double  adfBoundsMin1[4], adfBoundsMax1[4];
408        double  adfBoundsMin2[4], adfBoundsMax2[4];
409        double  adfBoundsMin3[4], adfBoundsMax3[4];
410        double  adfBoundsMin4[4], adfBoundsMax4[4];
411
412        SHPTreeSplitBounds( psTreeNode->adfBoundsMin,
413                            psTreeNode->adfBoundsMax,
414                            adfBoundsMinH1, adfBoundsMaxH1,
415                            adfBoundsMinH2, adfBoundsMaxH2 );
416
417        SHPTreeSplitBounds( adfBoundsMinH1, adfBoundsMaxH1,
418                            adfBoundsMin1, adfBoundsMax1,
419                            adfBoundsMin2, adfBoundsMax2 );
420
421        SHPTreeSplitBounds( adfBoundsMinH2, adfBoundsMaxH2,
422                            adfBoundsMin3, adfBoundsMax3,
423                            adfBoundsMin4, adfBoundsMax4 );
424
425        if( SHPCheckObjectContained(psObject, nDimension,
426                                    adfBoundsMin1, adfBoundsMax1)
427            || SHPCheckObjectContained(psObject, nDimension,
428                                    adfBoundsMin2, adfBoundsMax2)
429            || SHPCheckObjectContained(psObject, nDimension,
430                                    adfBoundsMin3, adfBoundsMax3)
431            || SHPCheckObjectContained(psObject, nDimension,
432                                    adfBoundsMin4, adfBoundsMax4) )
433        {
434            psTreeNode->nSubNodes = 4;
435            psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,
436                                                           adfBoundsMax1 );
437            psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,
438                                                           adfBoundsMax2 );
439            psTreeNode->apsSubNode[2] = SHPTreeNodeCreate( adfBoundsMin3,
440                                                           adfBoundsMax3 );
441            psTreeNode->apsSubNode[3] = SHPTreeNodeCreate( adfBoundsMin4,
442                                                           adfBoundsMax4 );
443
444            /* recurse back on this node now that it has subnodes */
445            return( SHPTreeNodeAddShapeId( psTreeNode, psObject,
446                                           nMaxDepth, nDimension ) );
447        }
448    }
449#endif /* MAX_SUBNODE == 4 */
450
451/* -------------------------------------------------------------------- */
452/*      Otherwise, consider creating two subnodes if could fit into     */
453/*      them, and adding to the appropriate subnode.                    */
454/* -------------------------------------------------------------------- */
455#if MAX_SUBNODE == 2
456    else if( nMaxDepth > 1 && psTreeNode->nSubNodes == 0 )
457    {
458        double  adfBoundsMin1[4], adfBoundsMax1[4];
459        double  adfBoundsMin2[4], adfBoundsMax2[4];
460
461        SHPTreeSplitBounds( psTreeNode->adfBoundsMin, psTreeNode->adfBoundsMax,
462                            adfBoundsMin1, adfBoundsMax1,
463                            adfBoundsMin2, adfBoundsMax2 );
464
465        if( SHPCheckObjectContained(psObject, nDimension,
466                                 adfBoundsMin1, adfBoundsMax1))
467        {
468            psTreeNode->nSubNodes = 2;
469            psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,
470                                                           adfBoundsMax1 );
471            psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,
472                                                           adfBoundsMax2 );
473
474            return( SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[0], psObject,
475                                           nMaxDepth - 1, nDimension ) );
476        }
477        else if( SHPCheckObjectContained(psObject, nDimension,
478                                         adfBoundsMin2, adfBoundsMax2) )
479        {
480            psTreeNode->nSubNodes = 2;
481            psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,
482                                                           adfBoundsMax1 );
483            psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,
484                                                           adfBoundsMax2 );
485
486            return( SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[1], psObject,
487                                           nMaxDepth - 1, nDimension ) );
488        }
489    }
490#endif /* MAX_SUBNODE == 2 */
491
492/* -------------------------------------------------------------------- */
493/*      If none of that worked, just add it to this nodes list.         */
494/* -------------------------------------------------------------------- */
495    psTreeNode->nShapeCount++;
496
497    psTreeNode->panShapeIds =
498        SfRealloc( psTreeNode->panShapeIds,
499                   sizeof(int) * psTreeNode->nShapeCount );
500    psTreeNode->panShapeIds[psTreeNode->nShapeCount-1] = psObject->nShapeId;
501
502    if( psTreeNode->papsShapeObj != NULL )
503    {
504        psTreeNode->papsShapeObj =
505            SfRealloc( psTreeNode->papsShapeObj,
506                       sizeof(void *) * psTreeNode->nShapeCount );
507        psTreeNode->papsShapeObj[psTreeNode->nShapeCount-1] = NULL;
508    }
509
510    return TRUE;
511}
512
513/************************************************************************/
514/*                         SHPTreeAddShapeId()                          */
515/*                                                                      */
516/*      Add a shape to the tree, but don't keep a pointer to the        */
517/*      object data, just keep the shapeid.                             */
518/************************************************************************/
519
520int SHPAPI_CALL
521SHPTreeAddShapeId( SHPTree * psTree, SHPObject * psObject )
522
523{
524    return( SHPTreeNodeAddShapeId( psTree->psRoot, psObject,
525                                   psTree->nMaxDepth, psTree->nDimension ) );
526}
527
528/************************************************************************/
529/*                      SHPTreeCollectShapesIds()                       */
530/*                                                                      */
531/*      Work function implementing SHPTreeFindLikelyShapes() on a       */
532/*      tree node by tree node basis.                                   */
533/************************************************************************/
534
535void SHPAPI_CALL
536SHPTreeCollectShapeIds( SHPTree *hTree, SHPTreeNode * psTreeNode,
537                        double * padfBoundsMin, double * padfBoundsMax,
538                        int * pnShapeCount, int * pnMaxShapes,
539                        int ** ppanShapeList )
540
541{
542    int         i;
543   
544/* -------------------------------------------------------------------- */
545/*      Does this node overlap the area of interest at all?  If not,    */
546/*      return without adding to the list at all.                       */
547/* -------------------------------------------------------------------- */
548    if( !SHPCheckBoundsOverlap( psTreeNode->adfBoundsMin,
549                                psTreeNode->adfBoundsMax,
550                                padfBoundsMin,
551                                padfBoundsMax,
552                                hTree->nDimension ) )
553        return;
554
555/* -------------------------------------------------------------------- */
556/*      Grow the list to hold the shapes on this node.                  */
557/* -------------------------------------------------------------------- */
558    if( *pnShapeCount + psTreeNode->nShapeCount > *pnMaxShapes )
559    {
560        *pnMaxShapes = (*pnShapeCount + psTreeNode->nShapeCount) * 2 + 20;
561        *ppanShapeList = (int *)
562            SfRealloc(*ppanShapeList,sizeof(int) * *pnMaxShapes);
563    }
564
565/* -------------------------------------------------------------------- */
566/*      Add the local nodes shapeids to the list.                       */
567/* -------------------------------------------------------------------- */
568    for( i = 0; i < psTreeNode->nShapeCount; i++ )
569    {
570        (*ppanShapeList)[(*pnShapeCount)++] = psTreeNode->panShapeIds[i];
571    }
572   
573/* -------------------------------------------------------------------- */
574/*      Recurse to subnodes if they exist.                              */
575/* -------------------------------------------------------------------- */
576    for( i = 0; i < psTreeNode->nSubNodes; i++ )
577    {
578        if( psTreeNode->apsSubNode[i] != NULL )
579            SHPTreeCollectShapeIds( hTree, psTreeNode->apsSubNode[i],
580                                    padfBoundsMin, padfBoundsMax,
581                                    pnShapeCount, pnMaxShapes,
582                                    ppanShapeList );
583    }
584}
585
586/************************************************************************/
587/*                      SHPTreeFindLikelyShapes()                       */
588/*                                                                      */
589/*      Find all shapes within tree nodes for which the tree node       */
590/*      bounding box overlaps the search box.  The return value is      */
591/*      an array of shapeids terminated by a -1.  The shapeids will     */
592/*      be in order, as hopefully this will result in faster (more      */
593/*      sequential) reading from the file.                              */
594/************************************************************************/
595
596/* helper for qsort */
597static int
598compare_ints( const void * a, const void * b)
599{
600    return (*(int*)a) - (*(int*)b);
601}
602
603int SHPAPI_CALL1(*)
604SHPTreeFindLikelyShapes( SHPTree * hTree,
605                         double * padfBoundsMin, double * padfBoundsMax,
606                         int * pnShapeCount )
607
608{
609    int *panShapeList=NULL, nMaxShapes = 0;
610
611/* -------------------------------------------------------------------- */
612/*      Perform the search by recursive descent.                        */
613/* -------------------------------------------------------------------- */
614    *pnShapeCount = 0;
615
616    SHPTreeCollectShapeIds( hTree, hTree->psRoot,
617                            padfBoundsMin, padfBoundsMax,
618                            pnShapeCount, &nMaxShapes,
619                            &panShapeList );
620
621/* -------------------------------------------------------------------- */
622/*      Sort the id array                                               */
623/* -------------------------------------------------------------------- */
624
625    qsort(panShapeList, *pnShapeCount, sizeof(int), compare_ints);
626
627    return panShapeList;
628}
629
630/************************************************************************/
631/*                          SHPTreeNodeTrim()                           */
632/*                                                                      */
633/*      This is the recurve version of SHPTreeTrimExtraNodes() that     */
634/*      walks the tree cleaning it up.                                  */
635/************************************************************************/
636
637static int SHPTreeNodeTrim( SHPTreeNode * psTreeNode )
638
639{
640    int         i;
641
642/* -------------------------------------------------------------------- */
643/*      Trim subtrees, and free subnodes that come back empty.          */
644/* -------------------------------------------------------------------- */
645    for( i = 0; i < psTreeNode->nSubNodes; i++ )
646    {
647        if( SHPTreeNodeTrim( psTreeNode->apsSubNode[i] ) )
648        {
649            SHPDestroyTreeNode( psTreeNode->apsSubNode[i] );
650
651            psTreeNode->apsSubNode[i] =
652                psTreeNode->apsSubNode[psTreeNode->nSubNodes-1];
653
654            psTreeNode->nSubNodes--;
655
656            i--; /* process the new occupant of this subnode entry */
657        }
658    }
659
660/* -------------------------------------------------------------------- */
661/*      We should be trimmed if we have no subnodes, and no shapes.     */
662/* -------------------------------------------------------------------- */
663    return( psTreeNode->nSubNodes == 0 && psTreeNode->nShapeCount == 0 );
664}
665
666/************************************************************************/
667/*                       SHPTreeTrimExtraNodes()                        */
668/*                                                                      */
669/*      Trim empty nodes from the tree.  Note that we never trim an     */
670/*      empty root node.                                                */
671/************************************************************************/
672
673void SHPAPI_CALL
674SHPTreeTrimExtraNodes( SHPTree * hTree )
675
676{
677    SHPTreeNodeTrim( hTree->psRoot );
678}
679
Note: See TracBrowser for help on using the repository browser.