[Liblas-devel] Squeeze me

[Howard Butler]

On Mar 9, 2010, at 1:31 PM, Black, Michael (IS) wrote:

> Actually, what is the "spatial order" of data that is tilted due to a non-0/90/180/270-degree flight path?
> What you really need is a spatial lookup -- not spatial ordering....there is no such thing as "spatial ordering" unless you'lre talking  about sorting just along one axis (x,y, or z).
>  
> The LIDAR guys aren't polite enough to collect perfectly aligned lat/lon routes.
>  
> If you want to be able to easily do spatial queries try using SQLITE and turn on the RTree.  An RTree is kind of a waste for a fully populated LIDAR cloud but it should work just fine.
> http://www.sqlite.org/
>  
>  
> We just built our own indexer so we could say "give me all points within N meters of here" rather than using an RTree or such.
>  

The development version of libLAS has a framework that I have been building to allow people to plug in their own indexing.  Right now it is based on libspatialindex [1], which is rtrees, but I also plan to enable something like libANN [2] [3], which are a bucketload of indexing methods more related to point data.  I suspect we should come up with some sort of IndexI interface would be able to be optionally provided that would have methods to index the data as well as support fast bbox queries.

Rtrees are indeed quite poor for indexing lidar data unless you are storing patches or blocks.  They're space inefficient and inserts are slow unless you pre-sort.  

In my mind, and ideal indexing approach for LAS is to store the index in the LAS file as VLR records, much as Merrick is doing.  I wish they would release details of their approach so we could all just use that as a starting point.

Howard

[1] http://www2.research.att.com/~marioh/spatialindex/
[2] http://www.cs.umd.edu/~mount/ANN/
[3] http://hg.liblas.org/ann