Copying shapefiles in spatially sorted (.qix) traversal code

[Tim]

Richard, that sounds great.  I just read your July 2004 post and it
seems to me if you've modified the program to be one pass, there's
no reason why it couldn't replace the existing sortshp or maptree
(perhaps with a added flag for compatibility reasons).  Have you
done any performance measurements of your new code?  Thanks for the
interesting spatial indexing paper references too.

I'll let Frank or others answer your question regarding contributing
the code.  You can probably post it to the developer's list and let
somebody take it from there.

Thanks,

Tim

On Fri, Apr 29, 2005 at 04:52:54PM +1000, richard.roger at agric.nsw.gov.au wrote:
> 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.