JavaScript Point Collision with Regular Hexagon

Question

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 1

Simple & fast diagonal rectangle slice.

Looking at the other answers I see that they have all a little over complicated the problem. The following is an order of magnitude quicker than the accepted answer and does not require any complicated data structures, iterators, or generate dead memory and unneeded GC hits. It returns the hex cell row and column for any related set of R, H, S or W. The example uses R = 50.

Part of the problem is finding which side of a rectangle a point is if the rectangle is split diagonally. This is a very simple calculation and is done by normalising the position of the point to test.

Slice any rectangle diagonally

Example a rectangle of width w, and height h split from top left to bottom right. To find if a point is left or right. Assume top left of rectangle is at rx,ry

var x = ?;
var y = ?;
x = ((x - rx) % w) / w;
y = ((y - ry) % h) / h;
if (x > y) { 
    // point is in the upper right triangle
} else if (x < y) {
    // point is in lower left triangle
} else {
    // point is on the diagonal
}

If you want to change the direction of the diagonal then just invert one of the normals

x = 1 - x;  // invert x or y to change the direction the rectangle is split
if (x > y) { 
    // point is in the upper left triangle
} else if (x < y) {
    // point is in lower right triangle
} else {
    // point is on the diagonal
}

Split into sub cells and use %

The rest of the problem is just a matter of splitting the grid into (R / 2) by (H / 2) cells width each hex covering 4 columns and 2 rows. Every 1st column out of 3 will have diagonals. with every second of these column having the diagonal flipped. For every 4th, 5th, and 6th column out of 6 have the row shifted down one cell. By using % you can very quickly determine which hex cell you are on. Using the diagonal split method above make the math easy and quick.

And one extra bit. The return argument retPos is optional. if you call the function as follows

var retPos;
mainLoop(){
    retPos = getHex(mouse.x, mouse.y, retPos);
}

the code will not incur a GC hit, further improving the speed.

Pixel to Hex coordinates

From Question diagram returns hex cell x,y pos. Please note that this function only works in the range 0 <= x, 0 <= y if you need negative coordinates subtract the min negative pixel x,y coordinate from the input

// the values as set out in the question image
var r = 50; 
var w = r * 2;
var h = Math.sqrt(3) * r;
// returns the hex grid x,y position in the object retPos.
// retPos is created if not supplied;
// argument x,y is pixel coordinate (for mouse or what ever you are looking to find)
function getHex (x, y, retPos){
    if(retPos === undefined){
        retPos = {};
    }
    var xa, ya, xpos, xx, yy, r2, h2;
    r2 = r / 2;
    h2 = h / 2;
    xx = Math.floor(x / r2);
    yy = Math.floor(y / h2);
    xpos = Math.floor(xx / 3);
    xx %= 6;
    if (xx % 3 === 0) {      // column with diagonals
        xa = (x % r2) / r2;  // to find the diagonals
        ya = (y % h2) / h2;
        if (yy % 2===0) {
            ya = 1 - ya;
        }
        if (xx === 3) {
            xa = 1 - xa;
        }
        if (xa > ya) {
            retPos.x = xpos + (xx === 3 ? -1 : 0);
            retPos.y = Math.floor(yy / 2);
            return retPos;
        }
        retPos.x = xpos + (xx === 0 ? -1 : 0);
        retPos.y = Math.floor((yy + 1) / 2);
        return retPos;
    }
    if (xx < 3) {
        retPos.x = xpos + (xx === 3 ? -1 : 0);
        retPos.y = Math.floor(yy / 2);
        return retPos;
    }
    retPos.x = xpos + (xx === 0 ? -1 : 0);
    retPos.y = Math.floor((yy + 1) / 2);
    return retPos;
}

Hex to pixel

And a helper function that draws a cell given the cell coordinates.

// Helper function draws a cell at hex coordinates cellx,celly
// fStyle is fill style
// sStyle is strock style;
// fStyle and sStyle are optional. Fill or stroke will only be made if style given
function drawCell1(cellPos, fStyle, sStyle){    
    var cell = [1,0, 3,0, 4,1, 3,2, 1,2, 0,1];
    var r2 = r / 2;
    var h2 = h / 2;
    function drawCell(x, y){
        var i = 0;
        ctx.beginPath();
        ctx.moveTo((x + cell[i++]) * r2, (y + cell[i++]) * h2)
        while (i < cell.length) {
            ctx.lineTo((x + cell[i++]) * r2, (y + cell[i++]) * h2)
        }
        ctx.closePath();
    }
    ctx.lineWidth = 2;
    var cx = Math.floor(cellPos.x * 3);
    var cy = Math.floor(cellPos.y * 2);
    if(cellPos.x  % 2 === 1){
        cy -= 1;
    }
    drawCell(cx, cy);
    if (fStyle !== undefined && fStyle !== null){  // fill hex is fStyle given
        ctx.fillStyle = fStyle
        ctx.fill();
    }
    if (sStyle !== undefined ){  // stroke hex is fStyle given
        ctx.strokeStyle = sStyle
        ctx.stroke();
    }
}

Answer 2

I think you need something like this~

EDITED I did some maths and here you have it. This is not a perfect version but probably will help you...

Ah, you only need a R parameter because based on it you can calculate H, W and S. That is what I understand from your description.

// setup canvas for demo
var canvas = document.getElementById('canvas');
canvas.width = 300;
canvas.height = 275;
var context = canvas.getContext('2d');
var hexPath;
var hex = {
  x: 50,
  y: 50,
  R: 100
}

// Place holders for mouse x,y position
var mouseX = 0;
var mouseY = 0;

// Test for collision between an object and a point
function pointInHexagon(target, pointX, pointY) {
  var side = Math.sqrt(target.R*target.R*3/4);
  
  var startX = target.x
  var baseX = startX + target.R / 2;
  var endX = target.x + 2 * target.R;
  var startY = target.y;
  var baseY = startY + side; 
  var endY = startY + 2 * side;
  var square = {
    x: startX,
    y: startY,
    side: 2*side
  }

  hexPath = new Path2D();
  hexPath.lineTo(baseX, startY);
  hexPath.lineTo(baseX + target.R, startY);
  hexPath.lineTo(endX, baseY);
  hexPath.lineTo(baseX + target.R, endY);
  hexPath.lineTo(baseX, endY);
  hexPath.lineTo(startX, baseY);

  if (pointX >= square.x && pointX <= (square.x + square.side) && pointY >= square.y && pointY <= (square.y + square.side)) {
    var auxX = (pointX < target.R / 2) ? pointX : (pointX > target.R * 3 / 2) ? pointX - target.R * 3 / 2 : target.R / 2;
    var auxY = (pointY <= square.side / 2) ? pointY : pointY - square.side / 2;
    var dPointX = auxX * auxX;
    var dPointY = auxY * auxY;
    var hypo = Math.sqrt(dPointX + dPointY);
    var cos = pointX / hypo;

    if (pointX < (target.x + target.R / 2)) {
      if (pointY <= (target.y + square.side / 2)) {
        if (pointX < (target.x + (target.R / 2 * cos))) return false;
      }
      if (pointY > (target.y + square.side / 2)) {
        if (pointX < (target.x + (target.R / 2 * cos))) return false;
      }
    }

    if (pointX > (target.x + target.R * 3 / 2)) {
      if (pointY <= (target.y + square.side / 2)) {
        if (pointX < (target.x + square.side - (target.R / 2 * cos))) return false;
      }
      if (pointY > (target.y + square.side / 2)) {
        if (pointX < (target.x + square.side - (target.R / 2 * cos))) return false;
      }
    }
    return true;
  }
  return false;
}

// Loop
setInterval(onTimerTick, 33);

// Render Loop
function onTimerTick() {
  // Clear the canvas
  canvas.width = canvas.width;

  // see if a collision happened
  var collision = pointInHexagon(hex, mouseX, mouseY);

  // render out text
  context.fillStyle = "Blue";
  context.font = "18px sans-serif";
  context.fillText("Collision: " + collision + " | Mouse (" + mouseX + ", " + mouseY + ")", 10, 20);

  // render out square    
  context.fillStyle = collision ? "red" : "green";
  context.fill(hexPath);
}

// Update mouse position
canvas.onmousemove = function(e) {
  mouseX = e.offsetX;
  mouseY = e.offsetY;
}

#canvas {
  border: 1px solid black;
}

<canvas id="canvas"></canvas>

Just replace your pointInHexagon(hexX, hexY, R, W, S, H, pointX, pointY) by the var hover = ctx.isPointInPath(hexPath, x, y).

• This is for Creating and copying paths
• This is about the Collision Detection

var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");

var hexPath = new Path2D();
hexPath.lineTo(25, 0);
hexPath.lineTo(75, 0);
hexPath.lineTo(100, 43);
hexPath.lineTo(75, 86);
hexPath.lineTo(25, 86);
hexPath.lineTo(0, 43);


function draw(hover) {
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  ctx.fillStyle = hover ? 'blue' : 'red';
  ctx.fill(hexPath);
}

canvas.onmousemove = function(e) {
  var x = e.clientX - canvas.offsetLeft, y = e.clientY - canvas.offsetTop;
  var hover = ctx.isPointInPath(hexPath, x, y)
  draw(hover)
};
draw();

<canvas id="canvas"></canvas>

Answer 3

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

Answer 4

Here is a fully mathematical and functional representation of your problem. You will notice that there are no ifs and thens in this code other than the ternary to change the color of the text depending on the mouse position. This whole job is in fact nothing more than pure simple math of just one line;

(r+m)/2 + Math.cos(a*s)*(r-m)/2;

and this code is reusable for all polygons from triangle to circle. So if interested please read on. It's very simple.

In order to display the functionality I had to develop a mimicking model of the problem. I draw a polygon on a canvas by utilizing a simple utility function. So that the overall solution should work for any polygon. The following snippet will take the canvas context c, radius r, number of sides s, and the local center coordinates in the canvas cx and cy as arguments and draw a polygon on the given canvas context at the right position.

function drawPolgon(c, r, s, cx, cy){ //context, radius, sides, center x, center y
  c.beginPath();
  c.moveTo(cx + r,cy);
  for(var p = 1; p < s; p++) c.lineTo(cx + r*Math.cos(p*2*Math.PI/s), cy + r*Math.sin(p*2*Math.PI/s));
  c.closePath();
  c.stroke();
}

We have some other utility functions which one can easily understand what exactly they are doing. However the most important part is to check whether the mouse is floating over our polygon or not. It's done by the utility function isMouseIn. It's basically calculating the distance and the angle of the mouse position to the center of the polygon. Then, comparing it with the boundaries of the polygon. The boundaries of the polygon can be expressed by simple trigonometry, just like we have calculated the vertices in the drawPolygon function.

We can think of our polygon as a circle with an oscillating radius at the frequency of number of sides. The oscillation's peak is at the given radius value r (which happens to be at the vertices at angle 2π/s where s is the number of sides) and the minimum m is r*Math.cos(Math.PI/s) (each shows at at angle 2π/s + 2π/2s = 3π/s). I am pretty sure the ideal way to express a polygon could be done by the Fourier transformation but we don't need that here. All we need is a constant radius component which is the average of minimum and maximum, (r+m)/2 and the oscillating component with the frequency of number of sides, s and the amplitude value maximum - minimum)/2 on top of it, Math.cos(a*s)*(r-m)/2. Well of course as per Fourier states we might carry on with smaller oscillating components but with a hexagon you don't really need further iteration while with a triangle you possibly would. So here is our polygon representation in math.

(r+m)/2 + Math.cos(a*s)*(r-m)/2;

Now all we need is to calculate the angle and distance of our mouse position relative to the center of the polygon and compare it with the above mathematical expression which represents our polygon. So all together our magic function is orchestrated as follows;

function isMouseIn(r,s,cx,cy,mx,my){
  var m = r*Math.cos(Math.PI/s),   // the min dist from an edge to the center
      d = Math.hypot(mx-cx,my-cy), // the mouse's distance to the center of the polygon
      a = Math.atan2(cy-my,mx-cx); // angle of the mouse pointer
  return d <= (r+m)/2 + Math.cos(a*s)*(r-m)/2;
}

So the following code demonstrates how you might approach to solve your problem.

// Generic function to draw a polygon on the canvas

function drawPolgon(c, r, s, cx, cy){ //context, radius, sides, center x, center y
  c.beginPath();
  c.moveTo(cx + r,cy);
  for(var p = 1; p < s; p++) c.lineTo(cx + r*Math.cos(p*2*Math.PI/s), cy + r*Math.sin(p*2*Math.PI/s));
  c.closePath();
  c.stroke();
}

// To write the mouse position in canvas local coordinates

function writeText(c,x,y,msg,col){
  c.clearRect(0, 0, 300, 30);
  c.font = "10pt Monospace";
  c.fillStyle = col;
  c.fillText(msg, x, y);
}

// Getting the mouse position and coverting into canvas local coordinates

function getMousePos(c, e) {
  var rect = c.getBoundingClientRect();
  return { x: e.clientX - rect.left,
           y: e.clientY - rect.top
         };
}

// To check if mouse is inside the polygone

function isMouseIn(r,s,cx,cy,mx,my){
  var m = r*Math.cos(Math.PI/s),
      d = Math.hypot(mx-cx,my-cy),
      a = Math.atan2(cy-my,mx-cx);
  return d <= (r+m)/2 + Math.cos(a*s)*(r-m)/2;
}

// the event listener callback

function mouseMoveCB(e){
  var mp = getMousePos(cnv, e),
     msg = 'Mouse at: ' + mp.x + ',' + mp.y,
     col = "black",
  inside = isMouseIn(radius,sides,center[0],center[1],mp.x,mp.y);
  writeText(ctx, 10, 25, msg, inside ? "turquoise" : "red");
}

// body of the JS code

var cnv = document.getElementById("myCanvas"),
    ctx = cnv.getContext("2d"),
  sides = 6,
 radius = 100,
 center = [150,150];
cnv.addEventListener('mousemove', mouseMoveCB, false);
drawPolgon(ctx, radius, sides, center[0], center[1]);

#myCanvas { background: #eee;
                 width: 300px;
                height: 300px;
                border: 1px #ccc solid
          }

<canvas id="myCanvas" width="300" height="300"></canvas>

Answer 5

At the redblog there is a full explanation with math and working examples.

The main idea is that hexagons are horizontally spaced by $3/4$ of hexagons size, vertically it is simply $H$ but the column needs to be taken to take vertical offset into account. The case colored red is determined by comparing x to y at 1/4 W slice.