Finding the Visibility Matrix of an Orthogonal Polygon
Amrita Agarwala · 2012
An algorithm to find the visibility matrix of an orthogonalpolygon is presented here. The algorithm is applied on the vertices of theinput polygon in an anti-clockwise manner to find the visibility matrixwhich indicates the visibility of other vertices from the given vertex. Thealgorithm uses combinatorial techniques to determine the visibility of avertex from a given vertex. The visibility matrix captures the visibility ofvertices from each vertex of an input polygon in the form of a matrix. Theruntime of the algorithm is ) ( 2 n O . An analysis of the visibility matricesof different isothetic polygons derived from the different shape images. 1 INTRODUCTON The visibility problem is an important research topic in computational geometry.For any two points x and y in the plane or space, x is said tobe visible from y or vice versa if and only if the line segment joining them doesnot intersect any object.Linear time algorithms for the problem of computing the visibility polygon are presented in [4] and [5]. Here, each edge of the polygon is assumed to beopaque. However, a modified version [8] of Lee's algorithm [4] is presented withthe proof of correctness. A linear time algorithm [9] deals with the similar problem for an orthogonal polygon. The notion of visibility of the polygon from a given edge is presented in [10]. The problem is solved in o(nlog log n) time presented in [11]. In the three-dimensional case, the well-known visibility problem for a set ofpolyhedra is the removal of all edges or parts of edges that are hidden from anobserver at some position (viewpoint), and it is referred to as the hiddenlineelimination problem. The visibility problems for orthogonal objects in two-or three dimensions in o(n log n+k) time and o(n) space has been addressed in[12].There are various notions of visibility studied by researchers. In [13] clear visibility is introduced. Two points u and v in a polygon P are called clearly visible ifthe open line segment joining u and v lies in the interior of P. Staircase visibility has been studied in [14], [15], [16]. If a path inside arectilinear polygon P is monotone with respect to both axes, the path is calledstaircase path in P. Two points u and v in Pare called staircase visible if thereis a staircase path between u and v in P.Rectangular visibility has beenpresented in [17], [18].Circular visibility, another variation of visibility, has been given in [19], [20].In[21] the study of X-ray visibility, which is another variation of visibility is given.Two points u and v are X-ray visible in a polygon P if the segment uv doesintersect more than a fixed number of edges of P.Point visibility is dealt in [22]. In this paper, an algorithm to find the visibility matrix of an orthogonalpolygon is presented. The rest of the paper is organized as follows. The preliminary definitions are presented in Sec. 2. Section 3 presents the algorithm witha discussion on the time complexity. The experimental results on different inner polygons of different images are presented in Sec. 4. Section 5 presents theconclusion with a note on future direction of this work. 2 PRELIMINARIES Definition 1: A subset of 2 Z in which every pair of points is k-connected, iscalled a k-connected set. A digital object A is said to be 8-connected subset of 2 Z whose complement S Z 2 is a 4-connected set [23]. Definition 2: The background grid is given by G=(H,V), where H & V represent two sets of equispaced horizontal and vertical grid lines respectively. Thegrid size g is defined as the distance between two consecutivehorizontal/verticalgrid lines. A grid point is the point of intersection of a horizontal and a verticalgrid line [24]. Definition 3: The inner (isothetic) cover (IIC) [24], denoted by ) (S P , isa set of inner polygons and (inner) hole polygons, such that the region, given bythe union of the inner polygons minus the union of the hole polygons, containsa unit grid block (UGB) if and only if it is a subset of S. The border BP of Pis the set of points belonging to its sides. Proc. of the Intl. Conf. on Advances in Computer Science and Electronics Engineering Editor In Chief Sahil Seth. Copyright © 2012 Universal Association of Computer and Electronics Engineers. All rights reserved. ISBN: 978-981-07-1403-1 doi:10.3850/978-981-07-1403-1 134 405 Proc. of the Intl. Conf. on Advances in Computer Science and Electronics Engineering The interior of P is the set of pointsin the union of its constituting UGBs excluding the border of P .An inner isothetic polygon P can be defined as follows: Inner polygon:P , , . . 0 , !. Definition 4: P is an orthogonal polygon if and only if each of its verticesis a grid point and each of its edges is axis-parallel. Definition 5: The visibility graph, ) , ( E V G ∈ of a simple polygon is defined asfollows. The vertices of the graph are the vertices of the polygon and E v v j i ∈ ) , ( ifthe line segment joining the corresponding vertices in the polygon lies completelyinside the polygon. Definition 6: The visibility matrix is a n x nmatrix for a polygon with n vertices defined as: v[ i,j]=1 ,if i is visible from j 0 ,otherwise 2.1 Deriving the Inner Isothetic Cover: Inner isothetic cover(Ain)of a digital object A with grid G is the maximum area orthogonal polygon that can inscribe into the object A. The algorithm TIPS [25] computes the ordered set of vertices of Ainusing a combinatorial technique based on the fact that the grid points lying on/ inside/ outside the object boundary. A grid point p is classified into 5 categories based on how many of the four cells, each of size g x g, incident at p, are fully occupied by the object points (i.e.,pixels from A). Say, the number of fully occupied cells incident at q is ] 4 , 0 [ ∈ i . Then q is classifed to class ]} 4 , 0 [ { ∈ i Ci , as shown in Fig. 1. The classification of the classes are shown below. (i) C0:None of the 4 cells occupied by object point. So, q is not a vertex of Ain; (ii) 1 C : Exactly 1 cell is occupied. q is a 90 0 vertex of Ain (Fig. 1(a)); (iii) C2: (a) If two adjacent cells are fully occupied, then q is an edge point(Fig. 1(c)); (b) If diagonally opposite cells are fully occupied, then q is a 90 vertex of Ain ( Fig. 1(d)); (iv) C3: q is classified as a 270 0 vertex (Fig. 1(b)); (v) C4: q is not a vertex of Ainand lies inside Ain . Fig1: Different vertex types 3 PROPOSED ALGORITHM 3.1 Algorithm The visibility matrix of a given polygon is computed by traversing the polygon in an anticlockwise manner from the given vertex from which the visibilities of other vertices are to be computed. The same procedure is followed from othervertices to compute the complete visibility matrix. Let 0 v be the reference pointfrom which the visibility of other vertices are to becomputed. If 1 v is the vertexnext to 0 v in P, then 1 0v v defines the reference axis. Each vertex i v is associated with a coefficient of concavity, i α , its relative angle i μ with the reference axis(the angle between 1 0v v and the edge i v v0 ). The concept of concavity coefficientis introduced to capture the fact when the concavity coefficient exceeds a specificvalue then the vertex is well inside a concavity, thus not visible from 0 v . The internal angle of a vertex i v is denoted by i φ (either90 or 270for an isotheticpolygon). i x , i y are defined as the relative, unsigned distance between ( 0 v , 1 v )along reference i X axis and i Y axis respectively having 0 v as origin and 1 0v v as i X reference axis. Also, the relative direction of traversal, either clockwiseoranticlockwise, from 1 − i v to i v is associated with i v as i d . A stack, S, is usedwhich contains the vertices visible from 0 v at a given point of traversal. As thetraversal proceeds to the next vertex, the visibility of the current vertex and theearlier vertices in the stack are analyzed using a combinatorial technique basedon i α , i φ ,and the distance of i v from 0 v . It may so happen that some of thevertices in S have to be popped. Once the traversal is completed, S contains theset of vertices which are visible from 0 v .The reference vertex, 0 v , can be either a90vertex, or a 270vertex. It may be noted that for the first vertex 1 v , 1 α is 1. The value of α is incremented(decremented) by one for any anticlockwise (clockwise) movement during thetraversal of the polygon. It may also be notedthat when 0 v is a 90 vertex, theconcluding vertex of the traversal, i.e., 0 v , has α = 4.For example, in Fig. 2(a), each vertex with their concavity coefficients areshown. For the vertex 6 v (Fig. 2(a)), 6 α is 6, so 6 v is invisible from 0 v . It is alsoevident that 7 v and 8 v having 7 α = 7 and 8 α = 6 are also invisible from 0 v .Similarly, if 0 v is