| 1 |
/******************************************************************************
|
| 2 |
* $Id: shptree.c,v 1.12 2008/11/12 15:39:50 fwarmerdam 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.12 2008/11/12 15:39:50 fwarmerdam
|
| 38 |
* improve safety in face of buggy .shp file.
|
| 39 |
*
|
| 40 |
* Revision 1.11 2007/10/27 03:31:14 fwarmerdam
|
| 41 |
* limit default depth of tree to 12 levels (gdal ticket #1594)
|
| 42 |
*
|
| 43 |
* Revision 1.10 2005/01/03 22:30:13 fwarmerdam
|
| 44 |
* added support for saved quadtrees
|
| 45 |
*
|
| 46 |
* Revision 1.9 2003/01/28 15:53:41 warmerda
|
| 47 |
* Avoid build warnings.
|
| 48 |
*
|
| 49 |
* Revision 1.8 2002/05/07 13:07:45 warmerda
|
| 50 |
* use qsort() - patch from Bernhard Herzog
|
| 51 |
*
|
| 52 |
* Revision 1.7 2002/01/15 14:36:07 warmerda
|
| 53 |
* updated email address
|
| 54 |
*
|
| 55 |
* Revision 1.6 2001/05/23 13:36:52 warmerda
|
| 56 |
* added use of SHPAPI_CALL
|
| 57 |
*
|
| 58 |
* Revision 1.5 1999/11/05 14:12:05 warmerda
|
| 59 |
* updated license terms
|
| 60 |
*
|
| 61 |
* Revision 1.4 1999/06/02 18:24:21 warmerda
|
| 62 |
* added trimming code
|
| 63 |
*
|
| 64 |
* Revision 1.3 1999/06/02 17:56:12 warmerda
|
| 65 |
* added quad'' subnode support for trees
|
| 66 |
*
|
| 67 |
* Revision 1.2 1999/05/18 19:11:11 warmerda
|
| 68 |
* Added example searching capability
|
| 69 |
*
|
| 70 |
* Revision 1.1 1999/05/18 17:49:20 warmerda
|
| 71 |
* New
|
| 72 |
*
|
| 73 |
*/
|
| 74 |
|
| 75 |
#include "shapefil.h"
|
| 76 |
|
| 77 |
#include <math.h>
|
| 78 |
#include <assert.h>
|
| 79 |
#include <stdlib.h>
|
| 80 |
#include <string.h>
|
| 81 |
#ifdef USE_CPL
|
| 82 |
#include <cpl_error.h>
|
| 83 |
#endif
|
| 84 |
|
| 85 |
#if 0
|
| 86 |
SHP_CVSID("$Id: shptree.c,v 1.12 2008/11/12 15:39:50 fwarmerdam Exp $")
|
| 87 |
#endif
|
| 88 |
|
| 89 |
#ifndef TRUE
|
| 90 |
# define TRUE 1
|
| 91 |
# define FALSE 0
|
| 92 |
#endif
|
| 93 |
|
| 94 |
static int bBigEndian = 0;
|
| 95 |
|
| 96 |
void SHPAPI_CALL SHPTreeSplitBounds( double *padfBoundsMinIn, double *padfBoundsMaxIn, double *padfBoundsMin1, double * padfBoundsMax1, double *padfBoundsMin2, double * padfBoundsMax2 );
|
| 97 |
void SHPAPI_CALL SHPTreeCollectShapeIds( SHPTree *hTree, SHPTreeNode * psTreeNode, double * padfBoundsMin, double * padfBoundsMax, int * pnShapeCount, int * pnMaxShapes, int ** ppanShapeList );
|
| 98 |
|
| 99 |
|
| 100 |
/* -------------------------------------------------------------------- */
|
| 101 |
/* If the following is 0.5, nodes will be split in half. If it */
|
| 102 |
/* is 0.6 then each subnode will contain 60% of the parent */
|
| 103 |
/* node, with 20% representing overlap. This can be help to */
|
| 104 |
/* prevent small objects on a boundary from shifting too high */
|
| 105 |
/* up the tree. */
|
| 106 |
/* -------------------------------------------------------------------- */
|
| 107 |
|
| 108 |
#define SHP_SPLIT_RATIO 0.55
|
| 109 |
|
| 110 |
/************************************************************************/
|
| 111 |
/* SfRealloc() */
|
| 112 |
/* */
|
| 113 |
/* A realloc cover function that will access a NULL pointer as */
|
| 114 |
/* a valid input. */
|
| 115 |
/************************************************************************/
|
| 116 |
|
| 117 |
static void * SfRealloc( void * pMem, int nNewSize )
|
| 118 |
|
| 119 |
{
|
| 120 |
if( pMem == NULL )
|
| 121 |
return( (void *) malloc(nNewSize) );
|
| 122 |
else
|
| 123 |
return( (void *) realloc(pMem,nNewSize) );
|
| 124 |
}
|
| 125 |
|
| 126 |
/************************************************************************/
|
| 127 |
/* SHPTreeNodeInit() */
|
| 128 |
/* */
|
| 129 |
/* Initialize a tree node. */
|
| 130 |
/************************************************************************/
|
| 131 |
|
| 132 |
static SHPTreeNode *SHPTreeNodeCreate( double * padfBoundsMin,
|
| 133 |
double * padfBoundsMax )
|
| 134 |
|
| 135 |
{
|
| 136 |
SHPTreeNode *psTreeNode;
|
| 137 |
|
| 138 |
psTreeNode = (SHPTreeNode *) malloc(sizeof(SHPTreeNode));
|
| 139 |
if( NULL == psTreeNode )
|
| 140 |
{
|
| 141 |
#ifdef USE_CPL
|
| 142 |
CPLError( CE_Fatal, CPLE_OutOfMemory, "Memory allocation failure");
|
| 143 |
#endif
|
| 144 |
return NULL;
|
| 145 |
}
|
| 146 |
|
| 147 |
psTreeNode->nShapeCount = 0;
|
| 148 |
psTreeNode->panShapeIds = NULL;
|
| 149 |
psTreeNode->papsShapeObj = NULL;
|
| 150 |
|
| 151 |
psTreeNode->nSubNodes = 0;
|
| 152 |
|
| 153 |
if( padfBoundsMin != NULL )
|
| 154 |
memcpy( psTreeNode->adfBoundsMin, padfBoundsMin, sizeof(double) * 4 );
|
| 155 |
|
| 156 |
if( padfBoundsMax != NULL )
|
| 157 |
memcpy( psTreeNode->adfBoundsMax, padfBoundsMax, sizeof(double) * 4 );
|
| 158 |
|
| 159 |
return psTreeNode;
|
| 160 |
}
|
| 161 |
|
| 162 |
|
| 163 |
/************************************************************************/
|
| 164 |
/* SHPCreateTree() */
|
| 165 |
/************************************************************************/
|
| 166 |
|
| 167 |
SHPTree SHPAPI_CALL1(*)
|
| 168 |
SHPCreateTree( SHPHandle hSHP, int nDimension, int nMaxDepth,
|
| 169 |
double *padfBoundsMin, double *padfBoundsMax )
|
| 170 |
|
| 171 |
{
|
| 172 |
SHPTree *psTree;
|
| 173 |
|
| 174 |
if( padfBoundsMin == NULL && hSHP == NULL )
|
| 175 |
return NULL;
|
| 176 |
|
| 177 |
/* -------------------------------------------------------------------- */
|
| 178 |
/* Allocate the tree object */
|
| 179 |
/* -------------------------------------------------------------------- */
|
| 180 |
psTree = (SHPTree *) malloc(sizeof(SHPTree));
|
| 181 |
if( NULL == psTree )
|
| 182 |
{
|
| 183 |
#ifdef USE_CPL
|
| 184 |
CPLError( CE_Fatal, CPLE_OutOfMemory, "Memory allocation failure");
|
| 185 |
#endif
|
| 186 |
return NULL;
|
| 187 |
}
|
| 188 |
|
| 189 |
psTree->hSHP = hSHP;
|
| 190 |
psTree->nMaxDepth = nMaxDepth;
|
| 191 |
psTree->nDimension = nDimension;
|
| 192 |
psTree->nTotalCount = 0;
|
| 193 |
|
| 194 |
/* -------------------------------------------------------------------- */
|
| 195 |
/* If no max depth was defined, try to select a reasonable one */
|
| 196 |
/* that implies approximately 8 shapes per node. */
|
| 197 |
/* -------------------------------------------------------------------- */
|
| 198 |
if( psTree->nMaxDepth == 0 && hSHP != NULL )
|
| 199 |
{
|
| 200 |
int nMaxNodeCount = 1;
|
| 201 |
int nShapeCount;
|
| 202 |
|
| 203 |
SHPGetInfo( hSHP, &nShapeCount, NULL, NULL, NULL );
|
| 204 |
while( nMaxNodeCount*4 < nShapeCount )
|
| 205 |
{
|
| 206 |
psTree->nMaxDepth += 1;
|
| 207 |
nMaxNodeCount = nMaxNodeCount * 2;
|
| 208 |
}
|
| 209 |
|
| 210 |
#ifdef USE_CPL
|
| 211 |
CPLDebug( "Shape",
|
| 212 |
"Estimated spatial index tree depth: %d",
|
| 213 |
psTree->nMaxDepth );
|
| 214 |
#endif
|
| 215 |
|
| 216 |
/* NOTE: Due to problems with memory allocation for deep trees,
|
| 217 |
* automatically estimated depth is limited up to 12 levels.
|
| 218 |
* See Ticket #1594 for detailed discussion.
|
| 219 |
*/
|
| 220 |
if( psTree->nMaxDepth > MAX_DEFAULT_TREE_DEPTH )
|
| 221 |
{
|
| 222 |
psTree->nMaxDepth = MAX_DEFAULT_TREE_DEPTH;
|
| 223 |
|
| 224 |
#ifdef USE_CPL
|
| 225 |
CPLDebug( "Shape",
|
| 226 |
"Falling back to max number of allowed index tree levels (%d).",
|
| 227 |
MAX_DEFAULT_TREE_DEPTH );
|
| 228 |
#endif
|
| 229 |
}
|
| 230 |
}
|
| 231 |
|
| 232 |
/* -------------------------------------------------------------------- */
|
| 233 |
/* Allocate the root node. */
|
| 234 |
/* -------------------------------------------------------------------- */
|
| 235 |
psTree->psRoot = SHPTreeNodeCreate( padfBoundsMin, padfBoundsMax );
|
| 236 |
if( NULL == psTree->psRoot )
|
| 237 |
{
|
| 238 |
return NULL;
|
| 239 |
}
|
| 240 |
|
| 241 |
/* -------------------------------------------------------------------- */
|
| 242 |
/* Assign the bounds to the root node. If none are passed in, */
|
| 243 |
/* use the bounds of the provided file otherwise the create */
|
| 244 |
/* function will have already set the bounds. */
|
| 245 |
/* -------------------------------------------------------------------- */
|
| 246 |
assert( NULL != psTree );
|
| 247 |
assert( NULL != psTree->psRoot );
|
| 248 |
|
| 249 |
if( padfBoundsMin == NULL )
|
| 250 |
{
|
| 251 |
SHPGetInfo( hSHP, NULL, NULL,
|
| 252 |
psTree->psRoot->adfBoundsMin,
|
| 253 |
psTree->psRoot->adfBoundsMax );
|
| 254 |
}
|
| 255 |
|
| 256 |
/* -------------------------------------------------------------------- */
|
| 257 |
/* If we have a file, insert all it's shapes into the tree. */
|
| 258 |
/* -------------------------------------------------------------------- */
|
| 259 |
if( hSHP != NULL )
|
| 260 |
{
|
| 261 |
int iShape, nShapeCount;
|
| 262 |
|
| 263 |
SHPGetInfo( hSHP, &nShapeCount, NULL, NULL, NULL );
|
| 264 |
|
| 265 |
for( iShape = 0; iShape < nShapeCount; iShape++ )
|
| 266 |
{
|
| 267 |
SHPObject *psShape;
|
| 268 |
|
| 269 |
psShape = SHPReadObject( hSHP, iShape );
|
| 270 |
if( psShape != NULL )
|
| 271 |
{
|
| 272 |
SHPTreeAddShapeId( psTree, psShape );
|
| 273 |
SHPDestroyObject( psShape );
|
| 274 |
}
|
| 275 |
}
|
| 276 |
}
|
| 277 |
|
| 278 |
return psTree;
|
| 279 |
}
|
| 280 |
|
| 281 |
/************************************************************************/
|
| 282 |
/* SHPDestroyTreeNode() */
|
| 283 |
/************************************************************************/
|
| 284 |
|
| 285 |
static void SHPDestroyTreeNode( SHPTreeNode * psTreeNode )
|
| 286 |
|
| 287 |
{
|
| 288 |
int i;
|
| 289 |
|
| 290 |
assert( NULL != psTreeNode );
|
| 291 |
|
| 292 |
for( i = 0; i < psTreeNode->nSubNodes; i++ )
|
| 293 |
{
|
| 294 |
if( psTreeNode->apsSubNode[i] != NULL )
|
| 295 |
SHPDestroyTreeNode( psTreeNode->apsSubNode[i] );
|
| 296 |
}
|
| 297 |
|
| 298 |
if( psTreeNode->panShapeIds != NULL )
|
| 299 |
free( psTreeNode->panShapeIds );
|
| 300 |
|
| 301 |
if( psTreeNode->papsShapeObj != NULL )
|
| 302 |
{
|
| 303 |
for( i = 0; i < psTreeNode->nShapeCount; i++ )
|
| 304 |
{
|
| 305 |
if( psTreeNode->papsShapeObj[i] != NULL )
|
| 306 |
SHPDestroyObject( psTreeNode->papsShapeObj[i] );
|
| 307 |
}
|
| 308 |
|
| 309 |
free( psTreeNode->papsShapeObj );
|
| 310 |
}
|
| 311 |
|
| 312 |
free( psTreeNode );
|
| 313 |
}
|
| 314 |
|
| 315 |
/************************************************************************/
|
| 316 |
/* SHPDestroyTree() */
|
| 317 |
/************************************************************************/
|
| 318 |
|
| 319 |
void SHPAPI_CALL
|
| 320 |
SHPDestroyTree( SHPTree * psTree )
|
| 321 |
|
| 322 |
{
|
| 323 |
SHPDestroyTreeNode( psTree->psRoot );
|
| 324 |
free( psTree );
|
| 325 |
}
|
| 326 |
|
| 327 |
/************************************************************************/
|
| 328 |
/* SHPCheckBoundsOverlap() */
|
| 329 |
/* */
|
| 330 |
/* Do the given boxes overlap at all? */
|
| 331 |
/************************************************************************/
|
| 332 |
|
| 333 |
int SHPAPI_CALL
|
| 334 |
SHPCheckBoundsOverlap( double * padfBox1Min, double * padfBox1Max,
|
| 335 |
double * padfBox2Min, double * padfBox2Max,
|
| 336 |
int nDimension )
|
| 337 |
|
| 338 |
{
|
| 339 |
int iDim;
|
| 340 |
|
| 341 |
for( iDim = 0; iDim < nDimension; iDim++ )
|
| 342 |
{
|
| 343 |
if( padfBox2Max[iDim] < padfBox1Min[iDim] )
|
| 344 |
return FALSE;
|
| 345 |
|
| 346 |
if( padfBox1Max[iDim] < padfBox2Min[iDim] )
|
| 347 |
return FALSE;
|
| 348 |
}
|
| 349 |
|
| 350 |
return TRUE;
|
| 351 |
}
|
| 352 |
|
| 353 |
/************************************************************************/
|
| 354 |
/* SHPCheckObjectContained() */
|
| 355 |
/* */
|
| 356 |
/* Does the given shape fit within the indicated extents? */
|
| 357 |
/************************************************************************/
|
| 358 |
|
| 359 |
static int SHPCheckObjectContained( SHPObject * psObject, int nDimension,
|
| 360 |
double * padfBoundsMin, double * padfBoundsMax )
|
| 361 |
|
| 362 |
{
|
| 363 |
if( psObject->dfXMin < padfBoundsMin[0]
|
| 364 |
|| psObject->dfXMax > padfBoundsMax[0] )
|
| 365 |
return FALSE;
|
| 366 |
|
| 367 |
if( psObject->dfYMin < padfBoundsMin[1]
|
| 368 |
|| psObject->dfYMax > padfBoundsMax[1] )
|
| 369 |
return FALSE;
|
| 370 |
|
| 371 |
if( nDimension == 2 )
|
| 372 |
return TRUE;
|
| 373 |
|
| 374 |
if( psObject->dfZMin < padfBoundsMin[2]
|
| 375 |
|| psObject->dfZMax < padfBoundsMax[2] )
|
| 376 |
return FALSE;
|
| 377 |
|
| 378 |
if( nDimension == 3 )
|
| 379 |
return TRUE;
|
| 380 |
|
| 381 |
if( psObject->dfMMin < padfBoundsMin[3]
|
| 382 |
|| psObject->dfMMax < padfBoundsMax[3] )
|
| 383 |
return FALSE;
|
| 384 |
|
| 385 |
return TRUE;
|
| 386 |
}
|
| 387 |
|
| 388 |
/************************************************************************/
|
| 389 |
/* SHPTreeSplitBounds() */
|
| 390 |
/* */
|
| 391 |
/* Split a region into two subregion evenly, cutting along the */
|
| 392 |
/* longest dimension. */
|
| 393 |
/************************************************************************/
|
| 394 |
|
| 395 |
void SHPAPI_CALL
|
| 396 |
SHPTreeSplitBounds( double *padfBoundsMinIn, double *padfBoundsMaxIn,
|
| 397 |
double *padfBoundsMin1, double * padfBoundsMax1,
|
| 398 |
double *padfBoundsMin2, double * padfBoundsMax2 )
|
| 399 |
|
| 400 |
{
|
| 401 |
/* -------------------------------------------------------------------- */
|
| 402 |
/* The output bounds will be very similar to the input bounds, */
|
| 403 |
/* so just copy over to start. */
|
| 404 |
/* -------------------------------------------------------------------- */
|
| 405 |
memcpy( padfBoundsMin1, padfBoundsMinIn, sizeof(double) * 4 );
|
| 406 |
memcpy( padfBoundsMax1, padfBoundsMaxIn, sizeof(double) * 4 );
|
| 407 |
memcpy( padfBoundsMin2, padfBoundsMinIn, sizeof(double) * 4 );
|
| 408 |
memcpy( padfBoundsMax2, padfBoundsMaxIn, sizeof(double) * 4 );
|
| 409 |
|
| 410 |
/* -------------------------------------------------------------------- */
|
| 411 |
/* Split in X direction. */
|
| 412 |
/* -------------------------------------------------------------------- */
|
| 413 |
if( (padfBoundsMaxIn[0] - padfBoundsMinIn[0])
|
| 414 |
> (padfBoundsMaxIn[1] - padfBoundsMinIn[1]) )
|
| 415 |
{
|
| 416 |
double dfRange = padfBoundsMaxIn[0] - padfBoundsMinIn[0];
|
| 417 |
|
| 418 |
padfBoundsMax1[0] = padfBoundsMinIn[0] + dfRange * SHP_SPLIT_RATIO;
|
| 419 |
padfBoundsMin2[0] = padfBoundsMaxIn[0] - dfRange * SHP_SPLIT_RATIO;
|
| 420 |
}
|
| 421 |
|
| 422 |
/* -------------------------------------------------------------------- */
|
| 423 |
/* Otherwise split in Y direction. */
|
| 424 |
/* -------------------------------------------------------------------- */
|
| 425 |
else
|
| 426 |
{
|
| 427 |
double dfRange = padfBoundsMaxIn[1] - padfBoundsMinIn[1];
|
| 428 |
|
| 429 |
padfBoundsMax1[1] = padfBoundsMinIn[1] + dfRange * SHP_SPLIT_RATIO;
|
| 430 |
padfBoundsMin2[1] = padfBoundsMaxIn[1] - dfRange * SHP_SPLIT_RATIO;
|
| 431 |
}
|
| 432 |
}
|
| 433 |
|
| 434 |
/************************************************************************/
|
| 435 |
/* SHPTreeNodeAddShapeId() */
|
| 436 |
/************************************************************************/
|
| 437 |
|
| 438 |
static int
|
| 439 |
SHPTreeNodeAddShapeId( SHPTreeNode * psTreeNode, SHPObject * psObject,
|
| 440 |
int nMaxDepth, int nDimension )
|
| 441 |
|
| 442 |
{
|
| 443 |
int i;
|
| 444 |
|
| 445 |
/* -------------------------------------------------------------------- */
|
| 446 |
/* If there are subnodes, then consider wiether this object */
|
| 447 |
/* will fit in them. */
|
| 448 |
/* -------------------------------------------------------------------- */
|
| 449 |
if( nMaxDepth > 1 && psTreeNode->nSubNodes > 0 )
|
| 450 |
{
|
| 451 |
for( i = 0; i < psTreeNode->nSubNodes; i++ )
|
| 452 |
{
|
| 453 |
if( SHPCheckObjectContained(psObject, nDimension,
|
| 454 |
psTreeNode->apsSubNode[i]->adfBoundsMin,
|
| 455 |
psTreeNode->apsSubNode[i]->adfBoundsMax))
|
| 456 |
{
|
| 457 |
return SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[i],
|
| 458 |
psObject, nMaxDepth-1,
|
| 459 |
nDimension );
|
| 460 |
}
|
| 461 |
}
|
| 462 |
}
|
| 463 |
|
| 464 |
/* -------------------------------------------------------------------- */
|
| 465 |
/* Otherwise, consider creating four subnodes if could fit into */
|
| 466 |
/* them, and adding to the appropriate subnode. */
|
| 467 |
/* -------------------------------------------------------------------- */
|
| 468 |
#if MAX_SUBNODE == 4
|
| 469 |
else if( nMaxDepth > 1 && psTreeNode->nSubNodes == 0 )
|
| 470 |
{
|
| 471 |
double adfBoundsMinH1[4], adfBoundsMaxH1[4];
|
| 472 |
double adfBoundsMinH2[4], adfBoundsMaxH2[4];
|
| 473 |
double adfBoundsMin1[4], adfBoundsMax1[4];
|
| 474 |
double adfBoundsMin2[4], adfBoundsMax2[4];
|
| 475 |
double adfBoundsMin3[4], adfBoundsMax3[4];
|
| 476 |
double adfBoundsMin4[4], adfBoundsMax4[4];
|
| 477 |
|
| 478 |
SHPTreeSplitBounds( psTreeNode->adfBoundsMin,
|
| 479 |
psTreeNode->adfBoundsMax,
|
| 480 |
adfBoundsMinH1, adfBoundsMaxH1,
|
| 481 |
adfBoundsMinH2, adfBoundsMaxH2 );
|
| 482 |
|
| 483 |
SHPTreeSplitBounds( adfBoundsMinH1, adfBoundsMaxH1,
|
| 484 |
adfBoundsMin1, adfBoundsMax1,
|
| 485 |
adfBoundsMin2, adfBoundsMax2 );
|
| 486 |
|
| 487 |
SHPTreeSplitBounds( adfBoundsMinH2, adfBoundsMaxH2,
|
| 488 |
adfBoundsMin3, adfBoundsMax3,
|
| 489 |
adfBoundsMin4, adfBoundsMax4 );
|
| 490 |
|
| 491 |
if( SHPCheckObjectContained(psObject, nDimension,
|
| 492 |
adfBoundsMin1, adfBoundsMax1)
|
| 493 |
|| SHPCheckObjectContained(psObject, nDimension,
|
| 494 |
adfBoundsMin2, adfBoundsMax2)
|
| 495 |
|| SHPCheckObjectContained(psObject, nDimension,
|
| 496 |
adfBoundsMin3, adfBoundsMax3)
|
| 497 |
|| SHPCheckObjectContained(psObject, nDimension,
|
| 498 |
adfBoundsMin4, adfBoundsMax4) )
|
| 499 |
{
|
| 500 |
psTreeNode->nSubNodes = 4;
|
| 501 |
psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,
|
| 502 |
adfBoundsMax1 );
|
| 503 |
psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,
|
| 504 |
adfBoundsMax2 );
|
| 505 |
psTreeNode->apsSubNode[2] = SHPTreeNodeCreate( adfBoundsMin3,
|
| 506 |
adfBoundsMax3 );
|
| 507 |
psTreeNode->apsSubNode[3] = SHPTreeNodeCreate( adfBoundsMin4,
|
| 508 |
adfBoundsMax4 );
|
| 509 |
|
| 510 |
/* recurse back on this node now that it has subnodes */
|
| 511 |
return( SHPTreeNodeAddShapeId( psTreeNode, psObject,
|
| 512 |
nMaxDepth, nDimension ) );
|
| 513 |
}
|
| 514 |
}
|
| 515 |
#endif /* MAX_SUBNODE == 4 */
|
| 516 |
|
| 517 |
/* -------------------------------------------------------------------- */
|
| 518 |
/* Otherwise, consider creating two subnodes if could fit into */
|
| 519 |
/* them, and adding to the appropriate subnode. */
|
| 520 |
/* -------------------------------------------------------------------- */
|
| 521 |
#if MAX_SUBNODE == 2
|
| 522 |
else if( nMaxDepth > 1 && psTreeNode->nSubNodes == 0 )
|
| 523 |
{
|
| 524 |
double adfBoundsMin1[4], adfBoundsMax1[4];
|
| 525 |
double adfBoundsMin2[4], adfBoundsMax2[4];
|
| 526 |
|
| 527 |
SHPTreeSplitBounds( psTreeNode->adfBoundsMin, psTreeNode->adfBoundsMax,
|
| 528 |
adfBoundsMin1, adfBoundsMax1,
|
| 529 |
adfBoundsMin2, adfBoundsMax2 );
|
| 530 |
|
| 531 |
if( SHPCheckObjectContained(psObject, nDimension,
|
| 532 |
adfBoundsMin1, adfBoundsMax1))
|
| 533 |
{
|
| 534 |
psTreeNode->nSubNodes = 2;
|
| 535 |
psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,
|
| 536 |
adfBoundsMax1 );
|
| 537 |
psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,
|
| 538 |
adfBoundsMax2 );
|
| 539 |
|
| 540 |
return( SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[0], psObject,
|
| 541 |
nMaxDepth - 1, nDimension ) );
|
| 542 |
}
|
| 543 |
else if( SHPCheckObjectContained(psObject, nDimension,
|
| 544 |
adfBoundsMin2, adfBoundsMax2) )
|
| 545 |
{
|
| 546 |
psTreeNode->nSubNodes = 2;
|
| 547 |
psTreeNode->apsSubNode[0] = SHPTreeNodeCreate( adfBoundsMin1,
|
| 548 |
adfBoundsMax1 );
|
| 549 |
psTreeNode->apsSubNode[1] = SHPTreeNodeCreate( adfBoundsMin2,
|
| 550 |
adfBoundsMax2 );
|
| 551 |
|
| 552 |
return( SHPTreeNodeAddShapeId( psTreeNode->apsSubNode[1], psObject,
|
| 553 |
nMaxDepth - 1, nDimension ) );
|
| 554 |
}
|
| 555 |
}
|
| 556 |
#endif /* MAX_SUBNODE == 2 */
|
| 557 |
|
| 558 |
/* -------------------------------------------------------------------- */
|
| 559 |
/* If none of that worked, just add it to this nodes list. */
|
| 560 |
/* -------------------------------------------------------------------- */
|
| 561 |
psTreeNode->nShapeCount++;
|
| 562 |
|
| 563 |
psTreeNode->panShapeIds = (int *)
|
| 564 |
SfRealloc( psTreeNode->panShapeIds,
|
| 565 |
sizeof(int) * psTreeNode->nShapeCount );
|
| 566 |
psTreeNode->panShapeIds[psTreeNode->nShapeCount-1] = psObject->nShapeId;
|
| 567 |
|
| 568 |
if( psTreeNode->papsShapeObj != NULL )
|
| 569 |
{
|
| 570 |
psTreeNode->papsShapeObj = (SHPObject **)
|
| 571 |
SfRealloc( psTreeNode->papsShapeObj,
|
| 572 |
sizeof(void *) * psTreeNode->nShapeCount );
|
| 573 |
psTreeNode->papsShapeObj[psTreeNode->nShapeCount-1] = NULL;
|
| 574 |
}
|
| 575 |
|
| 576 |
return TRUE;
|
| 577 |
}
|
| 578 |
|
| 579 |
/************************************************************************/
|
| 580 |
/* SHPTreeAddShapeId() */
|
| 581 |
/* */
|
| 582 |
/* Add a shape to the tree, but don't keep a pointer to the */
|
| 583 |
/* object data, just keep the shapeid. */
|
| 584 |
/************************************************************************/
|
| 585 |
|
| 586 |
int SHPAPI_CALL
|
| 587 |
SHPTreeAddShapeId( SHPTree * psTree, SHPObject * psObject )
|
| 588 |
|
| 589 |
{
|
| 590 |
psTree->nTotalCount++;
|
| 591 |
|
| 592 |
return( SHPTreeNodeAddShapeId( psTree->psRoot, psObject,
|
| 593 |
psTree->nMaxDepth, psTree->nDimension ) );
|
| 594 |
}
|
| 595 |
|
| 596 |
/************************************************************************/
|
| 597 |
/* SHPTreeCollectShapesIds() */
|
| 598 |
/* */
|
| 599 |
/* Work function implementing SHPTreeFindLikelyShapes() on a */
|
| 600 |
/* tree node by tree node basis. */
|
| 601 |
/************************************************************************/
|
| 602 |
|
| 603 |
void SHPAPI_CALL
|
| 604 |
SHPTreeCollectShapeIds( SHPTree *hTree, SHPTreeNode * psTreeNode,
|
| 605 |
double * padfBoundsMin, double * padfBoundsMax,
|
| 606 |
int * pnShapeCount, int * pnMaxShapes,
|
| 607 |
int ** ppanShapeList )
|
| 608 |
|
| 609 |
{
|
| 610 |
int i;
|
| 611 |
|
| 612 |
/* -------------------------------------------------------------------- */
|
| 613 |
/* Does this node overlap the area of interest at all? If not, */
|
| 614 |
/* return without adding to the list at all. */
|
| 615 |
/* -------------------------------------------------------------------- */
|
| 616 |
if( !SHPCheckBoundsOverlap( psTreeNode->adfBoundsMin,
|
| 617 |
psTreeNode->adfBoundsMax,
|
| 618 |
padfBoundsMin,
|
| 619 |
padfBoundsMax,
|
| 620 |
hTree->nDimension ) )
|
| 621 |
return;
|
| 622 |
|
| 623 |
/* -------------------------------------------------------------------- */
|
| 624 |
/* Grow the list to hold the shapes on this node. */
|
| 625 |
/* -------------------------------------------------------------------- */
|
| 626 |
if( *pnShapeCount + psTreeNode->nShapeCount > *pnMaxShapes )
|
| 627 |
{
|
| 628 |
*pnMaxShapes = (*pnShapeCount + psTreeNode->nShapeCount) * 2 + 20;
|
| 629 |
*ppanShapeList = (int *)
|
| 630 |
SfRealloc(*ppanShapeList,sizeof(int) * *pnMaxShapes);
|
| 631 |
}
|
| 632 |
|
| 633 |
/* -------------------------------------------------------------------- */
|
| 634 |
/* Add the local nodes shapeids to the list. */
|
| 635 |
/* -------------------------------------------------------------------- */
|
| 636 |
for( i = 0; i < psTreeNode->nShapeCount; i++ )
|
| 637 |
{
|
| 638 |
(*ppanShapeList)[(*pnShapeCount)++] = psTreeNode->panShapeIds[i];
|
| 639 |
}
|
| 640 |
|
| 641 |
/* -------------------------------------------------------------------- */
|
| 642 |
/* Recurse to subnodes if they exist. */
|
| 643 |
/* -------------------------------------------------------------------- */
|
| 644 |
for( i = 0; i < psTreeNode->nSubNodes; i++ )
|
| 645 |
{
|
| 646 |
if( psTreeNode->apsSubNode[i] != NULL )
|
| 647 |
SHPTreeCollectShapeIds( hTree, psTreeNode->apsSubNode[i],
|
| 648 |
padfBoundsMin, padfBoundsMax,
|
| 649 |
pnShapeCount, pnMaxShapes,
|
| 650 |
ppanShapeList );
|
| 651 |
}
|
| 652 |
}
|
| 653 |
|
| 654 |
/************************************************************************/
|
| 655 |
/* SHPTreeFindLikelyShapes() */
|
| 656 |
/* */
|
| 657 |
/* Find all shapes within tree nodes for which the tree node */
|
| 658 |
/* bounding box overlaps the search box. The return value is */
|
| 659 |
/* an array of shapeids terminated by a -1. The shapeids will */
|
| 660 |
/* be in order, as hopefully this will result in faster (more */
|
| 661 |
/* sequential) reading from the file. */
|
| 662 |
/************************************************************************/
|
| 663 |
|
| 664 |
/* helper for qsort */
|
| 665 |
static int
|
| 666 |
compare_ints( const void * a, const void * b)
|
| 667 |
{
|
| 668 |
return (*(int*)a) - (*(int*)b);
|
| 669 |
}
|
| 670 |
|
| 671 |
int SHPAPI_CALL1(*)
|
| 672 |
SHPTreeFindLikelyShapes( SHPTree * hTree,
|
| 673 |
double * padfBoundsMin, double * padfBoundsMax,
|
| 674 |
int * pnShapeCount )
|
| 675 |
|
| 676 |
{
|
| 677 |
int *panShapeList=NULL, nMaxShapes = 0;
|
| 678 |
|
| 679 |
/* -------------------------------------------------------------------- */
|
| 680 |
/* Perform the search by recursive descent. */
|
| 681 |
/* -------------------------------------------------------------------- */
|
| 682 |
*pnShapeCount = 0;
|
| 683 |
|
| 684 |
SHPTreeCollectShapeIds( hTree, hTree->psRoot,
|
| 685 |
padfBoundsMin, padfBoundsMax,
|
| 686 |
pnShapeCount, &nMaxShapes,
|
| 687 |
&panShapeList );
|
| 688 |
|
| 689 |
/* -------------------------------------------------------------------- */
|
| 690 |
/* Sort the id array */
|
| 691 |
/* -------------------------------------------------------------------- */
|
| 692 |
|
| 693 |
qsort(panShapeList, *pnShapeCount, sizeof(int), compare_ints);
|
| 694 |
|
| 695 |
return panShapeList;
|
| 696 |
}
|
| 697 |
|
| 698 |
/************************************************************************/
|
| 699 |
/* SHPTreeNodeTrim() */
|
| 700 |
/* */
|
| 701 |
/* This is the recurve version of SHPTreeTrimExtraNodes() that */
|
| 702 |
/* walks the tree cleaning it up. */
|
| 703 |
/************************************************************************/
|
| 704 |
|
| 705 |
static int SHPTreeNodeTrim( SHPTreeNode * psTreeNode )
|
| 706 |
|
| 707 |
{
|
| 708 |
int i;
|
| 709 |
|
| 710 |
/* -------------------------------------------------------------------- */
|
| 711 |
/* Trim subtrees, and free subnodes that come back empty. */
|
| 712 |
/* -------------------------------------------------------------------- */
|
| 713 |
for( i = 0; i < psTreeNode->nSubNodes; i++ )
|
| 714 |
{
|
| 715 |
if( SHPTreeNodeTrim( psTreeNode->apsSubNode[i] ) )
|
| 716 |
{
|
| 717 |
SHPDestroyTreeNode( psTreeNode->apsSubNode[i] );
|
| 718 |
|
| 719 |
psTreeNode->apsSubNode[i] =
|
| 720 |
psTreeNode->apsSubNode[psTreeNode->nSubNodes-1];
|
| 721 |
|
| 722 |
psTreeNode->nSubNodes--;
|
| 723 |
|
| 724 |
i--; /* process the new occupant of this subnode entry */
|
| 725 |
}
|
| 726 |
}
|
| 727 |
|
| 728 |
/* -------------------------------------------------------------------- */
|
| 729 |
/* We should be trimmed if we have no subnodes, and no shapes. */
|
| 730 |
/* -------------------------------------------------------------------- */
|
| 731 |
return( psTreeNode->nSubNodes == 0 && psTreeNode->nShapeCount == 0 );
|
| 732 |
}
|
| 733 |
|
| 734 |
/************************************************************************/
|
| 735 |
/* SHPTreeTrimExtraNodes() */
|
| 736 |
/* */
|
| 737 |
/* Trim empty nodes from the tree. Note that we never trim an */
|
| 738 |
/* empty root node. */
|
| 739 |
/************************************************************************/
|
| 740 |
|
| 741 |
void SHPAPI_CALL
|
| 742 |
SHPTreeTrimExtraNodes( SHPTree * hTree )
|
| 743 |
|
| 744 |
{
|
| 745 |
SHPTreeNodeTrim( hTree->psRoot );
|
| 746 |
}
|
| 747 |
|
| 748 |
/************************************************************************/
|
| 749 |
/* SwapWord() */
|
| 750 |
/* */
|
| 751 |
/* Swap a 2, 4 or 8 byte word. */
|
| 752 |
/************************************************************************/
|
| 753 |
|
| 754 |
static void SwapWord( int length, void * wordP )
|
| 755 |
|
| 756 |
{
|
| 757 |
int i;
|
| 758 |
unsigned char temp;
|
| 759 |
|
| 760 |
for( i=0; i < length/2; i++ )
|
| 761 |
{
|
| 762 |
temp = ((unsigned char *) wordP)[i];
|
| 763 |
((unsigned char *)wordP)[i] = ((unsigned char *) wordP)[length-i-1];
|
| 764 |
((unsigned char *) wordP)[length-i-1] = temp;
|
| 765 |
}
|
| 766 |
}
|
| 767 |
|
| 768 |
/************************************************************************/
|
| 769 |
/* SHPSearchDiskTreeNode() */
|
| 770 |
/************************************************************************/
|
| 771 |
|
| 772 |
static int
|
| 773 |
SHPSearchDiskTreeNode( FILE *fp, double *padfBoundsMin, double *padfBoundsMax,
|
| 774 |
int **ppanResultBuffer, int *pnBufferMax,
|
| 775 |
int *pnResultCount, int bNeedSwap )
|
| 776 |
|
| 777 |
{
|
| 778 |
int i;
|
| 779 |
int offset;
|
| 780 |
int numshapes, numsubnodes;
|
| 781 |
double adfNodeBoundsMin[2], adfNodeBoundsMax[2];
|
| 782 |
|
| 783 |
/* -------------------------------------------------------------------- */
|
| 784 |
/* Read and unswap first part of node info. */
|
| 785 |
/* -------------------------------------------------------------------- */
|
| 786 |
fread( &offset, 4, 1, fp );
|
| 787 |
if ( bNeedSwap ) SwapWord ( 4, &offset );
|
| 788 |
|
| 789 |
fread( adfNodeBoundsMin, sizeof(double), 2, fp );
|
| 790 |
fread( adfNodeBoundsMax, sizeof(double), 2, fp );
|
| 791 |
if ( bNeedSwap )
|
| 792 |
{
|
| 793 |
SwapWord( 8, adfNodeBoundsMin + 0 );
|
| 794 |
SwapWord( 8, adfNodeBoundsMin + 1 );
|
| 795 |
SwapWord( 8, adfNodeBoundsMax + 0 );
|
| 796 |
SwapWord( 8, adfNodeBoundsMax + 1 );
|
| 797 |
}
|
| 798 |
|
| 799 |
fread( &numshapes, 4, 1, fp );
|
| 800 |
if ( bNeedSwap ) SwapWord ( 4, &numshapes );
|
| 801 |
|
| 802 |
/* -------------------------------------------------------------------- */
|
| 803 |
/* If we don't overlap this node at all, we can just fseek() */
|
| 804 |
/* pass this node info and all subnodes. */
|
| 805 |
/* -------------------------------------------------------------------- */
|
| 806 |
if( !SHPCheckBoundsOverlap( adfNodeBoundsMin, adfNodeBoundsMax,
|
| 807 |
padfBoundsMin, padfBoundsMax, 2 ) )
|
| 808 |
{
|
| 809 |
offset += numshapes*sizeof(int) + sizeof(int);
|
| 810 |
fseek(fp, offset, SEEK_CUR);
|
| 811 |
return TRUE;
|
| 812 |
}
|
| 813 |
|
| 814 |
/* -------------------------------------------------------------------- */
|
| 815 |
/* Add all the shapeids at this node to our list. */
|
| 816 |
/* -------------------------------------------------------------------- */
|
| 817 |
if(numshapes > 0)
|
| 818 |
{
|
| 819 |
if( *pnResultCount + numshapes > *pnBufferMax )
|
| 820 |
{
|
| 821 |
*pnBufferMax = (int) ((*pnResultCount + numshapes + 100) * 1.25);
|
| 822 |
*ppanResultBuffer = (int *)
|
| 823 |
SfRealloc( *ppanResultBuffer, *pnBufferMax * sizeof(int) );
|
| 824 |
}
|
| 825 |
|
| 826 |
fread( *ppanResultBuffer + *pnResultCount,
|
| 827 |
sizeof(int), numshapes, fp );
|
| 828 |
|
| 829 |
if (bNeedSwap )
|
| 830 |
{
|
| 831 |
for( i=0; i<numshapes; i++ )
|
| 832 |
SwapWord( 4, *ppanResultBuffer + *pnResultCount + i );
|
| 833 |
}
|
| 834 |
|
| 835 |
*pnResultCount += numshapes;
|
| 836 |
}
|
| 837 |
|
| 838 |
/* -------------------------------------------------------------------- */
|
| 839 |
/* Process the subnodes. */
|
| 840 |
/* -------------------------------------------------------------------- */
|
| 841 |
fread( &numsubnodes, 4, 1, fp );
|
| 842 |
if ( bNeedSwap ) SwapWord ( 4, &numsubnodes );
|
| 843 |
|
| 844 |
for(i=0; i<numsubnodes; i++)
|
| 845 |
{
|
| 846 |
if( !SHPSearchDiskTreeNode( fp, padfBoundsMin, padfBoundsMax,
|
| 847 |
ppanResultBuffer, pnBufferMax,
|
| 848 |
pnResultCount, bNeedSwap ) )
|
| 849 |
return FALSE;
|
| 850 |
}
|
| 851 |
|
| 852 |
return TRUE;
|
| 853 |
}
|
| 854 |
|
| 855 |
/************************************************************************/
|
| 856 |
/* SHPSearchDiskTree() */
|
| 857 |
/************************************************************************/
|
| 858 |
|
| 859 |
int SHPAPI_CALL1(*)
|
| 860 |
SHPSearchDiskTree( FILE *fp,
|
| 861 |
double *padfBoundsMin, double *padfBoundsMax,
|
| 862 |
int *pnShapeCount )
|
| 863 |
|
| 864 |
{
|
| 865 |
int i, bNeedSwap, nBufferMax = 0;
|
| 866 |
unsigned char abyBuf[16];
|
| 867 |
int *panResultBuffer = NULL;
|
| 868 |
|
| 869 |
*pnShapeCount = 0;
|
| 870 |
|
| 871 |
/* -------------------------------------------------------------------- */
|
| 872 |
/* Establish the byte order on this machine. */
|
| 873 |
/* -------------------------------------------------------------------- */
|
| 874 |
i = 1;
|
| 875 |
if( *((unsigned char *) &i) == 1 )
|
| 876 |
bBigEndian = FALSE;
|
| 877 |
else
|
| 878 |
bBigEndian = TRUE;
|
| 879 |
|
| 880 |
/* -------------------------------------------------------------------- */
|
| 881 |
/* Read the header. */
|
| 882 |
/* -------------------------------------------------------------------- */
|
| 883 |
fseek( fp, 0, SEEK_SET );
|
| 884 |
fread( abyBuf, 16, 1, fp );
|
| 885 |
|
| 886 |
if( memcmp( abyBuf, "SQT", 3 ) != 0 )
|
| 887 |
return NULL;
|
| 888 |
|
| 889 |
if( (abyBuf[3] == 2 && bBigEndian)
|
| 890 |
|| (abyBuf[3] == 1 && !bBigEndian) )
|
| 891 |
bNeedSwap = FALSE;
|
| 892 |
else
|
| 893 |
bNeedSwap = TRUE;
|
| 894 |
|
| 895 |
/* -------------------------------------------------------------------- */
|
| 896 |
/* Search through root node and it's decendents. */
|
| 897 |
/* -------------------------------------------------------------------- */
|
| 898 |
if( !SHPSearchDiskTreeNode( fp, padfBoundsMin, padfBoundsMax,
|
| 899 |
&panResultBuffer, &nBufferMax,
|
| 900 |
pnShapeCount, bNeedSwap ) )
|
| 901 |
{
|
| 902 |
if( panResultBuffer != NULL )
|
| 903 |
free( panResultBuffer );
|
| 904 |
*pnShapeCount = 0;
|
| 905 |
return NULL;
|
| 906 |
}
|
| 907 |
/* -------------------------------------------------------------------- */
|
| 908 |
/* Sort the id array */
|
| 909 |
/* -------------------------------------------------------------------- */
|
| 910 |
qsort(panResultBuffer, *pnShapeCount, sizeof(int), compare_ints);
|
| 911 |
|
| 912 |
return panResultBuffer;
|
| 913 |
}
|
| 914 |
|
| 915 |
/************************************************************************/
|
| 916 |
/* SHPGetSubNodeOffset() */
|
| 917 |
/* */
|
| 918 |
/* Determine how big all the subnodes of this node (and their */
|
| 919 |
/* children) will be. This will allow disk based searchers to */
|
| 920 |
/* seek past them all efficiently. */
|
| 921 |
/************************************************************************/
|
| 922 |
|
| 923 |
static int SHPGetSubNodeOffset( SHPTreeNode *node)
|
| 924 |
{
|
| 925 |
int i;
|
| 926 |
long offset=0;
|
| 927 |
|
| 928 |
for(i=0; i<node->nSubNodes; i++ )
|
| 929 |
{
|
| 930 |
if(node->apsSubNode[i])
|
| 931 |
{
|
| 932 |
offset += 4*sizeof(double)
|
| 933 |
+ (node->apsSubNode[i]->nShapeCount+3)*sizeof(int);
|
| 934 |
offset += SHPGetSubNodeOffset(node->apsSubNode[i]);
|
| 935 |
}
|
| 936 |
}
|
| 937 |
|
| 938 |
return(offset);
|
| 939 |
}
|
| 940 |
|
| 941 |
/************************************************************************/
|
| 942 |
/* SHPWriteTreeNode() */
|
| 943 |
/************************************************************************/
|
| 944 |
|
| 945 |
static void SHPWriteTreeNode( FILE *fp, SHPTreeNode *node)
|
| 946 |
{
|
| 947 |
int i,j;
|
| 948 |
int offset;
|
| 949 |
unsigned char *pabyRec = NULL;
|
| 950 |
assert( NULL != node );
|
| 951 |
|
| 952 |
offset = SHPGetSubNodeOffset(node);
|
| 953 |
|
| 954 |
pabyRec = (unsigned char *)
|
| 955 |
malloc(sizeof(double) * 4
|
| 956 |
+ (3 * sizeof(int)) + (node->nShapeCount * sizeof(int)) );
|
| 957 |
if( NULL == pabyRec )
|
| 958 |
{
|
| 959 |
#ifdef USE_CPL
|
| 960 |
CPLError( CE_Fatal, CPLE_OutOfMemory, "Memory allocation failure");
|
| 961 |
#endif
|
| 962 |
assert( 0 );
|
| 963 |
}
|
| 964 |
assert( NULL != pabyRec );
|
| 965 |
|
| 966 |
memcpy( pabyRec, &offset, 4);
|
| 967 |
|
| 968 |
/* minx, miny, maxx, maxy */
|
| 969 |
memcpy( pabyRec+ 4, node->adfBoundsMin+0, sizeof(double) );
|
| 970 |
memcpy( pabyRec+12, node->adfBoundsMin+1, sizeof(double) );
|
| 971 |
memcpy( pabyRec+20, node->adfBoundsMax+0, sizeof(double) );
|
| 972 |
memcpy( pabyRec+28, node->adfBoundsMax+1, sizeof(double) );
|
| 973 |
|
| 974 |
memcpy( pabyRec+36, &node->nShapeCount, 4);
|
| 975 |
j = node->nShapeCount * sizeof(int);
|
| 976 |
memcpy( pabyRec+40, node->panShapeIds, j);
|
| 977 |
memcpy( pabyRec+j+40, &node->nSubNodes, 4);
|
| 978 |
|
| 979 |
fwrite( pabyRec, 44+j, 1, fp );
|
| 980 |
free (pabyRec);
|
| 981 |
|
| 982 |
for(i=0; i<node->nSubNodes; i++ )
|
| 983 |
{
|
| 984 |
if(node->apsSubNode[i])
|
| 985 |
SHPWriteTreeNode( fp, node->apsSubNode[i]);
|
| 986 |
}
|
| 987 |
}
|
| 988 |
|
| 989 |
/************************************************************************/
|
| 990 |
/* SHPWriteTree() */
|
| 991 |
/************************************************************************/
|
| 992 |
|
| 993 |
int SHPWriteTree(SHPTree *tree, const char *filename )
|
| 994 |
{
|
| 995 |
char signature[4] = "SQT";
|
| 996 |
int i;
|
| 997 |
char abyBuf[32];
|
| 998 |
FILE *fp;
|
| 999 |
|
| 1000 |
/* -------------------------------------------------------------------- */
|
| 1001 |
/* Open the output file. */
|
| 1002 |
/* -------------------------------------------------------------------- */
|
| 1003 |
fp = fopen(filename, "wb");
|
| 1004 |
if( fp == NULL )
|
| 1005 |
{
|
| 1006 |
return FALSE;
|
| 1007 |
}
|
| 1008 |
|
| 1009 |
/* -------------------------------------------------------------------- */
|
| 1010 |
/* Establish the byte order on this machine. */
|
| 1011 |
/* -------------------------------------------------------------------- */
|
| 1012 |
i = 1;
|
| 1013 |
if( *((unsigned char *) &i) == 1 )
|
| 1014 |
bBigEndian = FALSE;
|
| 1015 |
else
|
| 1016 |
bBigEndian = TRUE;
|
| 1017 |
|
| 1018 |
/* -------------------------------------------------------------------- */
|
| 1019 |
/* Write the header. */
|
| 1020 |
/* -------------------------------------------------------------------- */
|
| 1021 |
memcpy( abyBuf+0, signature, 3 );
|
| 1022 |
|
| 1023 |
if( bBigEndian )
|
| 1024 |
abyBuf[3] = 2; /* New MSB */
|
| 1025 |
else
|
| 1026 |
abyBuf[3] = 1; /* New LSB */
|
| 1027 |
|
| 1028 |
abyBuf[4] = 1; /* version */
|
| 1029 |
abyBuf[5] = 0; /* next 3 reserved */
|
| 1030 |
abyBuf[6] = 0;
|
| 1031 |
abyBuf[7] = 0;
|
| 1032 |
|
| 1033 |
fwrite( abyBuf, 8, 1, fp );
|
| 1034 |
|
| 1035 |
fwrite( &(tree->nTotalCount), 4, 1, fp );
|
| 1036 |
|
| 1037 |
/* write maxdepth */
|
| 1038 |
|
| 1039 |
fwrite( &(tree->nMaxDepth), 4, 1, fp );
|
| 1040 |
|
| 1041 |
/* -------------------------------------------------------------------- */
|
| 1042 |
/* Write all the nodes "in order". */
|
| 1043 |
/* -------------------------------------------------------------------- */
|
| 1044 |
|
| 1045 |
SHPWriteTreeNode( fp, tree->psRoot );
|
| 1046 |
|
| 1047 |
fclose( fp );
|
| 1048 |
|
| 1049 |
return TRUE;
|
| 1050 |
}
|
Parent Directory
| 
Revision Log