background image

 

Abstract 

 

 

The  availability  of  geospatial  data  is  increasing  daily,  making  the  development  of 

applications that process data for large areas in high definition necessary. Viewshed analysis is 

one of the applications that processes geospatial data to calculate the visibility of every point 

of the digital elevation model  from an observer for a predetermined area. It is an application 

widely  used  in  many  scientific  fields  for  projects  with  practical  and/  or  aesthetic  value.  For 

example,  analysing  the  disturbance  of  the  field  of  view  facilitates  the  recognition  of  areas, 

whose visibility is not blocked by anthropogenic constructions. As a result, the detection of the 

areas  that  exhibit  rare  natural  beauty  allows  their  exploitation  for  recreational  purposes. 

Regardless of the great benefits of the visual analysis, there is a major drawback in the usability 

due to the requirements of advanced processors and the increased time required to  derive the 

results;  thus,  limiting  their  practicality.  Aim  of  this  study  is  to  develop  an  algorithm  that 

optimizes high accuracy while minimizing the time necessary to achieve it.  

 

The  developed  algorithm  is  based  on  Van  Kreveld's  [1]  method,  which  is  most 

effective  in  reaching  high  performance  alongside  precision,  when  compared  to  similar 

algorithms.  Meanwhile,  the  interpolation  technique  is  used  in  order  to  calculate  the  exact 

altitude  of  every  available  spot,  which  leads  to  maximizing  the  precision  of  the  algorithm. 

Furthermore,  we  succeed  in  decreasing  the  execution  time  by  implementing  parallelization 

techniques with the use of message passing interface (MPI). This results in an algorithm that 

manages both precision and realistic execution time, which is practical for everyday use. 

 

key  words:  Interpolation  technique,  Van  Kreveld’s  algorithm,  Viewshed  analysis, 

Parallelization, Message Passing Interface, Line of sight