Is a point inside regular hexagon

Question

I'm looking for advice on the best way to proceed. I'm trying to find whether a given point A:(a, b) is inside a regular hexagon, defined with center O:(x, y) and diameter of circumscribing circle.

It seems like overkill to use Ray-casting, or Winding-number to determine this, for such a simple case, and I'm currently looking at the option of finding the angle (from horizontal) of the line OA, and "normalising" (probably not the right word) it into one of the 6 equilateral triangles and seeing if this new point lies within this triangle.

I get the feeling I'm missing something simple, and there's an easy way (or if I'm really lucky, a Java API) to do this simply and efficiently.

Thanks for your help.

Edit: The hexagon is oriented such that one of the sides is flat with the horizontal.

Answer 1

Alright, it is 2024 and this question is still seriously lacking a simple yet complete code with a proper explanation. This is TypeScript, but works the same in any language.

function isPointInsideHexagon(px: number, py: number, cx: number, cy: number, radius: number) {
    let sqrt3 = Math.sqrt(3);

    let dx = (px - cx) / radius;
    let dy = (py - cy) / radius;

    return dy > -sqrt3 / 2
        && dy < sqrt3 / 2
        && sqrt3 * dx + sqrt3 > dy
        && sqrt3 * dx - sqrt3 < dy
        && -sqrt3 * dx + sqrt3 > dy
        && -sqrt3 * dx - sqrt3 < dy
}

• (px, py) are the coordinates of the point to check
• (cx, cy) are the coordinates of the center of the hexagon
• radius is the distance from the center to any vertex of the hexagon

Explanation

Here we assume that the Y axis goes up: point (1,1) is top-right of point (0,0). However since it's a regular hexagon, the code works regardless of axis orientation.

We basically want to check, for each side of the hexagon, if both the point to check and the center of the hexagon are on the same side.

First, we convert the point coordinates for convenience:

let dx = (px - cx) / radius;
let dy = (py - cy) / radius;

From now on, (dx, dy) is the point to check, (0,0) is the center of the hexagon, and the radius of the hexagon is 1. This makes followup equations simpler.

Top and bottom sides

These are the simplest to check because they are horizontal lines. The Y coordinate of the top side is sqrt(3) / 2, and the Y coordinate of the bottom side is the opposite, -sqrt(3) / 2.

So we check with dy < sqrt3 / 2 and dy > -sqrt3 / 2 that the point is between these two lines.

Diagonal sides

There are 4 diagonal sides, for which the equations are (for an hexagon of center (0,0) and radius 1):

• top-left: y = sqrt(3) * x + sqrt(3)
• top-right: y = -sqrt(3) * x + sqrt(3)
• bottom-right: y = sqrt(3) * x - sqrt(3)
• bottom-left: y = -sqrt(3) * x - sqrt(3)

To know if two points are on the same side of a line, we plug their coordinates in the line equation and we check which side of the equation is greater that the other. If the same side is greater for both points, it means they are on the same side.

Let's have an example with the top-left side. We want to check if the point (0.5, 0.5) is on the same side as the center. So we plug the coordinates:

• For the point to check (0.5, 0.5):
  • Left side : y = 0.5
  • Right side : -sqrt(3) * x + sqrt(3) = -sqrt(3) * 0.5 + sqrt(3) ≈ 0.866
  • -> Right side is greater
• For the center of the hexagon (0, 0):
  • Left side : y = 0
  • Right side : -sqrt(3) * x + sqrt(3) = -sqrt(3) * 0 + sqrt(3) ≈ 1.732
  • -> Right side is greater

In both cases, the right side is greater than the left side thus we can conclude that both points (0, 0) and (0.5, 0.5) are on the same side of the top-right side of the hexagon.

If we try with the point (1, 1):

• For the point to check (1, 1):
  • Left side : y = 1
  • Right side : -sqrt(3) * x + sqrt(3) = -sqrt(3) * 1 + sqrt(3) = 0
  • -> Left side is greater
• For the center of the hexagon (0, 0):
  • Left side : y = 0
  • Right side : -sqrt(3) * x + sqrt(3) = -sqrt(3) * 0 + sqrt(3) ≈ 1.732
  • -> Right side is greater

A different side is greater for each point, thus the point (1, 1) is not on the same side as the center of the hexagon, thus it is is outside the hexagon.

All in all this boils down to evaluating: dy > -sqrt(3) * dx + sqrt(3) === cy > -sqrt(3) * cx + sqrt(3).

Because the values are always the same for the center (0, 0), we can simplify the equations, which gives us for the four sides:

• sqrt(3) * dx + sqrt(3) > dy
• sqrt(3) * dx - sqrt(3) < dy
• -sqrt(3) * dx + sqrt(3) > dy
• -sqrt(3) * dx - sqrt(3) < dy

And that's it. If the check passes for each of the six sides, the point is inside the hexagon. Otherwise it's outside.

Answer 2

There's a nice generalization to a hex lattice using homogeneous coordinates, by representing the lattice as the cube-lattice intersected with the plane x+y+z=0, see https://www.redblobgames.com/grids/hexagons/#coordinates

Answer 3

What you want is the code to find out whether a point is inside a convex polygon, an hexagon being a particular case of that.

Here's a good answer: https://stackoverflow.com/a/34689268/516188

I did modify that function for my use, I find my version clearer. It's typescript (you just squint and it's javascript):

function vectorX(v: Vector): number {
    return v[1].x - v[0].x;
}

function vectorY(v: Vector): number {
    return v[1].y - v[0].y;
}

function crossProduct(v1: Vector, v2: Vector): number {
    return vectorX(v1)*vectorY(v2) - vectorY(v1)*vectorX(v2);
}

function isInConvexPolygon(testPoint: Point, polygon: Polygon): boolean {
    // https://stackoverflow.com/a/34689268/516188
    if (polygon.length < 3) {
        throw "Only supporting polygons of length at least 3";
    }
    // going through all the edges around the polygon. compute the
    // vector cross-product http://allenchou.net/2013/07/cross-product-of-2d-vectors/
    // to find out for each edge on which side of the edge is the point.
    // if the point is on the same side for all the edges, it's inside
    let initCrossIsPositive = undefined;
    for (var i=0;i<polygon.length;i++) {
        if (polygon[i].x === testPoint.x &&
            polygon[i].y === testPoint.y) {
            // testPoint is an edge of the polygon
            return true;
        }
        const curPointOnEdge = polygon[i];
        const nextPointOnEdge = polygon[(i+1)%polygon.length];
        const vector1 = <[Point,Point]>[curPointOnEdge, nextPointOnEdge];
        const vector2 = <[Point,Point]>[curPointOnEdge, testPoint];
        const cross = crossProduct(vector1, vector2);
        if (initCrossIsPositive === undefined) {
            initCrossIsPositive = cross > 0;
        } else {
            if (initCrossIsPositive !== (cross > 0)) {
                return false;
            }
        }
    }
    // all the cross-products have the same sign: we're inside
    return true;
}

Answer 4

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.
Note that this algorithm will work for any convex polygon.

Answer 5

This is what I have been using:

public bool InsideHexagon(float x, float y)
{
    // Check length (squared) against inner and outer radius
    float l2 = x * x + y * y;
    if (l2 > 1.0f) return false;
    if (l2 < 0.75f) return true; // (sqrt(3)/2)^2 = 3/4

    // Check against borders
    float px = x * 1.15470053838f; // 2/sqrt(3)
    if (px > 1.0f || px < -1.0f) return false;

    float py = 0.5f * px + y;
    if (py > 1.0f || py < -1.0f) return false;

    if (px - py > 1.0f || px - py < -1.0f) return false;

    return true;
}

px and py are the coordinates of x and y projected onto a coordinate system where it is much easier to check the boundaries.

Answer 6

Subtract the position of the center of the hexagon from your point P to get a vector V. Then, take the dot product of V with the following vectors, which correspond to the three pairs of opposing hexagon edges:

[0,1] ; the edges that are flat with the horizontal
[cos(30),sin(30)] ; the upper-right and lower-left edges
[cos(-30),sin(-30)] ; the lower-right and upper-left edges

If any of the dot products are greater in magnitude than the distance from the center of the hexagon to one of its edges, then the point is not inside the hexagon.

For reference, the dot product of vectors [a,b] and [c,d] is a*c+b*d.

The angle "30" above is in degrees ;)

Answer 7

If you reduce the problem down to checking {x = 0, y = 0, d = 1} in a single quadrant, you could make very simple.

public boolean IsInsideHexagon(float x0, float y0, float d, float x, float y) {
    float dx = Math.abs(x - x0)/d;
    float dy = Math.abs(y - y0)/d;
    float a = 0.25 * Math.sqrt(3.0);
    return (dy <= a) && (a*dx + 0.25*dy <= 0.5*a);
}

• dy <= a checks that the point is below the horizontal edge.
• a*dx + 0.25*dy <= 0.5*a checks that the point is to the left of the sloped right edge.

For {x0 = 0, y0 = 0, d = 1}, the corner points would be (±0.25, ±0.43) and (±0.5, 0.0).

Answer 8

I would first check if the point is inside the inscribed circle (you can compute the inscribed circle radius easily) or outside the circumscribed circle (that you already have).

The first means the point is in, the latter means it's out.

Statistically, most of the input points should allow you to decide based on the above simple tests.

For the worst case scenario (point is in between the inscribed and circumscribed circles), I think you can find the two vertices that are closest to the point and then see on which side of the segment V1V2 the point is (inner or outer, as relative to the O center). Special case: point is equal to one of the vertices => it's in.

If I'll have a more clever idea (or if I'll ever start to really learn trigonometry), I'll edit the answer to let you know :)

Answer 9

Looks like you know general solution: "It seems like overkill to use...". So here is my idea:

Calculate distance from point to center and let's call it l.

Then you can compare it to inradius (r) and circumradius (R). if l < r then point is inside hexagon, if l > R then outside. If r < l < R then you have to check against each side respectively, but since R - r is very small (13% of length of side of hex) so probability that you will have to do complex calculations is tiny.

Formulas can be found here: http://mathworld.wolfram.com/Hexagon.html