[Liblas-devel] Indexing for point clouds

[Howard Butler]

Robert and Marios on the spatialindex list have also given me some  
great suggestions, especially Marios' about using bulk loading, which  
is relevant because LAS data are practically *never* updated.

http://lists.gispython.org/pipermail/spatialindex/2009-April/000058.html
http://lists.gispython.org/pipermail/spatialindex/2009-April/000059.html

On Apr 21, 2009, at 3:41 PM, Etienne Bellemare Racine wrote:

> My experience with this is extracting lidar subsets with Liblas. And  
> I thought that if it was possible to just sort the file by  
> coordinate (i.e. rewriting it ordered) it would enable to only scan  
> a part of the file. Maybe ordering the file would take some time  
> (probably a lot, do you have an idea ?), but if you are using it  
> frequently for an extraction, it could worth it, I don't really know  
> what are the gains.


On Apr 22, 2009, at 5:18 AM, Hamish wrote:
>
> also anything that introduces memory or processing time overheads must
> be built in a way that will scale to much larger datasets than we have
> today (but might in 5 years time, when hopefully this fine library is
> still in active use)
>
>

Yes, reordering isn't practical, but the biggest problem is that it  
changes the original data.  My scenario is the data warehousing  
scenario.  Imagine LAS files at 1m density covering the continental  
US.  Data accounting is very important in that scenario, and while  
libLAS isn't the database in that scenario, it can play a strong role  
as an intermediary.  Intermediaries shouldn't change data.

On Apr 22, 2009, at 4:45 AM, Volker Wichmann wrote:

> I've no experience with either spatialindex nor GML LidarK, but  
> maybe you can find some hints on
>
> http://research.graphicon.ru/3d-point-data-processing/gml-lidark-library-6.html
>
> There's some discussion on pro/cons of various indexing approaches.

An excellent lead, thanks.  Do you happen to know if it is compatible  
with libLAS' license?

On Apr 22, 2009, at 7:49 AM, Etienne Bellemare wrote:

> Is speed improvement the only virtue of spatial indexing, or am I  
> wrong ?

Spatial window querying speed is the strongest virtue, but there are a  
few others.  LAS is essentially just an archive format right now, with  
most softwares writing their own format to work with the data  
internally.  libLAS' ability to do fast window queries with an index  
would give developers another reason to stick with LAS rather than  
rolling their own -- lessening the chance of dropping data and  
increasing libLAS' uptake.

Another reason is mass parallelization.  Imagine a cluster of Amazon  
EC2 instances processing the indexes of 1000s of LAS files and then an  
operation that trolls through the indexes and merges them all together.