/*                         SHPTreeSplitBounds()                         *//*                                                                      *//*      Split a region into two subregion evenly, cutting along the     *//*      longest dimension.                                              *//************************************************************************/void SHPAPI_CALLSHPTreeSplitBounds( double *padfBoundsMinIn, double *padfBoundsMaxIn,                    double *padfBoundsMin1, double * padfBoundsMax1,                    double *padfBoundsMin2, double * padfBoundsMax2 ){/* -------------------------------------------------------------------- *//*      The output bounds will be very similar to the input bounds,     *//*      so just copy over to start.                                     *//* -------------------------------------------------------------------- */    memcpy( padfBoundsMin1, padfBoundsMinIn, sizeof(double) * 4 );    memcpy( padfBoundsMax1, padfBoundsMaxIn, sizeof(double) * 4 );    memcpy( padfBoundsMin2, padfBoundsMinIn, sizeof(double) * 4 );    memcpy( padfBoundsMax2, padfBoundsMaxIn, sizeof(double) * 4 );    /* -------------------------------------------------------------------- *//*      Split in X direction.                                           *//* -------------------------------------------------------------------- */    if( (padfBoundsMaxIn[0] - padfBoundsMinIn[0])        			> (padfBoundsMaxIn[1] - padfBoundsMinIn[1]) )    {        double	dfRange = padfBoundsMaxIn[0] - padfBoundsMinIn[0];        padfBoundsMax1[0] = padfBoundsMinIn[0] + dfRange * SHP_SPLIT_RATIO;        padfBoundsMin2[0] = padfBoundsMaxIn[0] - dfRange * SHP_SPLIT_RATIO;    }/* -------------------------------------------------------------------- *//*      Otherwise split in Y direction.                                 *//* -------------------------------------------------------------------- */    else    {        double	dfRange = padfBoundsMaxIn[1] - padfBoundsMinIn[1];        padfBoundsMax1[1] = padfBoundsMinIn[1] + dfRange * SHP_SPLIT_RATIO;        padfBoundsMin2[1] = padfBoundsMaxIn[1] - dfRange * SHP_SPLIT_RATIO;    }}/************************************************************************//*                       SHPTreeNodeAddShapeId()                        *//************************************************************************/static intSHPTreeNodeAddShapeId( SHPTreeNode * psTreeNode, SHPObject * psObject,                       int nMaxDepth, int nDimension ){    int		i;    /* -------------------------------------------------------------------- *//*      If there are subnodes, then consider wiether this object        *//*      will fit in them.                                               *//* -------------------------------------------------------------------- */    if( nMaxDepth > 1 && psTreeNode->nSubNodes > 0 )    {        for( i = 0; i < psTreeNode->nSubNodes; i++ )        {            if( SHPCheckObjectContained(psObject, nDimension,                                      psTreeNode->apsSubNode[i]->adfBoundsMin,                                      psTreeNode->apsSubNode[i]->adfBoundsMax))            {                return SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[i],                                              psObject, nMaxDepth-1,                                              nDimension );            }        }    }/* -------------------------------------------------------------------- *//*      Otherwise, consider creating four subnodes if could fit into    *//*      them, and adding to the appropriate subnode.                    *//* -------------------------------------------------------------------- */#if MAX_SUBNODE == 4    else if( nMaxDepth > 1 && psTreeNode->nSubNodes == 0 )    {        double	adfBoundsMinH1[4], adfBoundsMaxH1[4];        double	adfBoundsMinH2[4], adfBoundsMaxH2[4];        double	adfBoundsMin1[4], adfBoundsMax1[4];        double	adfBoundsMin2[4], adfBoundsMax2[4];        double	adfBoundsMin3[4], adfBoundsMax3[4];        double	adfBoundsMin4[4], adfBoundsMax4[4];        SHPTreeSplitBounds( psTreeNode->adfBoundsMin,                            psTreeNode->adfBoundsMax,                            adfBoundsMinH1, adfBoundsMaxH1,                            adfBoundsMinH2, adfBoundsMaxH2 );        SHPTreeSplitBounds( adfBoundsMinH1, adfBoundsMaxH1,                            adfBoundsMin1, adfBoundsMax1,                            adfBoundsMin2, adfBoundsMax2 );        SHPTreeSplitBounds( adfBoundsMinH2, adfBoundsMaxH2,                            adfBoundsMin3, adfBoundsMax3,                            adfBoundsMin4, adfBoundsMax4 );        if( SHPCheckObjectContained(psObject, nDimension,                                    adfBoundsMin1, adfBoundsMax1)            || SHPCheckObjectContained(psObject, nDimension,                                    adfBoundsMin2, adfBoundsMax2)            || SHPCheckObjectContained(psObject, nDimension,                                    adfBoundsMin3, adfBoundsMax3)            || SHPCheckObjectContained(psObject, nDimension,                                    adfBoundsMin4, adfBoundsMax4) )        {            psTreeNode->nSubNodes = 4;            psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,                                                           adfBoundsMax1 );            psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,                                                           adfBoundsMax2 );            psTreeNode->apsSubNode[2] = SHPTreeNodeCreate( adfBoundsMin3,                                                           adfBoundsMax3 );            psTreeNode->apsSubNode[3] = SHPTreeNodeCreate( adfBoundsMin4,                                                           adfBoundsMax4 );            /* recurse back on this node now that it has subnodes */            return( SHPTreeNodeAddShapeId( psTreeNode, psObject,                                           nMaxDepth, nDimension ) );        }    }#endif /* MAX_SUBNODE == 4 *//* -------------------------------------------------------------------- *//*      Otherwise, consider creating two subnodes if could fit into     *//*      them, and adding to the appropriate subnode.                    *//* -------------------------------------------------------------------- */#if MAX_SUBNODE == 2    else if( nMaxDepth > 1 && psTreeNode->nSubNodes == 0 )    {        double	adfBoundsMin1[4], adfBoundsMax1[4];        double	adfBoundsMin2[4], adfBoundsMax2[4];        SHPTreeSplitBounds( psTreeNode->adfBoundsMin, psTreeNode->adfBoundsMax,                            adfBoundsMin1, adfBoundsMax1,                            adfBoundsMin2, adfBoundsMax2 );        if( SHPCheckObjectContained(psObject, nDimension,                                 adfBoundsMin1, adfBoundsMax1))        {            psTreeNode->nSubNodes = 2;            psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,                                                           adfBoundsMax1 );            psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,                                                           adfBoundsMax2 );            return( SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[0], psObject,                                           nMaxDepth - 1, nDimension ) );        }        else if( SHPCheckObjectContained(psObject, nDimension,                                         adfBoundsMin2, adfBoundsMax2) )        {            psTreeNode->nSubNodes = 2;            psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,                                                           adfBoundsMax1 );            psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,                                                           adfBoundsMax2 );            return( SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[1], psObject,                                           nMaxDepth - 1, nDimension ) );        }    }#endif /* MAX_SUBNODE == 2 *//* -------------------------------------------------------------------- *//*      If none of that worked, just add it to this nodes list.         *//* -------------------------------------------------------------------- */    psTreeNode->nShapeCount++;    psTreeNode->panShapeIds = (int *)         SfRealloc( psTreeNode->panShapeIds,                   sizeof(int) * psTreeNode->nShapeCount );    psTreeNode->panShapeIds[psTreeNode->nShapeCount-1] = psObject->nShapeId;    if( psTreeNode->papsShapeObj != NULL )    {        psTreeNode->papsShapeObj = (SHPObject **)            SfRealloc( psTreeNode->papsShapeObj,                       sizeof(void *) * psTreeNode->nShapeCount );        psTreeNode->papsShapeObj[psTreeNode->nShapeCount-1] = NULL;    }    return TRUE;}/************************************************************************//*                         SHPTreeAddShapeId()                          *//*                                                                      *//*      Add a shape to the tree, but don't keep a pointer to the        *//*      object data, just keep the shapeid.                             *//************************************************************************/int SHPAPI_CALLSHPTreeAddShapeId( SHPTree * psTree, SHPObject * psObject ){    psTree->nTotalCount++;    return( SHPTreeNodeAddShapeId( psTree->psRoot, psObject,                                   psTree->nMaxDepth, psTree->nDimension ) );}/************************************************************************//*                      SHPTreeCollectShapesIds()                       *//*                                                                      *//*      Work function implementing SHPTreeFindLikelyShapes() on a       *//*      tree node by tree node basis.                                   *//************************************************************************/void SHPAPI_CALLSHPTreeCollectShapeIds( SHPTree *hTree, SHPTreeNode * psTreeNode,                        double * padfBoundsMin, double * padfBoundsMax,                        int * pnShapeCount, int * pnMaxShapes,                        int ** ppanShapeList ){    int		i;    /* -------------------------------------------------------------------- *//*      Does this node overlap the area of interest at all?  If not,    *//*      return without adding to the list at all.                       *//* -------------------------------------------------------------------- */    if( !SHPCheckBoundsOverlap( psTreeNode->adfBoundsMin,                                psTreeNode->adfBoundsMax,                                padfBoundsMin,                                padfBoundsMax,                                hTree->nDimension ) )        return;/* -------------------------------------------------------------------- *//*      Grow the list to hold the shapes on this node.                  *//* -------------------------------------------------------------------- */    if( *pnShapeCount + psTreeNode->nShapeCount > *pnMaxShapes )    {        *pnMaxShapes = (*pnShapeCount + psTreeNode->nShapeCount) * 2 + 20;        *ppanShapeList = (int *)            SfRealloc(*ppanShapeList,sizeof(int) * *pnMaxShapes);    }/* -------------------------------------------------------------------- *//*      Add the local nodes shapeids to the list.                       *//* -------------------------------------------------------------------- */    for( i = 0; i < psTreeNode->nShapeCount; i++ )    {        (*ppanShapeList)[(*pnShapeCount)++] = psTreeNode->panShapeIds[i];    }    /* -------------------------------------------------------------------- *//*      Recurse to subnodes if they exist.                              *//* -------------------------------------------------------------------- */    for( i = 0; i < psTreeNode->nSubNodes; i++ )    {        if( psTreeNode->apsSubNode[i] != NULL )            SHPTreeCollectShapeIds( hTree, psTreeNode->apsSubNode[i],                                    padfBoundsMin, padfBoundsMax,                                    pnShapeCount, pnMaxShapes,                                    ppanShapeList );    }}/************************************************************************//*                      SHPTreeFindLikelyShapes()                       *//*                                                                      *//*      Find all shapes within tree nodes for which the tree node       *//*      bounding box overlaps the search box.  The return value is      *//*      an array of shapeids terminated by a -1.  The shapeids will     *//*      be in order, as hopefully this will result in faster (more      *//*      sequential) reading from the file.                              *//************************************************************************//* helper for qsort */static intcompare_ints( const void * a, const void * b){    return (*(int*)a) - (*(int*)b);}int SHPAPI_CALL1(*)SHPTreeFindLikelyShapes( SHPTree * hTree,                         double * padfBoundsMin, double * padfBoundsMax,                         int * pnShapeCount ){    int	*panShapeList=NULL, nMaxShapes = 0;/* -------------------------------------------------------------------- *//*      Perform the search by recursive descent.                        *//* -------------------------------------------------------------------- */    *pnShapeCount = 0;    SHPTreeCollectShapeIds( hTree, hTree->psRoot,                            padfBoundsMin, padfBoundsMax,                            pnShapeCount, &nMaxShapes,                            &panShapeList );/* -------------------------------------------------------------------- *//*      Sort the id array                                               *//* -------------------------------------------------------------------- */    qsort(panShapeList, *pnShapeCount, sizeof(int), compare_ints);    return panShapeList;}/************************************************************************//*                          SHPTreeNodeTrim()                           *//*                                                                      *//*      This is the recurve version of SHPTreeTrimExtraNodes() that     *//*      walks the tree cleaning it up.                                  *//************************************************************************/static int SHPTreeNodeTrim( SHPTreeNode * psTreeNode ){    int		i;/* -------------------------------------------------------------------- *//*      Trim subtrees, and free subnodes that come back empty.          *//* -------------------------------------------------------------------- */    for( i = 0; i < psTreeNode->nSubNodes; i++ )    {        if( SHPTreeNodeTrim( psTreeNode->apsSubNode[i] ) )