An Art Gallery Approach to Submap Meshing

The Art Gallery Theorem and its lemmas have been used since the 1990s in the area of computer graphics to decompose orthogonal polygons into convex sub-regions. This paper extends and improvises Art Gallery concepts to non-orthogonal, generic polygons to perform a multiblock decomposition of faces into a set of maximal, single-loop, convex sub-faces. Concepts such as staircase, dent and notch are used to categorize face concavities and virtual vertices are inserted on smoother concave boundary bends. Multiblocking is performed without the need for Delaunay triangulation with the aid of a notch diagram. A light-weight, mesher-native topology builder that uses virtual topological elements is proposed to construct a virtual topology network from a notch diagram. Subsequently, virtual faces are processed for transfinite meshing. Results indicate the advantage of the proposed technique over existing procedures in terms of orthogonality and anisotropy.