Copying shapefiles in spatially sorted (.qix) traversal code

[Ed McNierney]

Richard -

Thanks - this is nice stuff.  Although I have not benchmarked it
carefully, I believe that the reason many users see a benefit from a
TILEINDEXed set of smaller shapefiles when compared to a single large
shapefile is the physical grouping of geographically nearby features on
disk.  A sorting scheme like yours might both eliminate the need to chop
up larger shapefiles (if that's not otherwise desirable to the user)
and/or improve smaller shapefile performance where the data are not
geographically sorted to begin with.

I've got a few large vector data sets I would be happy to experiment
with when the code's available.

        - Ed

Ed McNierney
President and Chief Mapmaker
TopoZone.com / Maps a la carte, Inc.
73 Princeton Street, Suite 305
North Chelmsford, MA  01863
ed at topozone.com
(978) 251-4242  

-----Original Message-----
From: UMN MapServer Users List [mailto:MAPSERVER-USERS at LISTS.UMN.EDU] On
Behalf Of Frank Warmerdam
Sent: Friday, April 29, 2005 10:02 AM
To: MAPSERVER-USERS at LISTS.UMN.EDU
Subject: Re: [UMN_MAPSERVER-USERS] Copying shapefiles in spatially
sorted (.qix) traversal code

On 4/29/05, richard.roger at agric.nsw.gov.au
<richard.roger at agric.nsw.gov.au> wrote:
> 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.

Richard, 

Cool! When you submit the code, please be fairly specific about this
"Hilbert-Peano Scan" as I would potentially like to apply it in the
seperate version of the spatial index code in in shapelib and OGR. 
  
> 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?

Please submit the updates via bugzilla. 

Best regards,
-- 
---------------------------------------+--------------------------------
---------------------------------------+------
I set the clouds in motion - turn up   | Frank Warmerdam,
warmerdam at pobox.com
light and sound - activate the windows | http://pobox.com/~warmerdam
and watch the world go round - Rush    | Geospatial Programmer for Rent