In this paper, we extend the fast-marching eikonal solver from the Cartesian to the tetragonal coordinates. Compared with the Cartesian implementation, the tetragonal (trigonal) fast-marching eikonal solver (TFMES) can reduce the first-order approximation error. It is also more efficient than the polar implementation. Since the fast-marching eikonal solver is based on the plane wave assumption, we can derive the same algorithm using variational principle. It is possible to extend the algorithm to unstructured grids (triangle in 2-D; tetrahedron in 3-D model).