Keywords

1 Introduction

Digital geometry works on discrete space, i.e., points can have only integer coordinates. In digital geometry, two basic neighborhood relations are defined in the square grid [19]—cityblock and chessboard. The cityblock motion allows horizontal and vertical movements only, while at the chessboard motion the diagonal directions are also permitted. So, based on these motions, in this grid we have two kinds of distances. In [12, 18], there is a short summary of examination of the square grid. Each coordinate of a point in square grid is independent of the other. Generalizing the concepts to n dimensions, n independent coordinates are used. In the n dimensional cubic grid, the structure of the nodes is isomorphic to the structure of the n dimensional cubes. The field called ‘Geometry of Numbers’ works on these grids [1, 8, 9, 11]. The concept of ‘lattice’ and ‘array’ were used which have about the same meaning with ‘grid’, which we are using.

In digital geometry, hexagonal and triangular grids are also analyzed. There is a connection among the cubic, hexagonal and triangular grids [10, 13, 17, 20], and thus, coordinate systems with 3 coordinates are opt for these grids (see Fig. 1(left)). In this paper, the problem is formulated based on triangular grid, which has three neighborhoods. The three kinds of neighborhood criteria of the triangular grid can be found in [4], where thinning algorithms are shown in the three basic grids. The three coordinates used in triangular grid are not independent [14]. The digital distances of two points based on a neighborhood relation gives the length of a shortest path connecting the two points where in each step the path moves to next neighborhood point (given a neighborhood type). Weighted distance in triangular grid is discussed in [16], where three weights are used to define a distance function.

Shortest path is not unique in discrete space. Between two points there may exist more than one shortest path. The recursive formulation for the number of cityblock, chessboard, and octagonal shortest paths between two points in 2D digital plane was proposed in [3]. In [2], the number of minimal paths in a digital image between every pair of points with respect to a particular neighborhood relation is presented, where the image is considered as matrix and hence the algorithm contains matrix operations. Determination of shortest isothetic path (cityblock) between two points inside a digital object for a given grid size, is presented in [6, 7]. Since a shortest isothetic path is not unique, finding the number of shortest isothetic paths between two points is essential. The corresponding problem is presented in [5]. Here, in this paper, we will discuss the number of shortest paths in triangular grid for 1- and 2-neighborhoods.

2 Preliminaries

In this section, we will discuss some definitions, that are required to understand the paper. Three types of neighborhood are used in triangular grid [4] as shown in Fig. 1(left). Each pixel of the triangular grid is a triangle and it is termed as a point of the grid. There are two orientations of the used triangles: there are triangles of shape \(\bigtriangleup \) and there are triangles of shape \(\bigtriangledown \). There are three 1-neighbors, nine 2-neighbors (the 1-neighbors, and six more 2-neighbors), and twelve 3-neighbors (nine 2-neighbors, and three more 3-neighbors) w.r.t. each triangle. These relations are reflexive (i.e., the pixel marked with dark triangle is a 1-, 2-, and 3-neighbor of itself). In addition, all 1-neighbors of a pixel are its 2-neighbors and all 2-neighbors are 3-neighbors, as well (i.e., increasing and inclusion properties).

Three coordinate values are required to represent the triangles (and the term point is also used for the pixels). One point in triangular grid is selected as origin whose coordinate values are (0, 0, 0). The three lines passing through the center of the origin triangle, which are orthogonal to its sides, are considered as three coordinate axes x, y, and z (see Fig. 1(right)). The coordinate values of a triangle can be determined from another triangle by considering the movement which must be parallel to one of the axes. If the step is in the direction of an axis, then the respective coordinate value is increased by 1, while in case when the step is in the opposite direction to an axis, the respective coordinate value is decreased by 1. In this way, every triangle gets a unique coordinate triplet [15]. Since triangular grid is in 2-dimensional plane, the three coordinate values are dependent on each other. A point is termed as even (of shape \(\bigtriangleup \)) when the sum of the coordinate values is zero. When the corresponding sum is one, the point is termed as odd (of shape \(\bigtriangledown \)).

Fig. 1.
figure 1

Types of neighbors in triangular grid (left). The coordinate values and lanes in triangular grid (right).

Full size image

The two grid points p and q of the triangular grid are m-neighbours (\(m = 1, 2, 3\)), if the following two conditions hold:

  1. 1.

    \(|p(i)-q(i)| \leqslant 1\) for \(i=1,2,3\), and

  2. 2.

    \(|p(1)-q(1)| + |p(2)-q(2)| + |p(3)-q(3)| \leqslant m\).

When for some value of m, the second condition holds equality, it is termed as strict m-neighbors.

The points having the same value as x, y, or z-coordinate, form a lane. Each lane is orthogonal to one of the coordinate axes. For the points of a lane a coordinate value is fixed. The other two values change by \(+ 1\)/\(-1\) moving to neighbor points on the lane. If two points share a coordinate value, then they are in a common lane (according to this shared coordinate value). If there is no coordinate value that is shared by the two points, then the points can be connected by two lanes having angle \(\frac{2}{3}\pi \) between them.

For technical purpose we name the sextants of the grid by terms direct and indirect sextants: a point (i, j, k) is in a direct sextant of the grid, if it has exactly 1 positive coordinate value and 2 negative coordinate values. A point is in an indirect sextant if it has two positive coordinate values (the third one is a negative value, necessarily, in this case). In this case, the grid consists of the three lanes through the origin and six pairwise disjoint sextants. Each sextant is bordered by two lanes (actually, only half parts of the lanes contain neighbor points of some of the points of the sextant).

It may happen that q is not origin. If q is an even point, let us say, (x, y, z) with \(x+y+z=0\), then a translation by vector \((-x,-y,-z)\) translates the grid in such a way, that every point (i, j, k) is mapped to \((i-x,j-y,k-z)\) [15]. It is also possible that q is an odd triangle. Any odd point \(q^\prime \) with coordinates (x, y, z) (\(x+y+z=1\)) can be transformed to the origin by mirroring [15], and the point \(p^\prime \) with coordinates (i, j, k) is transformed to p by the same transformation, e.g., assigning for any point (i, j, k) the point \((x-i,y-j,z-k)\). This transformation is also isometric, it keeps the structure of the grid. Thus further, it is enough to consider the number of shortest paths from the origin, i.e., we assume that q has coordinate triplet (0, 0, 0).

3 Formulation for Number of Shortest Paths

The number of shortest paths between two points (say, p and q) in triangular grid depends on the neighborhood used on the path. Let q be the origin having coordinate triplet (0, 0, 0) and p be any other point in the grid having coordinate triplet (i, j, k). Three lanes passes through q as shown in Fig. 1(right). Let \(f_r(i,j,k)\) be the number of shortest paths from q to p in r-neighborhood It may happen that we need the number of shortest paths where one of the points (between p and q) is not the origin. In this scenario, we can translate the origin to q and calculate the number of shortest paths.

From the symmetry of triangular grid, it can be said that \(f_r(i,j,k) = f_r(i,k,j) = f_r(j,i,k) = f_r(j,k,i) = f_r(k,j,i) = f_r(k,i,j)\). It is to be noted that in each sextant two values of the coordinate triplets have similar sign—either positive or negative, whereas the other one has opposite sign, which is called the prime coordinate. The other two, having the same sign, are called secondary coordinates. Consider the top-most sextant in Fig. 1(right), where \(i\geqslant 0\) and \(k\geqslant 0\) but \(j\leqslant 0\). Thus, j is the prime coordinate and i and k are secondary coordinates. A sextant can also be named by its prime coordinate, therefore the mentioned sextant is called j-indirect sextant. The value of the prime coordinate can never be less than (by the absolute values of the coordinates) any of the secondary coordinates. To determine the number of shortest paths in 1-neighborhood, we need only secondary coordinates, as we will see.

The formulations for the number of shortest paths in 1-neighborhood and 2-neighborhood are discussed in the following sections (Sects. 3.1, 3.2).

3.1 Number of Shortest Paths Based on 1-Neighborhood

Let \(f_1(i,j,k)\) be the number of shortest paths from (i, j, k) to (0, 0, 0) considering 1-neighborhood in triangular grid. The number of shortest paths from p to q can be defined as follows.

$$\begin{aligned} f_1(i,j,k) = \left( {\begin{array}{c}|a|+|b|\\ |a|\end{array}}\right) ,\left. \begin{array}{ll} &{} \text{ where } a,b\geqslant 0 \text{ or } a,b\leqslant 0\text{, } \\ &{} a \in \{i,j,k\} \text{ and } b \in \{i,j,k\} \setminus \{a\} \end{array} \right. \end{aligned}$$
(1)
Fig. 2.
figure 2

Number of shortest paths (shown inside circles) in 1-neighborhood.

Full size image

The number of shortest paths in 1-neighborhood for different coordinate triplets are shown in Fig. 2. It is to be noted that if p lies in any of the three lanes which intersect at q, then there will be only one shortest path between p and q in 1-neighborhood (see Fig. 2).

3.2 Number of Shortest Paths Based on 2-Neighborhood

Let \(f_2(i,j,k)\) be the number of shortest paths between two points p and q in 2-neighborhood. The calculation of number of shortest paths in 2-neighborhood is dependent on the same in 1-neighborhood. Then, \(f_2(i,j,k)\) can be defined as follows.

$$\begin{aligned} f_2(i,j,k) = f_1(i,j,k) \times \alpha ,\left. \begin{array}{ll} &{} \alpha = 1\text{, } \text{ when } i+j+k= 0\text{; } \\ &{} \alpha =\max (|i|,|j|,|k|)\text{, } \text{ when } i\times j\times k \geqslant 0\text{; } \\ &{} \alpha =\max (|i|,|j|,|k|)+1\text{, } \text{ when } i\times j\times k < 0\text{. } \\ \end{array} \right. \end{aligned}$$
(2)
Fig. 3.
figure 3

Number of shortest paths in 2-neighborhood.

Full size image

that is, the \(f_2(i,j,k)\) remains same as \(f_1(i,j,k)\) for even points and it is multiplied by the largest absolute value of the coordinates for odd points of the lanes containing the origin and for odd points of the direct sextants, and the sum of the absolute values of the secondary coordinates is used as coefficients for odd points of the indirect sextants (see also Fig. 3).

4 Proof of Correctness

Proof for 1-neighborhood: For 1-neighborhood, the proof goes by induction for the even and also for the odd points for both, points of the lanes and points of the (direct and indirect) sextants. Let us start by the lanes. It is clear that a shortest path from the origin q to any point having coordinates (i, j, 0) or (0, j, k) with \(j>0\) consists of \(|i|+j\) or \(j+|k|\) steps, respectively. Moreover, there is only one shortest path in these cases, stepping one by one, neighbor to neighbor on the given lane. Applying Eq. 1 for these cases we got \(\left( {\begin{array}{c}|i|\\ 0\end{array}}\right) =1\) (or \(\left( {\begin{array}{c}|i|\\ |i|\end{array}}\right) \), or \(\left( {\begin{array}{c}j\\ 0\end{array}}\right) \), or equivalently, \(\left( {\begin{array}{c}j\\ j\end{array}}\right) =1\)) and \(\left( {\begin{array}{c}|k|\\ 0\end{array}}\right) =1\) (or \(\left( {\begin{array}{c}|k|\\ |k|\end{array}}\right) \), or \(\left( {\begin{array}{c}j\\ 0\end{array}}\right) \), or equivalently, \(\left( {\begin{array}{c}j\\ j\end{array}}\right) =1\)), respectively. Thus, by symmetry, the formula is proven for the points of all the lanes containing the origin.

Now, let us consider the direct sextants, we show the proof for the j-direct sextant, but by symmetry it holds for the other direct sextants as well. We use an induction based on the sum of absolute values of the secondary coordinates w.r.t. a sextant. Now, let us consider an even point (i, j, k) such that it is inside the j-direct sextant, i.e., \(j>0\) and \(i,k<0\). Then in a shortest path from q one may arrive to the point (i, j, k) from \((i,j,k+1)\) or from \((i+1,j,k)\). There are no other possibilities. Therefore, \(f_1(i,j,k) = f_1(i,j,k+1) + f_1(i+1,j,k)=\left( {\begin{array}{c}|i|+|k|-1\\ |i|\end{array}}\right) +\left( {\begin{array}{c}|i|+|k|-1\\ |i|-1\end{array}}\right) =\left( {\begin{array}{c}|i|+|k|\\ |i|\end{array}}\right) \). Notice that both points \((i,j,k+1)\), \((i+1,j,k)\) are odd.

Now, let us consider an odd point such that \(j>0\) and \(i,k<0\). Then, in a shortest path from q, the last step must be from the even point \((i,j-1,k)\) to the point (i, j, k), and thus, \(f_1(i,j,k)=f_1(i,j-1,k)\).

Observe, that by using the already proven values for the lanes having a coordinate value 0, actually, the binomial coefficients and the Pascal’s triangle are obtained, in a way that every value is repeated from an even point to an odd point right below.

Now, let us consider odd points in the j-indirect sextant where \(j<0\) and \(i,k>0\). The proof for the points of the lanes bordering the j-indirect sextant is already given. Now, let us consider the odd points of this sextant. In a shortest path from q one may arrive to the point (i, j, k) (\(i+j+k=1\)) from \((i,j,k-1)\) or from \((i-1,j,k)\). There are no other possibilities. Therefore \(f_1(i,j,k) = f_1(i,j,k-1) + f_1(i-1,j,k)\). Notice that both points \((i,j,k-1)\), \((i-1,j,k)\) are even. If we consider even points in the j-indirect sextant, then in a shortest path from q, the last step must go from the odd point \((i,j-1,k)\) to the point (i, j, k), and thus, \(f_1(i,j,k)=f_1(i,j-1,k)\). The proof is also inductive here and the binomial coefficients are obtained in a quite similar manner as at the j-direct sextant.

Proof for 2-neighborhood: Similarly, we will prove for 2-neighborhood first for even and odd points on the lanes containing the origin, and then for points in the j-direct and j-indirect sextants. By symmetry, proof for other sextants is immediately follows.

By using 2-neighborhood, in a shortest path from q to an even point only steps changing two of the coordinate values are used (they are the so-called strict 2-steps). From q to an odd point exactly one 1-step is used, all the other steps in a shortest path are strict 2-steps (see, e.g., [14]).

Let us start by the even points in lanes. It is clear that a shortest path from the origin q to any point having coordinates \((i,j,0)=(-j,j,0)\) or \((0,j,k)=(0,j,-j)\) with \(j>0\) consists of exactly j steps, respectively. Moreover, there is only one shortest path in these cases, stepping one by one, strict 2-neighbor to strict 2-neighbor on the given lane. Applying Eq. 2 for these cases we got \(\left( {\begin{array}{c}|i|\\ 0\end{array}}\right) =1\) and \(\left( {\begin{array}{c}|k|\\ 0\end{array}}\right) =1\), respectively, i.e. the same value as for 1-neighborhood.

Now consider an odd point in lanes containing the origin. Let it have the coordinates (i, j, 0) or (0, j, k) with \(j>0\), i.e., it is \((1-j,j,0)\) or \((0,j,1-j)\). In a shortest path from the origin to the point \((1-j,j,0)\) the last step could be either from \((1-j,j-1,0)\) or from \((2-j,j-1,0)\). Similarly, to \((0,j,1-j)\) one can arrive from the points \((0,j-1,1-j)\) or \((0,j-1,2-j)\) in a shortest path, there is no other choice. Thus, the number of shortest paths from q to these odd points can be written as, \(f_2(0,j,k)=f_2(0,j-1,k)+f_2(0,j-1,k+1)\) or \(f_2(i,j,0)=f_2(i,j-1,0)+f_2(i+1,j-1,0)\), respectively. Here, the first terms are belonging to shortest paths for an even point and the second terms are belonging to the shortest paths for an odd point which will expand in similarly. By induction using Eq. 2, \(f_2(0,j,k)=f_1(0,j-1,k)+f_1(0,j-1,k+1)\times (j-1)\) and \(f_2(i,j,0)=f_1(i,j-1,0)+f_1(i-1,j-1,0)\times (j-1)\), respectively. Thus, \(f_2(0,j,k)=\left( {\begin{array}{c}0+|k|\\ |k|\end{array}}\right) +\left( {\begin{array}{c}0+|k|-1\\ |k|-1\end{array}}\right) \times (j-1)\) or \(f_2(i,j,0)=\left( {\begin{array}{c}|i|-1+0\\ |i|-1\end{array}}\right) +\left( {\begin{array}{c}|i|-1+0\\ |i|-1\end{array}}\right) \times (j-1)\), i.e., \(f_2(0,j,k)=1+1\times (j-1)\) or \(f_2(i,j,0)=1+1\times (j-1)\). Hence, \(f_2(0,j,k)=j\) and \(f_2(i,j,0)=j\). Thus, by symmetry, the formula is proven for the points of the lanes containing the origin.

Let us consider the shortest paths from q to an even point (i, j, k) in j-direct sextant (\(j>0\)). Since only strict 2-steps, i.e., even points are used in these shortest paths, there are exactly to points that can precede (i, j, k) in a shortest path: they are \((i,j-1,k+1)\) and \((i+1,j-1,k)\). Thus, the number of shortest paths can be written as \(f_2(i,j,k)=f_2(i,j-1,k+1)+f_2(i+1,j-1,k)\). The two terms represent the formula for two even points. Thus, \(f_2(i,j,k)=f_1(i,j-1,k+1)+f_1(i+1,j-1,k)\), i.e., \(f_2(i,j,k)=\left( {\begin{array}{c}|i|+|k|-1\\ |i|\end{array}}\right) +\left( {\begin{array}{c}|i|-1+|k|\\ |i|-1\end{array}}\right) =\left( {\begin{array}{c}|i|+|k|\\ |i|\end{array}}\right) =f_1(i,j,k)\).

In a shortest path from q one may arrive to the odd point (i, j, k) from \( (i, j -1, k+1)\) or \((i, j -1, k)\) or \((i+1, j -1, k)\), when (i, j, k) is an odd point in j-direct sextant. Subsequently, \(f_2(i,j,k)=f_2(i,j-1,k+1)+f_2(i+1,j-1,k)+f_2(i,j-1,k)\). The first two terms referring values for odd points and the third term does for an even point. Using Eq. 2, \(f_2(i,j,k)=f_1(i,j-1,k+1)\times (j-1)+f_1(i+1,j-1,k)\times (j-1)+f_1(i,j-1,k)\). Therefore, \(f_2(i,j,k)=(j-1)\times \left( \left( {\begin{array}{c}|i|+|k|-1\\ |i|\end{array}}\right) +\left( {\begin{array}{c}|i|-1+|k|\\ |i|-1\end{array}}\right) \right) +f_1(i,j-1,k)=(j-1)\times \left( {\begin{array}{c}|i|+|k|\\ |i|\end{array}}\right) + \left( {\begin{array}{c}|i|+|k|\\ |i|\end{array}}\right) =j\times \left( {\begin{array}{c}|i|+|k|\\ |i|\end{array}}\right) =j\times f_1(i,j,k)\). This is the formula that we wanted to proof in this case.

Let us consider a shortest path from q to an even point (i, j, k) in j-indirect sextant (\(j<0\)). Their number can be written as \(f_2(i,j,k)=f_2(i-1,j+1,k)+f_2(i,j+1,k-1)\) since one reach point (i, j, k) only from points \((i-1,j+1,k)\) and \((i,j+1,k-1)\) in a shortest path from the origin. The two terms represent values corresponding to two even points. Thus, \(f_2(i,j,k)=f_1(i-1,j+1,k)+f_1(i,j+1,k-1)\), i.e., \(f_2(i,j,k)=\left( {\begin{array}{c}i-1+k\\ i-1\end{array}}\right) +\left( {\begin{array}{c}i+k-1\\ k\end{array}}\right) =\left( {\begin{array}{c}i+k\\ i\end{array}}\right) =f_1(i,j,k)\).

Let us consider the last case. When (i, j, k) is an odd point in j-indirect sextant, then, in a shortest path, one may reach (i, j, k) from exactly one of the following points: \((i-1,j,k)\), \((i,j,k-1)\), \((i-1,j+1,k)\) and \((i,j+1,k-1)\). Consequently, \(f_2(i,j,k)=f_2(i-1,j,k)+f_2(i,j,k-1)+f_2(i-1,j+1,k)+f_2(i,j+1,k-1)\). The first two terms are values for even points and the last two terms are vales for odd points. Using Eq. 2, \(f_2(i,j,k)=f_1(i-1,j,k)+f_1(i,j,k-1)+f_1(i-1,j+1,k)\times (i-1+k)+f_1(i,j+1,k-1)\times (i+k-1)\). Therefore, \(f_2(i,j,k)=\left( {\begin{array}{c}i-1+k\\ i-1\end{array}}\right) +\left( {\begin{array}{c}i+k-1\\ i\end{array}}\right) +\left( {\begin{array}{c}i-1+k\\ i-1\end{array}}\right) \times (i-1+k)+\left( {\begin{array}{c}i+k-1\\ i\end{array}}\right) \times (i+k-1)\). Thus, \(f_2(i,j,k)=\left( {\begin{array}{c}i+k\\ i\end{array}}\right) +(i+k-1)\times \left( \left( {\begin{array}{c}i-1+k\\ i-1\end{array}}\right) +\left( {\begin{array}{c}i+k-1\\ i\end{array}}\right) \right) =\left( {\begin{array}{c}i+k\\ i\end{array}}\right) +(i+k-1)\times \left( {\begin{array}{c}i+k\\ i\end{array}}\right) =\left( {\begin{array}{c}i+k\\ i\end{array}}\right) \times (i+k-1+1)=f_1(i,j,k)\times (i+k)\). For odd points in j-indirect sextant, \(i+j+k=1\) and \(|j|+1=i+k\), since \(j<0\). Hence, \(f_2(i,j,k)=f_1(i,j,k)\times (|j|+1)\).

The proof for other sextants, i.e., i-direct sextant, i-indirect sextant, k-direct sextant, and k-indirect sextant, can be done similarly.

5 Conclusions

Digital distances have various application in several research areas, specially in image processing. Many studies have already been proposed on it. The usage of non-traditional grids can have several advantages based on their better symmetric properties (e.g., they have more symmetry axes) than the traditional (square, cubic) grids. The three types of basic neighborhood relations give more flexibility in triangular grid compared to square and hexagonal grid. The number of shortest paths based on 1- and 2-neighborhoods in triangular grid is presented in this paper. Theoretical background, such as the formulation of the problem and proof of correctness are elaborated. In future, we can extend the problem by finding number of shortest paths based on 3-neighborhood.