The Visibility Graph

Introduction

A visibility graph of a polygon scene shows the visibility relations between the separate vertexes of a scene. For Instance it could be used for the planning of a route of a punctiform robot inside this scene. By adding the starting position s and the target t to the visibility graph the shortest path between s and t can be determined, with the help of the Dijkstra Algorithm (Dijkstra, 1959). This is possible, because the path must lead through convex vertex obstacles.

• Definition of the visibility graph
• Construction of the visibility graph
• Calculating the processing sequence
• Horizon trees
• Applet for the calculation of the visibility graph
• References

Definition of the visibility graph

According to [KK01] the visibility graph is defined as follows:

If L is a set of non crossing lines in a plane, then the visibility graph of L is a graph VisG(L)=(V,E) with

V = {all endpoints of line segments inside of L}
E = {(p,q); p,q ∈ V, segment(p,q) does not cross a line segment}

The visibility graph of a set of polygons results from VisG(L) with L={all edges of P_i} by removing all visible edges inside a polygon.
Constructing a visibility graph is not simple and it has the complexity O(n²) due to the fact that a visibility graph itself has a complexity of at least O(n²) ( cp. Figure 1 (i) ).

Figure 1: The visibility graph can contain (i) O(n²) edges, but occasionally (ii) has only O(n).

As seen in Figure 1 (ii), the complexity can be a lot smaller.

Construction of the visibility graph

A naive calculation of the visibility graph is possible in the time of O(n³). For this we have to test for a point of intersection between a possible visible edge, given by two vertexes of the polygon scene, and every segment of obstacles. If no intersection exists, then the visible edge belongs to the visibility graph. But there are much more efficient methods to calculate a visibility graph. In the following a method for the construction of a visibility graph will be presented, which has the calculating time of O(n²) and needs the storage space of O(n).

The idea of constructing a visibility graph is based on a radial sweep. In this process the visible edges are calculated radial from south to north for every vertex. While doing this each for the vertex currently visible segment is stored. By using a cunning propagation of the visibility information (see Figure 2 ) between the separate vertexes the method can be optimized even more. For this the radial sweep between the separate vertexes is synchronized, so that a processing sequence of the potential visible edges is attained by means of the slope. This will be elaborated in next section.

Figure 2: Visibility information can be propagated from a to f

Figure 2 shows the processing of the visible segment(f,a). Because the segment(c,d) is currently visible from a, it will also be visible from f after processing the segment(f,a).
While initializing the radial sweep a ray is drawn due south from every vertex and a pointer is set on the next visible segment of that vertex. If there is no segment under the vertex the pointer is set to null. Subsequently the potential visible edges of the segment(p_i,q_j) (p_i,q_j ∈ V, total of O(n²); i,j ∈ N) are calculated according to the processing sequence. If no intersection point exists between the segment(p,q) and the segment visible from p, the segment is inserted into the visibility graph. An operating time of O(n²) is the result.

Calculating the processing sequence

The calculation of the processing sequence depends on the slope slope(p,q) of the segment between p and q. Thereby two types of constraints have to be fulfilled:

For the calculation of the processing sequence the characteristic trait of dual lines of points is used. A dual line of a point is defined as follows:

Point p = (p_x, p_y) → line p* = {y = p_xx - p_y)

If p = (p_x, p_y) and q = (q_x, q_y) without restriction, with p_x < q_x) is given. Then the slope of the segment is:

slope(p,q) = (q_y - p_y) / (q_xx - p_y) = x
X-coordinate of the intersection point of the dual lines p* and q*.

Figure 3 shows an arrangement of points and the appropriate dual lines.
This picture shows that the slope of the segment(e,d) is smaller than that of segment(e,d) meeting the requirement: slope(e,d) < slope(e,c). We can also see, that the X-coordinate of the intersection point between e* and d* is smaller than the one between e* and c*. Thus the pair of points (e,d) is processed before (e,c).

Figure 3: Arrangement of points (i) and the appropriate dual lines (ii).

The problem of the processing sequence will now be reduced to finding the order of intersection points, which are compliant to the order of the X-coordinates along each line. This problem can be solved by using a topological sweep [EG86]. The topological sweep in a plane is performed with a curve which topologically complies with a line. The sweep curve intersects every line in one point at most. This curve can be described as a list, which stores every line and the lines that restrict them. In our example the initial state would be:

Now it is possible to read off the list, that the lines b* and c* as well as the lines d* and e* are adjacent and therefore candidates for the next elementary intersection. After processing the intersection, the list hast to be updated. For this purpose upper and lower horizon trees are used.

Horizon trees

The horizon trees are constructed in the following way:

• Highlight every line intersected by the sweep curve
• Continue the highlighting rightwards until two lines intersect
• Proceed rightwards with highlighting at the line with greater (upper horizon tree To)/ smaller (lower horizon tree Tu) slope

Figure 4: construction of upper and lower horizon tree and the expansion of sweep curve

When an intersection point is over jumped by the sweep curve the horizon trees have to be updated. The selected edge, which was only highlighted as far as the intersection, has to be extended up to the next highlighted edge. The search for the next intersection can require up to O(n) steps.

Altogether an operating time of O(n²) is necessary for the construction of the visibility graph.

Applet for the calculation of the visibility graph

With means of the left mouse button vertexes are added to the polygon. If a polygon is closed it is filled with gray color. By touching the gray area with the left mouse button the polygon can be moved around. In the same manner the points and line segments can be moved to change the shape of the polygon. A click with the right mouse button will open the context menu. This offers many options. For instance a point, segment or polygon can be deleted, moved or resized. Also the starting position respectively target can be inserted or removed.
If a scene has been created, the visibility graph can be displayed. To make this possible the box "Show Visibility Graph" has to be checked. The edges of the visibility graph are displayed as red lines. The obstacle edges also belong to the visibility graph, but are displayed blue because of clarity reasons. The visibility graph is updated automatically if polygons, starting positions or targets can are moved. If new polygons are drawn it is advised to uncheck the box for the display of the visibility graph, because of a few display errors.
If a bounding polygon is included in the scene the box "Include Bounding Polygon" has to be checked for it to be included in the calculation of the visibility graph.

References

this document as PDF file

...page up

© University of Bonn, Computer Science I - - Last modified 23-01-2008 21:45