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

html5 canvas

Question

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.

Answer 1

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

Answer 2

Aquí hay una representación totalmente matemática y funcional de su problema. Notará que no hay if y sy s en este código que no sea el ternario para cambiar el color del texto dependiendo de la posición del mouse. De hecho, todo este trabajo no es más que pura matemática simple de una sola línea;

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

y este código es reutilizable para todos los polígonos de triángulo a círculo. Así que si está interesado por favor siga leyendo. Es muy sencillo.

Para mostrar la funcionalidad, tuve que desarrollar un modelo de imitación del problema. Dibujé un polígono en un lienzo utilizando una función de utilidad simple. Para que la solución global funcione para cualquier polígono. El siguiente fragmento tomará el contexto del lienzo c , el radio r , el número de lados s y las coordenadas del centro local en los lienzos cx y cy como argumentos y dibujará un polígono en el contexto del lienzo dado en la posición correcta.

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

Tenemos otras funciones de utilidad que se pueden entender fácilmente qué están haciendo exactamente. Sin embargo, la parte más importante es verificar si el mouse está flotando sobre nuestro polígono o no. Es hecho por la función de utilidad isMouseIn . Básicamente, se calcula la distancia y el ángulo de la posición del mouse hacia el centro del polígono. Luego, comparándolo con los límites del polígono. Los límites del polígono se pueden expresar mediante una simple trigonometría, tal como hemos calculado los vértices en la función drawPolygon .

Podemos pensar en nuestro polígono como un círculo con un radio oscilante en la frecuencia de número de lados. El pico de la oscilación está en el valor de radio dado r (que ocurre en los vértices en el ángulo 2π/s donde s es el número de lados) y el mínimo m es r*Math.cos(Math.PI/s) (cada uno muestra un ángulo de 2π/s + 2π/2s = 3π/s ). Estoy bastante seguro de que la transformación ideal de Fourier podría hacer la forma ideal de expresar un polígono, pero no lo necesitamos aquí. Todo lo que necesitamos es un componente de radio constante que sea el promedio de mínimo y máximo, (r+m)/2 y el componente oscilante con la frecuencia de número de lados, s el valor de amplitud máximo - mínimo) / 2 encima de it, Math.cos(a*s)*(rm)/2 . Bueno, por supuesto, según los estados de Fourier, podríamos continuar con componentes oscilantes más pequeños, pero con un hexágono no necesita más iteración mientras que con un triángulo es posible. Así que aquí está nuestra representación de polígonos en matemáticas.

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

Ahora todo lo que necesitamos es calcular el ángulo y la distancia de la posición de nuestro mouse en relación con el centro del polígono y compararla con la expresión matemática anterior que representa nuestro polígono. Así que todos juntos nuestra función mágica está orquestada de la siguiente manera;

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

Por lo tanto, el siguiente código muestra cómo podría acercarse para resolver su problema.

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

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

• Esto es para crear y copiar rutas.
• Esto es sobre la detección de colisiones.

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 4

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.

Answer 5

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