Data Formats and Spatial Indexing

Three chapters have gone into getting the measurement right. You can specify an acquisition, place its returns in a stated reference frame, and put an accuracy figure on them. Now the delivery arrives, and it arrives as files: a folder of tiles in a container somebody else chose, in an order somebody else chose. They hold whatever attributes that container had fields for. Two questions have to be answered before any method in this book touches those points. What did the container keep? And how do you find, for one point, the points near it?

Take the first at the scale it is decided on. The format a national mapping agency writes its annual output in determines whether that output will still be queryable in five years or readable only through an obsolete tool chain. And the volumes make the choice binding: tens of terabytes a year for a typical agency, hundreds for the largest high-density programmes. France's LiDAR HD accounts for roughly three petabytes over its 2021–2026 campaign. So nothing at that scale is opened by hand, and you settle the container and the way into it before the first processing step, not after.

The second carries a cost you can compute. Say you want a neighbourhood statistic for every point of a 50 GB airborne laser scanning (ALS) tile. For every point you have to find the points that lie near it, and with no spatial index that means measuring the distance to all the others. That tile holds roughly 1.5 billion points at the 34 bytes a point of Point Format 3, so a brute-force sweep computes about $10^{18}$ distinct pairwise distances. That is three decades of work at a billion distance computations per second, for one statistic on one tile.

And conversion carries a hazard of its own, this one silent. Say you convert a terrestrial laser scanning (TLS) dataset from scanner-native E57 to LAS. The output keeps only the attributes LAS has fields for. You won't see the loss in a viewer, because every point is still there and the file is still valid. In figure 4.2 you can find what each container carries and what it has no field for.

How much computation does an index save you? On the airborne tile of figure 4.13, at one million points, a single $k$-NN query answered by scanning every point takes 1 688 times as long as the same query answered through a k-d tree. A pass over every point's neighbourhood falls from 2.8 hours to 5.9 seconds. Nothing about the points changed. What changed is the order they are held in, and the structure built over them.

So everything downstream rests on those two decisions. The scans delivered by the platforms of chapter 3 arrive as files in the formats treated here. The neighbourhood queries that drive downsampling (chapter 5), filtering (chapter 6), normal estimation (chapter 7), registration (chapter 8), and feature extraction (chapter 10) all run on the indexes we build in this chapter. Let's start with the containers, since what a file kept determines what you have left to index.