Approximation algorithms for visibility computation and testing over a terrain
- PDF / 2,518,587 Bytes
- 7 Pages / 595.224 x 790.955 pts Page_size
- 6 Downloads / 179 Views
ORIGINAL PAPER
Approximation algorithms for visibility computation and testing over a terrain 3 · Morteza Golkari1 ¨ ukbay ¨ Sharareh Alipour1 · Mohammad Ghodsi1,2 · U˘gur Gud
Received: 19 April 2016 / Accepted: 6 December 2016 © Societ`a Italiana di Fotogrammetria e Topografia (SIFET) 2017
Abstract 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
Sharareh Alipour
[email protected] Mohammad Ghodsi [email protected] U˘gur G¨ud¨ukbay [email protected] Morteza Golkari [email protected] 1
Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
2
Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
3
Department of Computer Engineering, Bilkent University, Ankara, Turkey
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. Keywords Visibility computation · Visibility counting problem · Visibility testing problem · Approximation algorithm · Randomized algorithm
Introduction Problem statement Suppose that T is a set of n disjoint triangles representing a 2.5D terrain. Two points p, q ∈ R 3 above or on T are visible to each other with respect to T if the line segment pq does not intersect any triangle of T . A triangle ∈ T is also considered to be visible from a point p above or on T , if there exists a point q ∈ such that p and q are visible to each other. Here, the visibility counting problem (VCP) is to find the number of triangles of T that are visible from any query point p. The visibility testing problem (VTP) is also defined as follows: given a query point p and a triangle ∈ T , we want to test whether is visible from p. Definition 1 The set of all points on T that are visible from a query point p is the visibility region of p and is denoted by VR(p). Related work Computing the visible region of a point is a well-known problem appearing in numerous applications (see, e.g., Cohen-Or and Shaked 1995; Cole and Sharir 1989; Floriani and Magillo 1994; Floriani and Magillo 1996; Franklin et al. 1994; Goodchild and Lee 1989; Stewart 1998). For example, the coverage area of an
Appl Geomat
antenna for which the line of sight may be approximated by clipping the region that is visible
Data Loading...
