How to implement viewshed calculation?

Question

I'm looking for a way to implement visibility (aka viewshed). I found a previous GIS SE question that suggested a few GIS applications (not what I need - I'm trying to embed the calculations), and also SAGA. SAGA looks more like what I'm looking for (C++, Java, C# classes), but I can't understand enough of the API documentation to figure out what classes I even need to instantiate (or subclass).

I'm not tied to the idea of SAGA - I'm just looking for library / engine that can do intervisibility calcs.

The constraints are that it needs to be:

• reasonably "light weight" (since I'd like to be able to cover embedded / mobile)
• reasonably open source (since my application will be open source, although I'm flexible on exactly which license as long as its (L)GPL compatible).

Can anyone recommend such a library or engine, and provide a description of or link to which bit of the library or engine I need to use to viewshed calculations?

Alternatively / in-addition, I'd also appreciate references to papers or tutorials that explain how to do these calculations in an efficient way (as applicable to embedded / mobile devices, so a GPU based implementation may not be as useful as something that is more general, and handles low power devices)

My preference is an existing implementation, rather than creating something myself (which is a a backup option).

Edit: C++ isn't a firm requirement - anything reasonably portable (C#, C++, Java) will do. I'm trying for a library or templates rather than embedding a large application.

Answer 1

As you would have seen from the referenced GIS SE question, there doesn't appear to be much in the way of viewshed stand-alone packages at least in the Open Source market beyond SAGA and GRASS GIS. Apart from writing a wrapper around the code for these algorthims you may end up implementing viewshed yourself unfortunately. (Though I would love to be corrected on this.)

If you read the documentation for the GRASS r.viewshed function it provides a broad description of the algorithm and a reference to the following paper which thoroughly discusses one viewshed algorithm:

Computing Visibility on Terrains in External Memory. Herman Haverkort, Laura Toma and Yi Zhuang. In the Proceedings of the 9th Workshop on Algorithm Engineering and Experiments / Workshop on Analytic Algorithms and Combinatorics (ALENEX/ANALCO 2007).

Alternately the Wikipedia article on Viewshed provides references:

Wu, H., Pan, M., Yao, L., & Luo, B. (2007). A Partition-based Serial Algorithm for Generating Viewshed on Massive DEMs. International Journal of Geographical Information Science, 21(9), 955-964.

Answer 2

There is a freeware package called RadioMobile which is designed for radio communication studies that generates a view shed. The output is based on a DEM input and can be either a vector (point file) or Raster. I have been able to use the vector point file to create polygons through some scripting which I will be happy to share with you. Since you can set a palette on the raster output you could also convert the raster to vector using gdal.

The program has a gui but can also be run in batch mode so you can easily incorporate it into a program. While there are a lot more options than required for a traditional viewshed you can set these to null so that the effects such as the transmitter power aren't included - see http://www.g3tvu.co.uk/RM_Batch_Files.htm

The program is at http://www.cplus.org/rmw/rme.html The author is very helpful as well.

Hope this helps,