Minimal Path-Generated Distances on the Trihexagonal Grid Having Four Neighborhoods

Abstract

Grids are more general geometric objects than discrete subgroups. However, they are still very regular. Grids are applied in crystallography, chemistry, digital image processing, computer graphics, networking, just to mention a few. Recently, distances of the points pixels of grids based on minimal path have been developed. The trihexagonal grid has three types of pixels: hexagons and two oppositely oriented triangles. Four types of neighborhood relations are considered on the grid. The first type of neighborhood contains the side-neighbors that are always a hexagon and a triangle. There are two semi-neighbor relations: the second type of neighborhood describes the pairs of closest hexagons, while the third type of neighborhood refers to the closest pairs of differently oriented triangles. Finally, the extended neighborhood relates to the closest same-shaped triangles, and this is the fourth type of neighborhood we have defined. Based on the four types of neighbor relations, four weights are used. The main result of the paper is that formulas are provided giving the minimal path between any two pixels. The length of the minimal path depends on the coordinate differences of the pixels, the relation of the weights, and the types of the two pixels. Formulas for all possible cases are given (with some usual restrictions, e.g., a step between side neighbor pixels cannot be longer, i.e., with larger weight than other steps). Some properties of these distances, including metricity, are also analyzed.