Approximation algorithms for visibility computation and testing over a terrain

Given a 2.5D terrain and a query point p on or above it, we want to find the triangles of terrain that are visible from p . We present an approximation algorithm to solve this problem. We implement the algorithm and test it on real data sets. The experimental results show that our approximate soluti...

Full description

Saved in:
Bibliographic Details
Published in:Applied geomatics 2017-03, Vol.9 (1), p.53-59
Main Authors: Alipour, Sharareh, Ghodsi, Mohammad, Güdükbay, Uğur, Golkari, Morteza
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Comparative analysis
Computation
Earth and Environmental Science
Geographical Information Systems/Cartography
Geography
Geophysics/Geodesy
Mathematical models
Measurement Science and Instrumentation
Original Paper
Remote Sensing/Photogrammetry
Surveying
Testing
Visibility
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a 2.5D terrain and a query point p on or above it, we want to find the triangles of terrain that are visible from p . We present an approximation algorithm to solve this problem. We implement the algorithm and test it on real data sets. The experimental results show that our approximate solution is very close to the exact solution and compared to the other similar works, the computational cost of our algorithm is lower. We analyze the computational complexity of the algorithm. We consider the visibility testing problem where the goal is to test whether a given triangle of the terrain is visible or not with respect to p . We present an algorithm for this problem and show that the average running time of this algorithm is the same as the running time of the case where we want to test the visibility between two query points p and q . We also propose a randomized algorithm for providing an estimate of the portion of the visible region of a terrain for a query point.
ISSN:1866-9298
1866-928X
DOI:10.1007/s12518-016-0180-9