How to check if a point is inside a hexagon
Hexagons have always fascinated me, they appear everywhere, in architecture, computer games and more curiously; this rather symmetrical structure emerge in a lot of places naturally.
Snow crystal:
Bee hive:
Civilization V:
Google on hexagon and you shall be surprised of all its appearances.
Anyway, I’ve never familiarized myself closer to those mystical shapes other than admiring them from a distance. Until today – when I decided to write a little class that represents a hexagon.
Hexagon
In short – a hexagon has six sides and a the total sum of internal angels is 720. For more throughout description see wikipedia.
When I came about to implement the isInside(point) method of my Hexagon class I started by searching the net for algorithms to perform this test. I found a few, most involved a general “point inside polygon” algorithm where the hexagon is considered as a general polygon. Those tests works for all kind of shapes and involves ray casting through the shape and counting hits. Another approach I found required one dot product per edge. Perhaps I am really bad to search, but I could not find any satisfactory answer to the question: “What is the best way to find if a point is inside a hexagon?”. So I thought I would give it a shot.
Here is my representation:
To create a hexagon I specify v, then h=2*v*cos(30).
Basic Approach
The intuitive way to check if a point is inside a hexagon is to first check if a point is outside the hexagons bounding box – if so we can safely regard it to be outside. After this, we are left with four corner cases (literary) that we need to check, if the point resides on the inside of those corners the point is indeed within the hexagon.
1) Check against the bounding box
2) Check against the 4 corners
Symmetry ftw…wtf
Now, since hexagons are highly symmetrical, we can use it to reduce the number of tests required by simply transforming the point to test into one of the hexagons 4 quadrants (corners). The simplest transform I can think of is to move it into quadrant 2, the lower right one. In this space all components (relative to the hexagon position) are positive – so the transformation is really simple and inexpensive – we just take the absolute value on the point to test (after transforming it into the hexagon space of course).
1) Transform point to test into hexagon space (local point)
2) Transform local point into quadrant 2 (q2)
3) Check against the bounding box
4) Test against quadrant 2’s corner
1-3 is straightforward, but what way is easiest to check if the point is inside our outside the hexagon corner in q2?
Checking against the corner
In quadrant 2, the corner line from p2 to p3 sets up a vector p3-p2, if we rotate this vector 90 degrees inwards, towards the center of the hexagon we have a normal to the edge between p2 and p3. This normal, n, is simply <-v,-h> (see the picture, I downscaled it a bit in the image so it would not be all over, but the direction remains the same)
Now we create another vector from p2 to q2=m. (q2 is the point to test that has been transformed into quadrant 2).
Now we can just check if the two vectors are pointing in the same direction – if so the point is inside of the hexagon (remember n is pointing inwards the hexagon). This test is easily performed with the dot product between n and m.
So,
n = <-v, -h>
m = q2-p2
dot product d = n dot m = -v*(q2.x-p2.x) – h*(q2.y-p2.y)
Now, if we look at the components of p2, we find <v, h>, lets insert that and see what we get:
d = -v*(q2.x-h)-h*(q2.y-v) = -v*q2x + v*h – h*q2.y + v*h = 2*v*h – v*q2.x -h*q2.y
There we have the dot product, d, and if this is greater or equal to 0 the point is inside the hexagon (n and m are not pointing away from each other).
Here is the code to accomplish this test:
public function isInside(pos:Vec2Const):Boolean
{
const q2x:Number = Math.abs(pos.x - _center.x); // transform the test point locally and to quadrant 2
const q2y:Number = Math.abs(pos.y - _center.y); // transform the test point locally and to quadrant 2
if (q2x > _hori || q2y > _vert*2) return false; // bounding test (since q2 is in quadrant 2 only 2 tests are needed)
return 2 * _vert * _hori - _vert * q2x - _hori * q2y >= 0; // finally the dot product can be reduced to this due to the hexagon symmetry
}
This is the best I could do, of course this is only a reinvention and has been done thousands of times before. My hope is that this will be helpful for those that don’t have the time to reinvent it.
Any suggestions on improvements?
Thanks! Good explanation and fast formula. Just what I was looking for now!
I’m having an area complete cowered with hexagon tiles, and my next step is may be to figure out a way to just convert a coordinate to a matching numbered hexagon tile, without checking every hex.
This help me a lot.
I have to modify the function because my hexagons are rotated 90º, the result works great:
public function isInside(_x:Number, _y:Number):Boolean
{
const q2x:Number = Math.abs(_x – _center.x);
const q2y:Number = Math.abs(_y – _center.y);
if (q2x > _hori*2 || q2y > _vert) return false;
return _vert * 2* _hori – _vert * q2x – 2* _hori * q2y >= 0;
}
Great!
Nice trick. Defining the local origin to maximize symmetry is used in point in ellipse testing as well, but the result isn’t as clean (best I’ve been able to get is an iterative approach that has to wait for reasonable convergence). This is probably the least expensive point in hexagon test I’ve seen.
I’ve a large hex grid that I test for ray intersection, grabbing (x,y) at an approximated intersection plane, getting a ringed region about the most likely hex, and running point in hexagon on those. It’s fairly fast. Makes intersection independent of map size at least.
Thanks, I am happy you like it!!
Thanks for this tip – it is still unclear to me as to whether isInside needs to be called once, or once for every corner / triangle. I am not sure I am quite getting how the former would be possible – how can the one function account for all corners?
You call this once, it will test for all cases by transforming the test point to one of the quadrant.
Do you know off the top of your head how to calculate v & h? I’m drawing my hexagons off of a radius, and my implementation of your isInside function is giving me pretty poor hit checks.
It is my assumption that:
hex.getHeight() returns hexagon.radius * sqrt(3);
v = hexagon.getHeight() / 4;
v * 2 = hexagon.getHeight() / 2;
hex.getWidth() returns radius; // radius = width
h = hexagon.width() / 2
I could have fundamentals of hexagon geometry wrong here, but I don’t think so as all my other math is spot on (in terms of loading on to the grid in proper position).
However, with the following c++ code, the hittest area is really tight to the center of the hex, and the corners certainly are not trigger spots – I’m having two hexes at the same time, or no hexes at all, highlighted. If you have time to take a look that would be great!
////////////////
bool HexagonShape::isInside(sf::Vector2f point){
// transform the test point locally and to quadrant 2
float q2x = abs(point.x – center.x);
float q2y = abs(point.y – center.y);
// bounding test (since q2 is in quadrant 2 only 2 tests are needed)
if (q2x > (getWidth() / 2) || q2y > (getHeight() /2 )){
return false;
}
// finally the dot product can be reduced to this due to the hexagon symmetry
return 2 * (getHeight() / 4) * (getWidth() / 2) – (getHeight() / 4) * q2x – (getWidth() / 2) * q2y >= 0;
}
Thanks!
Hey, thx for the awesome method, makes my code a bit smaller 🙂
But do you know anything for this…
If I set the origin to the mid of the hexagon…
And I then have and angle (which is obtained by a point in or out the hexagon) from the origin to the point
Do you know how to get the point where a line under that angle intersects with the hexagon?
Hello,
Nice article. I came up with an alternative implementation that works for any orientation. Basically:
– The hexagon is defined by two points in space, center(cx, cy) and one vertex(vx, vy). Knowing these two points allows reconstructing the whole hexagon.
– To check whether an arbitrary point (x,y) falls inside the hexagon, I do the following:
Notation. denote vertex vector by V, point (x,y) vector by P
1. Calculate distance to the center, i.e. length of P (pretty straight forward).
2. Calculate angle between P and closest vertex. In fact, this’s simpler than what it seems because you simply calculate angle between P and V (dot product formula) then take the modulus with 60 degrees. Let’s call this angle alpha.
3. P (or its extension) intersects the hexagon side at some point (sx,sy). Calculate the distance between (sx,sy) and the center. This is done using sine law (hence need for alpha). If this distance is less than P then point (x,y) falls outside the hexagon.
I don’t know if this’s the most efficient way… just needed a quick matlab implementation and it seems to work.