Shapefile quadtree in shapelib

Question

In shapelib, I've noted that quite amount of code is meant to handle Shapefile quadtree. For instance, the tool shptreedump (in shapelib source code).

warmerda@gdal[207]% shptreedump -maxdepth 6 eg_data/polygon.shp ( SHPTreeNode Min = (471127.19,4751545.00) Max = (489292.31,4765610.50) Shapes(0): ( SHPTreeNode Min = (471127.19,4751545.00) Max = (481118.01,4765610.50) Shapes(0): ( SHPTreeNode Min = (471127.19,4751545.00) Max = (481118.01,4759281.03) Shapes(0): ( SHPTreeNode Min = (471127.19,4751545.00) Max = (476622.14,4759281.03) Shapes(0): ( SHPTreeNode Min = (471127.19,4751545.00) Max = (476622.14,4755799.81) Shapes(0): ( SHPTreeNode Min = (471127.19,4751545.00) Max = (474149.41,4755799.81) Shapes(6): 395 397 402 404 405 422 ) ( SHPTreeNode Min = (473599.92,4751545.00) Max = (476622.14,4755799.81) Shapes(10): 392 394 403 413 414 417 426 433 434 447 ) ) ...

I think I've been quite familiar with shapefile format after reading the ESRI Shapefile Technical Description. But I can't see any internal tree structure itself. So my question is, what is the shapefile quadtree for? And if possible, with explanation of shapefile quadtree implementation.

Thanks.

Answer 1

If you look at the end of your quoted text, right where you stopped, lots of closing parenthesis...good old Lisp style encoding:

(R (st1 (st21 () () () ()) () () ()) (st2) (st3) (st4))

R stands for the root of the tree, then you have four subtrees in () plus the actual data st1, I denoted the 4 subtrees by st1...st4. st21 stands for the first subtree on the second level. The subtrees could be labeled, or if any of them empty denoted by (). It is easy to parse and print.