Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Empirical comparison of data structures for line-of-sight computation

: Fünfzig, Christoph; Ullrich, Torsten; Fellner, Dieter W.; Bachelder, Edward N.


Institute of Electrical and Electronics Engineers -IEEE-:
IEEE International Symposium on Intelligent Signal Processing, WISP 2007 : 3-5 Oct. 2007, Alcala de Henares (Madrid) Spain
Piscataway, NJ: IEEE, 2007
ISBN: 978-1-4244-0830-6
ISBN: 1-4244-0830-X
6 pp.
International Symposium on Intelligent Signal Processing (WISP) <2007, Alcala>
Conference Paper
Fraunhofer IGD ()
geographic information systems (GIS); data structure; terrain modeling

Line-of-sight (LOS) computation is important for interrogation of heightfield grids in the context of geo information and many simulation tasks like electromagnetic wave propagation and flight surveillance. Compared to searching the regular grid directly, more advanced data structures like a 2.5 d kd-tree offer better performance. We describe the definition of a 2.5 d kd-tree from the digital elevation model and its use for LOS computation on a point-reconstructed or bilinear-reconstructed terrain surface. For compact storage, we use a wavelet-like storage scheme which saves one half of the storage space without considerably compromising the runtime performance. We give an empirical comparison of both approaches on practical data sets which show the method of choice for CPU computation of LOS.