<br><font size=2 face="sans-serif">Tim/Schuyler/Frank -- see the messages below mine which prompted this one.</font>
<br>
<br><font size=2 face="sans-serif">I asked on the list about such a spatial sorting program in a post entitled "Query: sortshp, spatially clustering shapefiles on disk" on or about 23rd July 2004. I discussed a couple of references in that message which deal with this idea well.</font>
<br>
<br><font size=2 face="sans-serif">I didn't get a positive response, so I did it myself. My program's based on programs in the mapserver distribution (particularly, maptree.c which is Frank's). If my memory serves me correctly, it's pretty basic - reads and writes each shape one at a time, then reads and writes the DBF file records one at a time. Nevertheless, on our Sun system (a 480R with 16 GB), it sorted the entire cadastre for my state (1.3 GB, 4 million polygons) in about 8 minutes. I've marginally altered Frank's spatial indexing so that it visits nodes following a Hilbert-Peano scan, so that sequential nodes are spatially adjacent.</font>
<br>
<br><font size=2 face="sans-serif">I shall re-visit my code and polish it up. It would fit in with "shptree" and "maptree" from which it's derived. What's the best way of contributing this to the codebase?</font>
<br>
<br><font size=2 face="sans-serif">Sorry about the delayed reply, but I only read the digest.</font>
<br>
<br><font size=2 face="sans-serif">Regards</font>
<br>
<br><font size=2 face="sans-serif">Richard E. Roger</font>
<br>
<br><font size=2 face="sans-serif">"Dr. R. E. Roger NSW Department of <br>
Primary Industries<br>
Spatial Information Officer Systems 161 Kite St<br>
Resource Information Unit Locked Bag 21<br>
ORANGE NSW 2800<br>
ph: (02) 6391 3697 fax: (02) 6391 3740</font>
<br>
<br><font size=2 face="Courier New">------------------------------<br>
<br>
</font>
<br><font size=2 face="Courier New">Date: Wed, 27 Apr 2005 17:19:05 -0500<br>
From: Tim Tsai <ttsai@POBOX.COM><br>
Subject: Re: tiling shape files, or shptree<br>
<br>
On Wed, Apr 27, 2005 at 02:48:07PM -0400, Frank Warmerdam wrote:<br>
> Tim / Schuyler,<br>
><br>
> Yes, I've thought about that sometimes too. It might be helpful to have<br>
> a tool that would would copy a shapefile in .qix traversal order. That<br>
> is to reorder the features by locality as determined by the quadtree index.<br>
> That might given the convenient managability of one big shapefile<br>
> with the locality benefits of tiling.<br>
<br>
That should help clustering the blocks together. I am not<br>
very familiar with the .qix format but I don't think it actually<br>
tries to balance the quadtree at all right now. A mostly balanced<br>
algorithm with a re-sorted shapefile might be a good approach.<br>
<br>
Also, I wonder what would happen if you run a big shapefile through<br>
shp2tile, merge the shape files back sequentially into a big file,<br>
then run shapetree on it. Seems like you'd get most of the effects<br>
of above.<br>
<br>
http://www.cs.umd.edu/~brabec/quadtree/ has lots of spatial<br>
index algorithms. One of these days I'll read through all of them.<br>
<br>
Tim<br>
<br>
<br>
<br>
This message is intended for the addressee named and may contain confidential information. If you are not the intended recipient or received it in error, please delete the message and notify sender. Views expressed are those of the individual sender and are not necessarily the views of their organisation.</font>