Partial edge visibility in linear time

Abstract

This research addresses the problem of partial edge visibility. This problem stems from work done in the ray guarding of configurations of adjacent rectangles [7]. In ray guarding these configurations it is necessary to be able to find a straight line through a set of adjacencies in a group of adjacent rectangles. If the adjacent rectangles are visualised as an orthogonal polygon whose boundary is the boundaries of the rectangles excluding the adjacencies between the rectangles then the problem is one of finding a straight line from one edge in the polygon to another that is completely contained in the polygon. Partial edge visibility is thus the ability to determine whether one edge of a polygon can "see" another edge in the same polygon. This research derived an algorithm to answer the question "Is some part of edge ef of a given simple polygon visible to some part of edge el of the polygon?" The problem domain places some constraints on the simple polygons that can occur and these constraints were used in developing the algorithm. The final algorithm obtained is linear in the number of polygon vertices. Future work in this area will focus on adapting the algorithm to solve the problem of ray guarding general convex polygons.