c - shapelib 中的 Shapefile 四叉树

Question

在shapelib ，我注意到相当多的代码是用来处理 Shapefile 四叉树的。例如，工具 shptreedump(在 shapelib 源代码中)。

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 ) ) ...

我想我在阅读 ESRI Shapefile Technical Description 之后对 shapefile 格式已经相当熟悉了。 .但是我看不到任何内部树结构本身。所以我的问题是，shapefile 四叉树的用途是什么？如果可能的话，解释 shapefile 四叉树的实现。

谢谢。

Answer 1

如果您查看引用文本的末尾，就在您停止的地方，有很多右括号......很好的旧 Lisp 风格编码:

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

R代表树的根，那么你在()中有四棵子树加上实际的数据st1，我把这4棵子树记为st1...st4。 st21 代表第二层的第一个子树。可以标记子树，或者如果其中任何一个为空，则用 () 表示。易于解析和打印。