与正六边形的JavaScript点碰撞

Question

我正在制作一个基于HTML5画布六边形网格的系统,我需要能够检测单击画布时单击网格中的六边形拼贴.

几个小时的搜索和尝试我自己的方法没有任何结果,从其他语言移植实现只是让我困惑到我的大脑迟钝的点.

网格由平顶正六边形组成,如下图所示:

基本上,给定一个点和此图像中指定的变量作为网格中每个六边形的大小(R,W,S,H):

我需要能够确定一个点是否在给定的六边形内.

一个示例函数调用将是pointInHexagon(hexX, hexY, R, W, S, H, pointX, pointY)hexX和hexY是六边形图块边界框左上角的坐标(如上图中的左上角).

是否有人知道如何做到这一点？目前速度并不是很重要.

Answer 1

简单快速的对角矩形切片.

看看其他答案,我看到他们有点过于复杂的问题.以下比接受的答案快一个数量级,并且不需要任何复杂的数据结构,迭代器,或生成死存储器和不需要的GC命中.它返回R,H,S或W的任何相关集合的十六进制单元格行和列.该示例使用R = 50.

部分问题是如果矩形是对角分割的,则找到矩形的哪一边是一个点.这是一个非常简单的计算,通过标准化要测试的点的位置来完成.

对角切割任何矩形

示例宽度为w的矩形,高度h从左上角到右下角分割.查找点是左还是右.假设矩形的左上角是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
}

如果你想改变对角线的方向,那么只需反转其中一个法线

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
}

分成子单元格并使用%

剩下的问题只是将网格分成(R/2)个(H/2)单元格宽度,每个六边形覆盖4列和2行.每3列中的第1列将具有对角线.这些柱的每一秒都有对角线翻转.对于每6个中的第4列,第5列和第6列,行向下移动一个单元格.通过使用%,您可以非常快速地确定您所在的十六进制单元格.使用上面的对角线分割方法可以使数学变得简单快捷.

还有一点.return参数retPos是可选的.如果你按如下方式调用该函数

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

代码不会导致GC命中,进一步提高速度.

像素到十六进制坐标

从问题图表返回hex cell x,ypos.请注意,此功能仅适用于该范围0 <= x,0 <= y如果您需要负坐标,则从输入中减去最小负像素x,y坐标

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

十六进制到像素

一个辅助函数,在给定单元格坐标的情况下绘制一个单元格.

// 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

我想你需要这样的东西~

编辑 我做了一些数学计算，在这里你得到了它。这不是一个完美的版本，但可能会对您有所帮助......

啊，你只需要一个R参数，因为根据它你可以计算H、W和S。从你的描述中我是这么理解的。

// 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>

只需将您的替换pointInHexagon(hexX, hexY, R, W, S, H, pointX, pointY)为var hover = ctx.isPointInPath(hexPath, x, y).

• 这是用于创建和复制路径
• 这是关于碰撞检测的

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>