Copying shapefiles in spatially sorted (.qix) traversal code

[Richard E. Roger]

Tim/Schuyler/Frank -- see the messages below mine which prompted this one.

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.

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.

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?

Sorry about the delayed reply, but I only read the digest.

Regards

Richard E. Roger

"Dr. R. E. Roger                                    NSW Department of
                                         Primary Industries
Spatial Information Officer Systems                    161 Kite St
Resource Information Unit                     Locked Bag 21
                                           ORANGE NSW 2800
ph: (02) 6391 3697                               fax: (02) 6391 3740

------------------------------


Date:    Wed, 27 Apr 2005 17:19:05 -0500
From:    Tim Tsai <ttsai at POBOX.COM>
Subject: Re: tiling shape files, or shptree

On Wed, Apr 27, 2005 at 02:48:07PM -0400, Frank Warmerdam wrote:
> Tim / Schuyler,
>
> Yes, I've thought about that sometimes too.  It might be helpful to have
> a tool that would would copy a shapefile in .qix traversal order.  That
> is to reorder the features by locality as determined by the quadtree
index.
> That might given the convenient managability of one big shapefile
> with the locality benefits of tiling.

  That should help clustering the blocks together.  I am not
very familiar with the .qix format but I don't think it actually
tries to balance the quadtree at all right now.  A mostly balanced
algorithm with a re-sorted shapefile might be a good approach.

  Also, I wonder what would happen if you run a big shapefile through
shp2tile, merge the shape files back sequentially into a big file,
then run shapetree on it.  Seems like you'd get most of the effects
of above.

  http://www.cs.umd.edu/~brabec/quadtree/ has lots of spatial
index algorithms.  One of these days I'll read through all of them.

  Tim



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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/mapserver-users/attachments/20050429/87751594/attachment.htm>