Consider a terrain and a set of viewpoints placed anywhere on or above the terrain. We are interested in computing the visible regions of the terrain, that is, all points which are seen by at least one of the viewpoints.
While being of interest on its own, visibility computations occur as part of other algorithms. For example, in the terrain guarding problem (TGP) a lot of single viewpoint queries for the same terrain need to be processed.
For a single viewpoint p, the visibility region can be computed in O(n) time by computing the visibility polygon of p. We can close the unbounded space above the 1.5D terrain to transform it into a simple polygon and use one of several linear time algorithms.
A naive approach to determine the visibility map for multiple viewpoints is therefore to compute and union the visibility region for each viewpoint. This obviously takes O (nm) time. Recently Löffler et al. proposed a better solution: an O (n + m log m) sweep line algorithm to compute the visibility map for viewpoints placed on the terrain vertices.
We implemented this algorithm and will release it as part of an upcoming CGAL package.
However, with regard to real-world terrain data, an implementation for visibility in 2.5D terrains is far more interesting, albeit more complex and challenging. While the use-cases for 1.5D terrains seem very limited and somewhat artificial, 2.5D terrains have direct applications in geographical information systems and terrain analysis
Additionally, there is a broad range of digital elevation data publicly and freely available, which was gathered through the Shuttle Radar Topography Mission (SRTM) and the Advanced Spaceborne Thermal Emission and Reflection Radiometer (ASTER) instrument of the Terra satellite. Overall, it seems only logical to make the step to 2.5D visibility and to provide an according implementation for CGAL sometime in the future.
| No entries found. |
Ist hier derzeit keine offene Arbeit zu vergeben? Oder interessiert dich das Projekt, aber es ist einfach nicht das richtige Thema für dich dabei? Dann wende dich einfach direkt an uns! Wir haben laufend Ideen für mögliche Themen in verschiedenen Bereichen, die aber vielleicht im Moment noch nicht zu einer konkreten Aufgabenbeschreibung ausgearbeitet sind. Vielleicht finden wir dann gemeinsam auch für dich eine passende und interessante Aufgabe.
| No entries found. |
You are welcome to contact the project members for further information.