I/O-efficient contour queries on terrains
Pankaj K. Agarwal, Thomas Mølhave, Bardia Sadri · 2011
A terrain M can be represented as a triangulation of the plane along with a height function associated with the vertices (and linearly interpolated within the edges and triangles) of M. We investigate the problem of answering contour queries on M: Given a height ` and a triangle f of M that intersects the level set of M at height `, report the list of the edges of the connected component of this level set that intersect f, sorted in clockwise or counter-clockwise order. Contour queries are different from level-set queries in that only one contour (connected component of the level set) out of all those that may exist is expected to be reported. We present an I/O-efficient data structure of linear size that answers a contour query in O(logB N + T/B) I/Os, where N is the number of triangles in the terrain and T is the number of edges in the output contour. The data structure can be constructed using O(Sort(N)) I/Os.