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.
|
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.
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).
|
This is actually quite innovative, but it still doesn't account for the physical thicknesses of raster points and lines.
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..."
"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.
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 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.
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:
|
|
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.
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