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?