BDS Software

Hex vs. Square - Page 11



Which Hex Has Been Clicked (Various Methods)


Amit Patel

Amit begins his treatment of this subject by saying:

One of the most common questions is, how do I take a pixel location (such as a mouse click) and convert it into a hex grid coordinate? I'll show how to do this for axial or cube coordinates. For offset coordinates, the simplest thing to do is to convert the cube to offset at the end.

What Amit terms "offset coordinates" is the system of hex numbers I'm using here, cf. Worlographer.

First he sets up a conversion matrix to convert hex coordinates to pixel coordinates, and then he inverts that matrix to give pixel-to-hex conversion.

Patel 01

Patel 02


function pixel_to_flat_hex(point):
      var q = ( 2./3 * point.x ) / size
      var r = (-1./3 * point.x + sqrt(3)/3 * point.y) / size
      return axial_round(Hex(q, r))


function axial_round(hex):
      return cube_to_axial(cube_round(axial_to_cube(hex)))

Amit continues, "Sometimes we'll end up with a floating-point cube coordinate, and we'll want to know which hex it should be in.... Converting a floating point value to an integer value is called rounding so I call this algorithm cube_round":

function cube_round(frac):
      var q = round(frac.q)
      var r = round(frac.r)
      var s = round(frac.s)

      var q_diff = abs(q - frac.q)
      var r_diff = abs(r - frac.r)
      var s_diff = abs(s - frac.s)

      if q_diff > r_diff and q_diff > s_diff:
            q = -r-s
      else if r_diff > s_diff:
            r = -q-s
      else:
            s = -q-r

      return Cube(q, r, s)

This math is indeed intriguing, but it still doesn't account for the physical thicknesses of raster points and lines.


-----

Greg Kuperberg

In addition to his own work, Amit Patel has also archived for us previous methodology which, as far as I can tell, is not currently available from anywhere else.

From Greg Kuperberg's December 3, 1992 article 8616 on the usenet group rec.games.programmer, we find a method based on brick layer's patterned rectangles (I'm not covering any of these ideas in detail; only in brief - please go directly to the sources if you wish to dig deeper).

Kuperberg 01

"...we can divide the region into... rectangles in a sideways brick-layer's pattern so that the rectangles are almost in the same place as the hexagons..."


"The idea is to assume first that if the mouse landed in rectangle ij then it landed in hexagon ij and then correct if the mouse position is in one of the two triangular flaps. I'll compute two numbers tx and ty which index the hexagon that the user clicked in. All my arithmetic is in integers and I assume that division is never rounded up, and, compatibly, remainders are always non-negative. I also assume h, the height of a hexagon, is even."

This is actually quite innovative, but it still doesn't account for the physical thicknesses of raster points and lines.


-----

Paul Gyugyi

In Amit's archive, we also find the December 10, 1992 article 8688 from Paul Gyugyi, on the same usenet group, in which we find a method based on doing some hit-testing after dividing the hexagons into triangles.

Gyugyi begins, "I create three new axis (sic), centered on the (x,y) origin. The H-axis runs vertically (the same as the y axis). The E-axis is a line sloping upwards at +30 deg. The X-axis (sorry about the use of the same letter) runs downwards at -30 deg. Given an (x,y) point, I project the vector from the origin to the point onto each axis and record the length of the projection. I then take that length, double it (to make the math easier), and truncate towards negative infinity..."


Gyugyi 01

"So once I've converted from (x,y) to (H,E,X) it is just a matter of calculating which hex a given (H,E,X) triangle is in."

About 3 to 4 pages of math follows and, at the end, the physical thicknesses of raster points and lines again remain unaccounted for.


-----

Cosmin

In a March 4, 2011 StackOverflow response, Cosmin outlines what appears to be a rather elegant purely mathematical solution:

You can use the equations for each of the sides of the hexagon; with them you can find out if a given point is in the same half-plane as the center of the hexagon.

For example, the top-right side has the equation:

-sqrt(3)x - y + sqrt(3)/2 = 0

You plug in this the coordinates of the point and then the coordinates of the center. If the results have the same sign, then the point is in the bottom-left half-plane (so it may be inside the hexagon).

You then repeat by using the equations of the others sides.

But this ultimately involves running a line equation twelve times per hexagon (kinda expensive timewise, especially if you need to check 483 separate hexagons to see which one the point falls inside, and (Nope) no accounting for line or point thickness.


-----

Wikipedia and Rosetta Code

Wikipedia outlines a couple more purely mathematical approaches: The Ray Casting Algorithm and The Winding Number Algorithm.

Rosetta Code expands upon Wikipedia's Ray Casting Algorithm in greater detail.

For a formsl development, see Sedgewick (315-318).

Both of these algorithms suffer from the same deficiency as Cosmin's solution - they're intended for checking a single polygon and would become prohibitively exzpensive when having to check 483 hexagons with every click of the mouse. They also don't account for real-world point and line thicknesses.


-----

dlras2

I checked out several other proposed solutions, all of which also failed to account for real-world point and line thicknesses. Clark Verbrugge's site provides a wealth of related links if you're up to wading through that extensive list.

But dlras2's July 22, 2011 response in Game Development is interesting:


dlras2 01

A hexagon is a rectangle with clipped corners. The way I've seen this done, and I've heard the Civilization series does it this way with orthogonal maps, is to create a bitmap with a white space (orthogonal or hexagonal), and a red, green, blue, and yellow corner. (Or whatever colors you like.)

Then, just determine which rectangle the cursor is over, and test the color of the pixel at that location. If it's white, they're hovering over that space. Each other color is mapped to an offset, and they're hovering over that hexagon instead. This way is efficient, takes little geometry, and can be used for any arbitrarily tessellating space.

This suffers from the fact that you have to determine the enclosing rectangle before you even start checking the hex, and it also doesn't account for point and line thicknesses.

But the "colors" concept did offer a germ of an idea which I built upon in my own solution, which starts on the Next Page.


----------

References:

Cosmin. In "Is a point inside regular hexagon". StackOverflow. https://stackoverflow.com/questions/5193331/is-a-point-inside-regular-hexagon.

dlras2. In "Recognizing a hexagonal clickbox". On Game Development. https://gamedev.stackexchange.com/questions/15110/recognizing-a-hexagonal-clickbox.

Patel, Amit. His archive: "Hexagonal Coordinates, Distances, and Angles". http://www-cs-students.stanford.edu/~amitp/Articles/Hexagon1.html.

Patel, Amit. "Pixel to Hex". https://www.redblobgames.com/grids/hexagons/#pixel-to-hex.

Rosetta Code. "Ray-casting algorithm". https://rosettacode.org/wiki/Ray-casting_algorithm.

Sedgewick, Robert. 1983. Algorithms. Addison-Wesley.

Verbrugge, Clark. "Research in Modern Computer Games". http://www.sable.mcgill.ca/~clump/games.html.

Wikipedia. "Point in polygon". https://en.wikipedia.org/wiki/Point_in_polygon.

Worldographer. "RPG Map Software". https://worldographer.com/.




                                                                                                                                                                M.D.J. 2022/08/27