[Liblas-devel] Indexing for libLAS

[Wes Toews]

Do you have approximate performance numbers (anecdotal is fine) for the data
structure? Is it a 3d or 2d solution? And, what sort of overhead does it add
to the LAS file size?

That said, any ability to perform the 'return n points within a distance of
a current point' would be a hugely welcome addition.
Thanks,
On 15 August 2010 07:15, Howard Butler <hobu.inc at gmail.com> wrote:

> 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
> >_______________________________________________
> Liblas-devel mailing list
> Liblas-devel at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/liblas-devel
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/liblas-devel/attachments/20100815/750b3275/attachment.html