A digital geometry on the tetrakis square tiling-Distance and coarsening

Abstract

There are various tessellations of the plane, including three regular and eight semi-regular tilings. The square grid is self-dual, and the hexagonal and triangular tilings are dual to each other. The semi-regular tessellations are based on more than one type of regular tiles, while their dual tilings are based on a sole but not a regular tile. In various applications, including Geographical Information Systems, it is worth considering non-regular grids instead of the most used square grid. In this article, we are interested in the dual of the semi-regular truncated quadrille tiling, T(8,8,4), which is also known as the Khalimsky grid due to its connectedness structure. In our grid, which is called the tetrakis square or kisquadrille tiling, while it is denoted by D(8,8,4), we consider the right-angled triangle regions of the usual two-dimensional Khalimsky graph as tiles/pixels. We give an easy-to-use coordinate frame addressing the triangles of all the four different orientations. Neighbor relations are described mathematically based on this frame. Based on the shortest path algorithm, a closed formula is proven to compute the digital, that is, path-based distance on this grid. Some properties of the distance function have also been studied. Hierarchical coarsening is a frequently used technique both in Geometric and Geographical Information Systems to rescale some parts of the map. The tetrakis square grid is apt for hierarchical coarsening, and thus, it can easily be used in image compression and multigrid and other related methods.