Accurate and efficient traveltime calculation is an important topic in seismic imaging. We present a fast-marching eikonal solver in the tetragonal coordinates (3-D) and trigonal coordinates (2-D), tetragonal (trigonal) fast-marching eikonal solver (TFMES), which can significantly reduce the first-order approximation error without greatly increasing the computational complexity. In the trigonal coordinates, there are six equally-spaced points surrounding one specific point and the number is twelve in the tetragonal coordinates, whereas the numbers of points are four and six respectively in the Cartesian coordinates. This means that the local traveltime updating space is more densely sampled in the tetragonal ( or trigonal) coordinates, which is the main reason that TFMES is more accurate than its counterpart in the Cartesian coordinates. Compared with the fast-marching eikonal solver in the polar coordinates, TFMES is more convenient since it needs only to transform the velocity model from the Cartesian to the tetragonal coordinates for one time. Potentially, TFMES can handle the complex velocity model better than the polar fast-marching solver. We also show that TFMES can be completely derived from Fermat's principle. This variational formulation implies that the fast-marching method can be extended for traveltime computation on other nonorthogonal or unstructured grids.