[Liblas-devel] Indexing for libLAS

[Howard Butler]

All,

I would like to introduce Gary Huber, who has been working with me (or trying to read my mind via email and programming accordingly, rather) to design and implement a spatial indexing mechanism for libLAS.  Followers of the list will remember that I spent quite a bit of time investigating different spatial indexing strategies for use in my work with the Oracle Point Cloud integration work that will be released as part of libLAS 1.6.  My efforts with Gary are an extension of that, and they are an attempt to come up with a generic solution to spatial window filtering for LAS files.  

While the ASPRS LAS format is never going to be a good working format for someone wanting to do high-throughput visualization, there are some distinct advantages to keeping your data in its native format and working with it as long as you can.  One significant hurdle to keeping data in LAS format is its linear nature, however.  The point data are in an order, which sometimes has meaning, and breaking free of this order to do things like select for a window often means trudging through the entire file.  A spatial index is clearly needed to speed these types of operations up, but developing one that's both generic enough for the kinds of queries people would want to do but specific enough for high-volumn scan data is quite a balancing act.  To that end, we have embarked on developing a spatial index for libLAS that has the following properties:

- A simple octree, with optional (and off by default) z-binning
- The ability to optionally store itself in VLR records
- The ability to optionally store the index in a file alongside the .las file
- Memory efficient (and configurable) index building

The code the implements the index and an attempt at an interface for using it was pushed up to the main repository about a week ago.  Gary told me he has another iteration that will be pushed up early this week.  This email is to solicit feedback on the concept, as well as attempt to attract some ideas on what incorporating spatial indexing should mean for the design of libLAS.  How would you use a spatial index of LAS data?  Do you already have some experience with this?  Are simple window queries the most common thing that people would want to do?  There isn't much time to make whole-scale design changes to libLAS before our first beta release, but I intend that code and utilities to build indexes as well as query them simply will be available as part of the libLAS 1.6 release [1].  

Looking forward to your feedback,

Howard

[1] <http://liblas.org/development/release_plan.html#generic-spatial-indexing>