Tobsta Tobsta - 15 days ago 5
Javascript Question

JavaScript Point Collision with Regular Hexagon

I'm making an HTML5 canvas hexagon grid based system and I need to be able to detect what hexagonal tile in a grid has been clicked when the canvas is clicked.

Several hours of searching and trying my own methods led to nothing, and porting implementations from other languages has simply confused me to a point where my brain is sluggish.

The grid consists of flat topped regular hexagons like in this diagram:



Essentially, given a point and the variables specified in this image as the sizing for every hexagon in the grid (R, W, S, H):



I need to be able to determine whether a point is inside a hexagon given.

An example function call would be

pointInHexagon(hexX, hexY, R, W, S, H, pointX, pointY)
where hexX and hexY are the coordinates for the top left corner of the bounding box of a hexagonal tile (like the top left corner in the image above).

Is there anyone who has any idea how to do this? Speed isn't much of a concern for the moment.

Answer

I've made a solution for you that demonstrates the point in triangle approach to this problem.

http://codepen.io/spinvector/pen/gLROEp

maths below:

isPointInside(point)
{
    // Point in triangle algorithm from http://totologic.blogspot.com.au/2014/01/accurate-point-in-triangle-test.html
    function pointInTriangle(x1, y1, x2, y2, x3, y3, x, y)
    {
        var denominator = ((y2 - y3)*(x1 - x3) + (x3 - x2)*(y1 - y3));
        var a = ((y2 - y3)*(x - x3) + (x3 - x2)*(y - y3)) / denominator;
        var b = ((y3 - y1)*(x - x3) + (x1 - x3)*(y - y3)) / denominator;
        var c = 1 - a - b;

        return 0 <= a && a <= 1 && 0 <= b && b <= 1 && 0 <= c && c <= 1;
    }

    // A Hex is composite of 6 trianges, lets do a point in triangle test for each one.
    // Step through our triangles
    for (var i = 0; i < 6; i++) {
        // check for point inside, if so, return true for this function;
        if(pointInTriangle( this.origin.x, this.origin.y,
                            this.points[i].x, this.points[i].y,
                            this.points[(i+1)%6].x, this.points[(i+1)%6].y,
                            point.x, point.y))
            return true;
    }
    // Point must be outside.
    return false;
}