About rectangular coordinates and hexagonal grids

I think no one needs to explain how widely hexagonal grids are used in games (and not only). As for a given hexagonal cell, finding the coordinates of its center and vertices is fairly obvious. The inverse transformation (i.e., the search for the cell into which the given point with x and y coordinates fell) is no longer so trivial. About him and will be discussed in this topic.

Prologue

I have an old dream: to write an interesting game. I am going very slowly to the result and, perhaps, not quite right, but this is not the point here. In the next free time period, I wanted to work out some concept of a future game based on a hexagonal grid. Being in the country and without any sign of the Internet, I had to look for the transformation algorithm between the “hexagonal” and rectangular coordinates myself. Later I compared what turned out to well-known algorithms and was pleasantly surprised: the very first links in Google, for the query “pixel to hexagon,” gave descriptions of algorithms that were much more laborious and confusing than mine. The method equivalent to mine, I found here .

On this topic

Mesh description

To begin with, we will distinguish two ways to orient a hexagonal cell relative to rectangular coordinates:

The axes I called the letters "m", "l" and "r" from main, left and right. (Initially, this was all done on a piece of paper, where m coincided with the x axis, and the y axis looked up - therefore the “left” and “right” are rather arbitrary.) Thus, the m axis coincides with one of the rectangular axes; the axis l is rotated 60 degrees relative to this rectangular axis and 30 degrees relative to the second rectangular axis; The r-axis is 60 degrees with the first rectangular axis and 150 degrees with the second. The numbering of the cells goes along the axes m and l.

To implement the grid, I wrote a “field manager” - a class whose object stores information about the orientation and lattice period.
')

//      Qt- , , // ..      ,  //  typedef-. typedef QPointF MyPointF; typedef QPoint MyPointI; //    class FieldManager { public: //  ,     m. enum Orientation { OX, OY }; //   . FieldManager(double period = 1, Orientation orientation = OX); //       ( ). MyPointF CellCenter(int m, int l) const; //   ,     (x, y) ( ). MyPointI CellInd(double x, double y) const; private: //  . double m_period; //  . Orientation m_orientation; }; 

Direct conversion

 //    ,  //     . const double sin60 = sqrt(3.0) * 0.5; const double cos60 = 0.5; const double sin30 = cos60; const double cos30 = sin60; //  . FieldManager::FieldManager(double period, Orientation orientation) : m_period(period), m_orientation(orientation) { } //  .   . MyPointF FieldManager::CellCenter(int m, int l) const { double along_coord = m_period * (m + l * cos60); double other_coord = m_period * l * sin60; if (m_orientation == OX) return MyPointF(along_coord, other_coord); else return MyPointF(other_coord, along_coord); } 

Inverse transform

With the inverse transformation, I suffered for a long time. I really did not want to push bulky loops or conditional statements into the program. It was clear that the contour lines of the m, l and r axes (that is, the set of points with constant coordinate values ​​corresponding to these axes) divide the plane into many triangles (as a step along each axis I used half the period):

Thus, each triangle is assigned three numbers. It only remained to invent an operation that would group these triangles into six into one hexagon. It is also obvious that the transformation should be linear, since grid sizes do not change in space. As a result, the correct transformation was found by me:

 //  . MyPointI FieldManager::CellInd(double x, double y) const { //   . double along_coord = (m_orientation == OX) ? x : y; double other_coord = (m_orientation == OX) ? y : x; //     m, l  r (   ). //       , // , ,         //    int m = floor(2 * along_coord / m_period); int l = floor(2 * (cos60 * along_coord + sin60 * other_coord) / m_period); int r = floor(2 * (cos60 * along_coord - sin60 * other_coord) / m_period); // , ,   : return MyPointI( floor((m + r + 2) / 3.0), floor((l - r + 1) / 3.0)); } 

To find this transformation, I was helped by the following actions: I plotted a grid of these triangles on a piece of paper, then selected on it “lines” of hexagons with a constant (taking into account rounding) value m and looked at what unites the resulting triangles. Then did the same for the l axis. It was seen that for a strip of hexagons directed along the axis l, the axes m and r divide the space into diamonds that do not intersect this strip (that is, they lie entirely inside or outside of it). Moreover, for a fixed m, this band corresponds to three diamonds with different l and vice versa. Hence the rounding from dividing by 3. And similarly for another set of bands.

Conclusion

On this note, this narrative ends. I thank everyone who is not deprived of attention. I hope I could help someone.

PS
I also hope that the game will someday see the light and there will also be an article about it.