Punto de colisión de JavaScript con hexágono regular




html5 canvas (4)

He creado una solución para usted que demuestra el enfoque de punto en triángulo para este problema.

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

Matemáticas a continuación:

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

Estoy creando un sistema basado en una rejilla hexagonal de lienzo HTML5 y necesito poder detectar en qué cuadrícula hexagonal se ha hecho clic en una cuadrícula cuando se hace clic en el lienzo.

Varias horas de búsqueda y prueba de mis propios métodos no llevaron a nada, y portar implementaciones de otros idiomas simplemente me ha confundido con un punto en el que mi cerebro es lento.

La cuadrícula consiste en hexágonos regulares con cubierta plana como en este diagrama:

Esencialmente, dado un punto y las variables especificadas en esta imagen como el tamaño de cada hexágono en la cuadrícula (R, W, S, H):

Necesito poder determinar si un punto está dentro de un hexágono dado.

Un ejemplo de llamada de función sería pointInHexagon(hexX, hexY, R, W, S, H, pointX, pointY) donde hexX y hexY son las coordenadas de la esquina superior izquierda del cuadro delimitador de un mosaico hexagonal (como la esquina superior izquierda en la imagen de arriba).

¿Hay alguien que tenga alguna idea de cómo hacer esto? La velocidad no es una gran preocupación por el momento.


Creo que necesitas algo como esto ~

EDITADO Hice algunas matemáticas y aquí las tienes. Esta no es una versión perfecta pero probablemente te ayude ...

Ah, solo necesitas un parámetro R porque en función de él puedes calcular H , W y S Eso es lo que entiendo de su descripción.

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

Simplemente reemplace su pointInHexagon(hexX, hexY, R, W, S, H, pointX, pointY) por la 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>


En el redblog hay una explicación completa con matemáticas y ejemplos de trabajo.

La idea principal es que los hexágonos están espaciados horizontalmente por $ 3/4 $ del tamaño de los hexágonos, verticalmente es simplemente $ H $ pero la columna debe tomarse para tener en cuenta el desplazamiento vertical. El color rojo de la caja se determina comparando x con y en una división de 1/4 W.


Rectángulo diagonal simple y rápido.

Mirando las otras respuestas, veo que todas ellas han superado un poco el problema. El siguiente es un orden de magnitud más rápido que la respuesta aceptada y no requiere estructuras de datos complicadas, iteradores, ni genera memoria muerta y aciertos de GC innecesarios. Devuelve la fila y columna de celda hexadecimal para cualquier conjunto relacionado de R, H, S o W. El ejemplo usa R = 50.

Parte del problema es encontrar qué lado de un rectángulo es un punto si el rectángulo está dividido en diagonal. Este es un cálculo muy simple y se realiza normalizando la posición del punto a probar.

Cortar cualquier rectángulo en diagonal

Ejemplo de un rectángulo de ancho w, y la altura h se divide desde la parte superior izquierda a la inferior derecha. Para saber si un punto es izquierdo o derecho. Supongamos que la esquina superior izquierda del rectángulo está en 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
}

Si desea cambiar la dirección de la diagonal, simplemente invierta uno de los normales

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
}

Dividir en sub celdas y usar%

El resto del problema es solo una cuestión de dividir la cuadrícula en (R / 2) por (H / 2) celdas de ancho de cada hexágono que cubre 4 columnas y 2 filas. Cada 1ª columna de cada 3 tendrá diagonales. con cada segundo de estas columnas con la diagonal invertida. Por cada 4ª, 5ª y 6ª columna de las 6, la fila se desplazó hacia abajo una celda. Al usar%, puedes determinar muy rápidamente en qué celda hexadecimal estás. Usar el método de división diagonal anterior hace que las matemáticas sean fáciles y rápidas.

Y un bit extra. El argumento de retorno retPos es opcional. Si llama a la función de la siguiente manera

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

el código no incurrirá en un golpe de GC, mejorando aún más la velocidad.

Pixel a Hex coordenadas

Desde el diagrama de la pregunta devuelve la celda hexadecimal x , y pos. Tenga en cuenta que esta función solo funciona en el rango 0 <= x , 0 <= y si necesita coordenadas negativas reste el píxel negativo mínimo x, coordenada y de la entrada

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

Hexagonal a píxel

Y una función auxiliar que dibuja una celda dadas las coordenadas de la celda.

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




hexagonal-tiles