shptree.c

用于读取TAB、MIF、SHP文件的类

        {
            SHPDestroyTreeNode( psTreeNode->apsSubNode[i] );

            psTreeNode->apsSubNode[i] =
                psTreeNode->apsSubNode[psTreeNode->nSubNodes-1];

            psTreeNode->nSubNodes--;

            i--; /* process the new occupant of this subnode entry */
        }
    }

/* -------------------------------------------------------------------- */
/*      We should be trimmed if we have no subnodes, and no shapes.     */
/* -------------------------------------------------------------------- */
    return( psTreeNode->nSubNodes == 0 && psTreeNode->nShapeCount == 0 );
}

/************************************************************************/
/*                       SHPTreeTrimExtraNodes()                        */
/*                                                                      */
/*      Trim empty nodes from the tree.  Note that we never trim an     */
/*      empty root node.                                                */
/************************************************************************/

void SHPAPI_CALL
SHPTreeTrimExtraNodes( SHPTree * hTree )

{
    SHPTreeNodeTrim( hTree->psRoot );
}

/************************************************************************/
/*                              SwapWord()                              */
/*                                                                      */
/*      Swap a 2, 4 or 8 byte word.                                     */
/************************************************************************/

static void SwapWord( int length, void * wordP )

{
    int		i;
    unsigned char	temp;

    for( i=0; i < length/2; i++ )
    {
	temp = ((unsigned char *) wordP)[i];
	((unsigned char *)wordP)[i] = ((unsigned char *) wordP)[length-i-1];
	((unsigned char *) wordP)[length-i-1] = temp;
    }
}

/************************************************************************/
/*                       SHPSearchDiskTreeNode()                        */
/************************************************************************/

static int
SHPSearchDiskTreeNode( FILE *fp, double *padfBoundsMin, double *padfBoundsMax,
                       int **ppanResultBuffer, int *pnBufferMax, 
                       int *pnResultCount, int bNeedSwap )

{
    int i;
    int offset;
    int numshapes, numsubnodes;
    double adfNodeBoundsMin[2], adfNodeBoundsMax[2];

/* -------------------------------------------------------------------- */
/*      Read and unswap first part of node info.                        */
/* -------------------------------------------------------------------- */
    fread( &offset, 4, 1, fp );
    if ( bNeedSwap ) SwapWord ( 4, &offset );

    fread( adfNodeBoundsMin, sizeof(double), 2, fp );
    fread( adfNodeBoundsMax, sizeof(double), 2, fp );
    if ( bNeedSwap )
    {
        SwapWord( 8, adfNodeBoundsMin + 0 );
        SwapWord( 8, adfNodeBoundsMin + 1 );
        SwapWord( 8, adfNodeBoundsMax + 0 );
        SwapWord( 8, adfNodeBoundsMax + 1 );
    }
      
    fread( &numshapes, 4, 1, fp );
    if ( bNeedSwap ) SwapWord ( 4, &numshapes );

/* -------------------------------------------------------------------- */
/*      If we don't overlap this node at all, we can just fseek()       */
/*      pass this node info and all subnodes.                           */
/* -------------------------------------------------------------------- */
    if( !SHPCheckBoundsOverlap( adfNodeBoundsMin, adfNodeBoundsMax, 
                                padfBoundsMin, padfBoundsMax, 2 ) )
    {
        offset += numshapes*sizeof(int) + sizeof(int);
        fseek(fp, offset, SEEK_CUR);
        return TRUE;
    }

/* -------------------------------------------------------------------- */
/*      Add all the shapeids at this node to our list.                  */
/* -------------------------------------------------------------------- */
    if(numshapes > 0) 
    {
        if( *pnResultCount + numshapes > *pnBufferMax )
        {
            *pnBufferMax = (int) ((*pnResultCount + numshapes + 100) * 1.25);
            *ppanResultBuffer = (int *) 
                SfRealloc( *ppanResultBuffer, *pnBufferMax * sizeof(int) );
        }

        fread( *ppanResultBuffer + *pnResultCount, 
               sizeof(int), numshapes, fp );

        if (bNeedSwap )
        {
            for( i=0; i<numshapes; i++ )
                SwapWord( 4, *ppanResultBuffer + *pnResultCount + i );
        }

        *pnResultCount += numshapes; 
    } 

/* -------------------------------------------------------------------- */
/*      Process the subnodes.                                           */
/* -------------------------------------------------------------------- */
    fread( &numsubnodes, 4, 1, fp );
    if ( bNeedSwap  ) SwapWord ( 4, &numsubnodes );

    for(i=0; i<numsubnodes; i++)
    {
        if( !SHPSearchDiskTreeNode( fp, padfBoundsMin, padfBoundsMax, 
                                    ppanResultBuffer, pnBufferMax, 
                                    pnResultCount, bNeedSwap ) )
            return FALSE;
    }

    return TRUE;
}

/************************************************************************/
/*                         SHPSearchDiskTree()                          */
/************************************************************************/

int SHPAPI_CALL1(*) 
SHPSearchDiskTree( FILE *fp, 
                   double *padfBoundsMin, double *padfBoundsMax,
                   int *pnShapeCount )

{
    int i, bNeedSwap, nBufferMax = 0;
    unsigned char abyBuf[16];
    int *panResultBuffer = NULL;

    *pnShapeCount = 0;

/* -------------------------------------------------------------------- */
/*	Establish the byte order on this machine.	  	        */
/* -------------------------------------------------------------------- */
    i = 1;
    if( *((unsigned char *) &i) == 1 )
        bBigEndian = FALSE;
    else
        bBigEndian = TRUE;

/* -------------------------------------------------------------------- */
/*      Read the header.                                                */
/* -------------------------------------------------------------------- */
    fseek( fp, 0, SEEK_SET );
    fread( abyBuf, 16, 1, fp );

    if( memcmp( abyBuf, "SQT", 3 ) != 0 )
        return NULL;

    if( (abyBuf[3] == 2 && bBigEndian)
        || (abyBuf[3] == 1 && !bBigEndian) )
        bNeedSwap = FALSE;
    else
        bNeedSwap = TRUE;

/* -------------------------------------------------------------------- */
/*      Search through root node and it's decendents.                   */
/* -------------------------------------------------------------------- */
    if( !SHPSearchDiskTreeNode( fp, padfBoundsMin, padfBoundsMax, 
                                &panResultBuffer, &nBufferMax, 
                                pnShapeCount, bNeedSwap ) )
    {
        if( panResultBuffer != NULL )
            free( panResultBuffer );
        *pnShapeCount = 0;
        return NULL;
    }
/* -------------------------------------------------------------------- */
/*      Sort the id array                                               */
/* -------------------------------------------------------------------- */
    qsort(panResultBuffer, *pnShapeCount, sizeof(int), compare_ints);
    
    return panResultBuffer;
}

/************************************************************************/
/*                        SHPGetSubNodeOffset()                         */
/*                                                                      */
/*      Determine how big all the subnodes of this node (and their      */
/*      children) will be.  This will allow disk based searchers to     */
/*      seek past them all efficiently.                                 */
/************************************************************************/

static int SHPGetSubNodeOffset( SHPTreeNode *node) 
{
    int i;
    long offset=0;

    for(i=0; i<node->nSubNodes; i++ ) 
    {
        if(node->apsSubNode[i]) 
        {
            offset += 4*sizeof(double) 
                + (node->apsSubNode[i]->nShapeCount+3)*sizeof(int);
            offset += SHPGetSubNodeOffset(node->apsSubNode[i]);
        }
    }

    return(offset);
}

/************************************************************************/
/*                          SHPWriteTreeNode()                          */
/************************************************************************/

static void SHPWriteTreeNode( FILE *fp, SHPTreeNode *node) 
{
    int i,j;
    int offset;
    unsigned char *pabyRec = NULL;

    offset = SHPGetSubNodeOffset(node);
  
    pabyRec = (unsigned char *) 
        malloc(sizeof(double) * 4
               + (3 * sizeof(int)) + (node->nShapeCount * sizeof(int)) );

    memcpy( pabyRec, &offset, 4);

    /* minx, miny, maxx, maxy */
    memcpy( pabyRec+ 4, node->adfBoundsMin+0, sizeof(double) );
    memcpy( pabyRec+12, node->adfBoundsMin+1, sizeof(double) );
    memcpy( pabyRec+20, node->adfBoundsMax+0, sizeof(double) );
    memcpy( pabyRec+28, node->adfBoundsMax+1, sizeof(double) );

    memcpy( pabyRec+36, &node->nShapeCount, 4);
    j = node->nShapeCount * sizeof(int);
    memcpy( pabyRec+40, node->panShapeIds, j);
    memcpy( pabyRec+j+40, &node->nSubNodes, 4);

    fwrite( pabyRec, 44+j, 1, fp );
    free (pabyRec);
  
    for(i=0; i<node->nSubNodes; i++ ) 
    {
        if(node->apsSubNode[i])
            SHPWriteTreeNode( fp, node->apsSubNode[i]);
    }
}

/************************************************************************/
/*                            SHPWriteTree()                            */
/************************************************************************/

int SHPWriteTree(SHPTree *tree, const char *filename )
{
    char		signature[4] = "SQT";
    int		        i;
    char		abyBuf[32];
    FILE                *fp;
  
/* -------------------------------------------------------------------- */
/*      Open the output file.                                           */
/* -------------------------------------------------------------------- */
    fp = fopen(filename, "wb");
    if( fp == NULL ) 
    {
        return FALSE;
    }

/* -------------------------------------------------------------------- */
/*	Establish the byte order on this machine.	  	        */
/* -------------------------------------------------------------------- */
    i = 1;
    if( *((unsigned char *) &i) == 1 )
        bBigEndian = FALSE;
    else
        bBigEndian = TRUE;
  
/* -------------------------------------------------------------------- */
/*      Write the header.                                               */
/* -------------------------------------------------------------------- */
    memcpy( abyBuf+0, signature, 3 );
    
    if( bBigEndian )
        abyBuf[3] = 2; /* New MSB */
    else
        abyBuf[3] = 1; /* New LSB */

    abyBuf[4] = 1; /* version */
    abyBuf[5] = 0; /* next 3 reserved */
    abyBuf[6] = 0;
    abyBuf[7] = 0;

    fwrite( abyBuf, 8, 1, fp );

    fwrite( &(tree->nTotalCount), 4, 1, fp );

    /* write maxdepth */

    fwrite( &(tree->nMaxDepth), 4, 1, fp );

/* -------------------------------------------------------------------- */
/*      Write all the nodes "in order".                                 */
/* -------------------------------------------------------------------- */

    SHPWriteTreeNode( fp, tree->psRoot );  
    
    fclose( fp );

    return TRUE;
}