| 295 | } |
| 296 | |
| 297 | static int treeNodeAddShapeId( treeNodeObj *node, int id, rectObj rect, int maxdepth) |
| 298 | { |
| 299 | int i; |
| 300 | |
| 301 | /* -------------------------------------------------------------------- */ |
| 302 | /* If there are subnodes, then consider whether this object */ |
| 303 | /* will fit in them. */ |
| 304 | /* -------------------------------------------------------------------- */ |
| 305 | if( maxdepth > 1 && node->numsubnodes > 0 ) { |
| 306 | for(i=0; i<node->numsubnodes; i++ ) { |
| 307 | if( msRectContained(&rect, &node->subnode[i]->rect)) { |
| 308 | return treeNodeAddShapeId( node->subnode[i], id, rect, maxdepth-1); |
| 309 | } |
| 310 | } |
| 311 | } |
| 312 | |
| 313 | /* -------------------------------------------------------------------- */ |
| 314 | /* Otherwise, consider creating four subnodes if could fit into */ |
| 315 | /* them, and adding to the appropriate subnode. */ |
| 316 | /* -------------------------------------------------------------------- */ |
| 317 | #if MAX_SUBNODES == 4 |
| 318 | else if( maxdepth > 1 && node->numsubnodes == 0 ) { |
| 319 | rectObj half1, half2, quad1, quad2, quad3, quad4; |
| 320 | |
| 321 | treeSplitBounds(&node->rect, &half1, &half2); |
| 322 | treeSplitBounds(&half1, &quad1, &quad2); |
| 323 | treeSplitBounds(&half2, &quad3, &quad4); |
| 324 | |
| 325 | if(msRectContained(&rect, &quad1) || msRectContained(&rect, &quad2) || msRectContained(&rect, &quad3) || msRectContained(&rect, &quad4)) { |
| 326 | node->numsubnodes = 4; |
| 327 | node->subnode[0] = treeNodeCreate(quad1); |
| 328 | node->subnode[1] = treeNodeCreate(quad2); |
| 329 | node->subnode[2] = treeNodeCreate(quad3); |
| 330 | node->subnode[3] = treeNodeCreate(quad4); |
| 331 | |
| 332 | /* recurse back on this node now that it has subnodes */ |
| 333 | return(treeNodeAddShapeId(node, id, rect, maxdepth)); |
| 334 | } |
| 335 | } |
| 336 | #endif |
| 337 | |
| 338 | /* -------------------------------------------------------------------- */ |
| 339 | /* Otherwise, consider creating two subnodes if could fit into */ |
| 340 | /* them, and adding to the appropriate subnode. */ |
| 341 | /* -------------------------------------------------------------------- */ |
| 342 | #if MAX_SUBNODE == 2 |
| 343 | else if( maxdepth > 1 && node->numsubnodes == 0 ) { |
| 344 | rectObj half1, half2; |
| 345 | |
| 346 | treeSplitBounds(&node->rect, &half1, &half2); |
| 347 | |
| 348 | if( msRectContained(&rect, &half1)) { |
| 349 | node->numsubnodes = 2; |
| 350 | node->subnode[0] = treeNodeCreate(half1); |
| 351 | node->subnode[1] = treeNodeCreate(half2); |
| 352 | |
| 353 | return(treeNodeAddShapeId(node->subnode[0], id, rect, maxdepth-1)); |
| 354 | } else |
no test coverage detected