13

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.

7
  • 2
    You also have to give information about the orientation of the hexagon (0-60 degrees)!
    – Curd
    Mar 4, 2011 at 11:55
  • @Curd Good point, thanks. I've edited the post, not sure what angle that would be though, 0 degrees I'm guessing.
    – Adam
    Mar 4, 2011 at 11:58
  • I don't think there's an API for it, unfortunately. Mar 4, 2011 at 11:59
  • @Andrzej Thought as much. Am I not missing a simpler way than the one I discussed, however?
    – Adam
    Mar 4, 2011 at 12:02
  • @Andrzej: I think that there can not and should not be an API for everything. The programmers would be out of job on the long run. :-) Mar 4, 2011 at 12:18

8 Answers 8

9

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.

5
  • I think this is the best way - if (a,b) is on the same side of each line-segment as (x,y) then the point is inside the hexagon. Mar 4, 2011 at 12:32
  • 3
    Would it be possible to elaborate on this? I think I get it conceptually but the code snippet you have there is not quite making sense to me. May 12, 2011 at 2:56
  • 1
    Can you explain the whole solution? Maybe with an example. Thank you so much. Mar 23, 2015 at 14:15
  • Only 4 checks are needed, not 6.
    – eirirlar
    Jun 9, 2021 at 19:17
  • This comment needs some more explaining and some images. Sep 10, 2022 at 14:00
9

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).

3
  • 1
    I like your approach, but I think the formula is off. Your function says that dx=1, dy=0 is inside the hexagon. Mar 4, 2011 at 23:32
  • (1,0) is just the edge of the projected hexagon. If you do not want to include the edges, you can change <= to <. Not that it makes much difference with floating-point numbers. Mar 5, 2011 at 13:27
  • If your diameter is 1, then (.5,0) is the edge of the projected hexagon. Mar 8, 2011 at 10:33
9

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.

enter image description here

1
  • nice! what about just shrinking x via px = x / sqrt(3) to get a square (diamond) with the corners clipped so you'd just need to test |px| < 1/2 and |px| + |py| < 1? Feb 26, 2020 at 19:33
4

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

1

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 :)

1
  • "you can find the two vertices that are closest to the point" - or take the angle of the point, relative to a line connecting the centre of the hexagon to any one of its vertices. Modulo pi/3, this tells you where your point sits relative to an equilateral triangle, and the formula for the distance from the vertex of that triangle to the opposite edge, along a line at a given angle, can't be that hard. Mar 4, 2011 at 14:38
0

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 ;)

0

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;
}
0

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

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.