source: TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/shapelib/README.tree @ 2194

Subversion URL: http://proj.badc.rl.ac.uk/svn/ndg/TI02-CSML/trunk/services/3rdParty/Quadtree-0.1.2/shapelib/README.tree@2194
Revision 2194, 6.8 KB checked in by lawrence, 13 years ago (diff)

Adding various specs and 3rd party code of interest for the CSML
services development.

Line 
1Venkat,
2
3I have completed the planned Shapefile quadtree mechanism.  The additions
4to the traditional Shapelib are found in shptree.c (functions supporting
5quad tree searching and query).  There are also some new prototypes for
6the tree stuff in shapefil.h ... including some prototypes for functions
7you don't require and hence that I haven't implemented at this time.
8
9I have also prepared a demonstration program using the API.  That is
10the ``shpdumptree'' program, with the source code in shpdumptree.c.  The
11shpdumptree program has two functions.  One is to dump an ASCII rendering
12of the internal quadtree, and the other is example use of a quad tree
13searching function.
14
15Dumping the Tree
16----------------
17
18The tree dumping is done as shown below.  The "-maxdepth" commandline
19switch can be used to control the maximum depth, otherwise it internally
20computes a ``reasonable depth'' to use based on the number of structures
21in the shapefile.
22
23warmerda@gdal[207]% shptreedump -maxdepth 6 eg_data/polygon.shp
24( SHPTreeNode
25  Min = (471127.19,4751545.00)
26  Max = (489292.31,4765610.50)
27  Shapes(0):
28  ( SHPTreeNode
29    Min = (471127.19,4751545.00)
30    Max = (481118.01,4765610.50)
31    Shapes(0):
32    ( SHPTreeNode
33      Min = (471127.19,4751545.00)
34      Max = (481118.01,4759281.03)
35      Shapes(0):
36      ( SHPTreeNode
37        Min = (471127.19,4751545.00)
38        Max = (476622.14,4759281.03)
39        Shapes(0):
40        ( SHPTreeNode
41          Min = (471127.19,4751545.00)
42          Max = (476622.14,4755799.81)
43          Shapes(0):
44          ( SHPTreeNode
45            Min = (471127.19,4751545.00)
46            Max = (474149.41,4755799.81)
47            Shapes(6): 395 397 402 404 405 422
48          )
49          ( SHPTreeNode
50            Min = (473599.92,4751545.00)
51            Max = (476622.14,4755799.81)
52            Shapes(10): 392 394 403 413 414 417 426 433 434 447
53          )
54        )
55...
56
57A structure like the following represents one node in the tree.  In
58this case it cover the region of 473599.92 < X < 476622.14,and
594751545.0 < Y < 4755799.81.  There are ten shapes within this region
60who's shapeids are 392, 394 ... 447.  This node has no children nodes.
61
62          ( SHPTreeNode
63            Min = (473599.92,4751545.00)
64            Max = (476622.14,4755799.81)
65            Shapes(10): 392 394 403 413 414 417 426 433 434 447
66          )
67
68The heirarchy of indentation is intended to show the parent, child
69relationship between nodes, with the tree being deeper the further to the
70right you go.
71
72The `-v' flag to the program can be used to expand the report to include
73the full information about shapes, not just their shapeid.  This can result
74in a report looking more like this:
75
76          ...
77          ( SHPTreeNode
78            Min = (478095.78,4751545.00)
79            Max = (481118.01,4755799.81)
80            Shapes(3):
81            ( Shape
82              ShapeId = 448
83              Min = (479988.09,4753300.00)
84              Max = (480705.59,4754236.50)
85              Vertex[0] = (480136.59,4754174.50)
86              Vertex[1] = (480229.97,4754182.00)
87              Vertex[2] = (480370.09,4754200.50)
88              Vertex[3] = (480695.12,4754236.50)
89              Vertex[4] = (480687.97,4754129.50)
90              Vertex[5] = (480650.47,4754075.50)
91              Vertex[6] = (480520.62,4753948.00)
92              Vertex[7] = (480490.00,4753900.00)
93              Vertex[8] = (480499.78,4753840.50)
94              Vertex[9] = (480500.97,4753820.50)
95              Vertex[10] = (480534.75,4753660.50)
96              Vertex[11] = (480560.00,4753565.00)
97              Vertex[12] = (480574.91,4753550.50)
98          ...
99
100While it is possible to part the output of the shptreedump program, and
101insert it into your database, my intention was that the shptreedump program
102would serve as an example of how to pre-order traversal of the quad tree,
103and collect the information you will need to insert into your database.
104I would then expect you to write a new program based on shptreedump that
105calls a C API for your database to insert objects instead of printing them
106out.  Alternatively there may be an ASCII format for loading tables that
107you could modify the program to output.
108
109Searching
110---------
111
112The other thing that you can do with the shptreedump program is to
113perform a search on the quadtree.  For instance the following shows
114searching on a small region.
115
116% shptreedump -search 471127 4751545 476622 4759281 eg_data/polygon.shp
117Shape 17: not in area of interest, but fetched.
118Shape 31: not in area of interest, but fetched.
119Shape 52: not in area of interest, but fetched.
120Shape 76: not in area of interest, but fetched.
121Shape 82: not in area of interest, but fetched.
122Shape 104: not in area of interest, but fetched.
123Shape 124: not in area of interest, but fetched.
124Shape 134: not in area of interest, but fetched.
125Shape 139: not in area of interest, but fetched.
126Shape 154: not in area of interest, but fetched.
127Shape 175: not in area of interest, but fetched.
128Shape 177: not in area of interest, but fetched.
129Shape 185: not in area of interest, but fetched.
130Shape 192: not in area of interest, but fetched.
131Shape 196: appears to be in area of interest.
132....
133
134
135I have included this capability (and the SHPTreeFindLikelyShapes() function)
136so that you can see a working example of how to search this quad tree.
137Note that searching is a multi-stage affair. 
138
139First a pass is made over the quadtree, collecting the shapeids of all
140shapes contained in a quadtree node for which the bounding rectangle overlaps
141the search rectangle.  This is all accomplished by SHPTreeFindLikelyShapes()
142in shptree.c.
143
144The second phase is to fetch the actual shapes, and verify if their bounding
145box falls within the area of interest.  This is necessary because the shape
146will tend to have a significantly smaller bounding rectangle than the tree
147node in which it is found.  This can result ``false positives'' on the first
148phase search, as indicated by teh ``not in area of interest, but fetched''
149messages above.  This stage is done in the SHPTreeNodeSearchAndDump()
150function in shptreedump.c.
151
152A possible third phase is to verify that the actualy line segments in the
153shape actually cross the area of interest.  I don't both with this as it
154is complicated, and assuming that the drawing engine takes care of clipping
155it is quite a bit easier to let it fall through.
156
157Building
158--------
159
160I have added a makefile.vc to the shapelib distribution.  After you have
161unpacked the shapefile you should have a shapelib subdirectory.  If you
162cd to that directory, and enter ``nmake -f makefile.vc'' in a DOS window
163you should be able to build everything with VC++ (assuming it is properly
164installed and in your path).
165
166You can also create a project in VC just including the files
167shpopen.c, shptree.c and shptreedump.c, building as a Win32 console
168application.
169
170For your convenience I am including prebuild .obj files, and .exe files
171in the distribution.
172
Note: See TracBrowser for help on using the repository browser.