Подтвердить что ты не робот

Столкновение с точками JavaScript с регулярным шестиугольником

Я создаю систему на основе хэшагона в формате HTML5, и мне нужно определить, какая гексагональная плитка в сетке была нажата при нажатии на холст.

Несколько часов поиска и попытки моих собственных методов ни к чему не привели, а перенос реализаций с других языков просто смутил меня до такой степени, что мой мозг вялый.

Сетка состоит из ровных верхних правильных шестиугольников, как на этой диаграмме:

По существу, учитывая точку и переменные, указанные в этом изображении, в качестве размера для каждого шестиугольника в сетке (R, W, S, H):

Мне нужно определить, находится ли точка внутри указанного шестиугольника.

Пример вызова функции будет pointInHexagon(hexX, hexY, R, W, S, H, pointX, pointY), где hexX и hexY - это координаты для верхнего левого угла ограничивающей рамки гексагональной плитки (например, верхний левый угол на изображении выше).

Есть ли у кого-нибудь идеи, как это сделать? На данный момент скорость не очень беспокоит.

4b9b3361

ОТВЕТЫ

Ответ 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 строки. Каждая 1-я колонна из 3 будет иметь диагонали. причем каждая вторая колонка имеет диагональ. Для каждого 4-го, 5-го и 6-го столбцов из 6 строка сдвигается вниз по одной ячейке. Используя%, вы можете очень быстро определить, в какую ячейку вы находитесь. Используя метод диагонального разделения выше, математика легко и быстро.

И еще один бит. Аргумент return retPos не является обязательным. если вы вызываете функцию следующим образом

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

код не будет нести GC-удар, что еще больше улучшит скорость.

Координаты пикселов в шестнадцатеричные

Из диаграммы вопросов возвращает шестнадцатеричную ячейку x, y поз. Обратите внимание, что эта функция работает только в диапазоне 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();
    }
}

Ответ 2

Я думаю, вам нужно что-то вроде этого ~

EDITED Я сделал некоторые математики, и у вас это есть. Это не идеальная версия, но, вероятно, поможет вам...

А, вам нужен только параметр 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>

Ответ 3

Я сделал для вас решение, которое демонстрирует точку в треугольном подходе к этой проблеме.

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

ниже:

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

Ответ 4

В redblog есть полное объяснение с помощью математических и рабочих примеров.

Основная идея заключается в том, что шестиугольники расположены горизонтально на 3/4 $от размера шестиугольников, по вертикали это просто $H $, но нужно учитывать столбец, чтобы учитывать вертикальное смещение. Случай, окрашенный в красный цвет, определяется путем сравнения x с y на 1/4 W срезе.

Ответ 5

Вот полностью математическое и функциональное представление вашей проблемы. Вы заметите, что в этом коде нет if и then, кроме тройного, чтобы изменить цвет текста в зависимости от положения мыши. Вся эта работа на самом деле не более чем простая простая математика только одной строки;

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

и этот код можно использовать повторно для всех полигонов от треугольника до круга. Поэтому, если вы заинтересованы, пожалуйста, прочитайте. Это очень просто.

Чтобы отобразить функциональность, мне пришлось разработать имитирующую модель проблемы. Я рисую многоугольник на холсте, используя простую функцию полезности. Чтобы общее решение работало для любого полигона. Следующий фрагмент примет контекст canvas c, radius r, число сторон s и локальные координаты центра в холсте cx и cy в качестве аргументов и нарисуют многоугольник в данном контексте холста в правильном положении.

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

У нас есть некоторые другие служебные функции, которые легко понять, что именно они делают. Однако самая важная часть - проверить, плавает ли мышь над нашим полигоном или нет. Это выполняется с помощью функции утилиты isMouseIn. Это в основном вычисление расстояния и угла положения мыши к центру многоугольника. Затем, сравнивая его с границами многоугольника. Границы многоугольника могут быть выражены простой тригонометрией, точно так же, как мы вычислили вершины в функции drawPolygon.

Мы можем думать о нашем полигоне как о круге с колеблющимся радиусом на частоте числа сторон. Пик колебаний находится при заданном значении радиуса r (который находится в вершинах под углом 2π/s, где s - количество сторон), а минимум m равен r*Math.cos(Math.PI/s) (каждый показывает при at угол 2π/s + 2π/2s = 3π/s). Я вполне уверен, что идеальный способ выражения многоугольника может быть выполнен преобразованием Фурье, но здесь нам это не нужно. Все, что нам нужно, это постоянная составляющая радиуса, которая представляет собой среднее значение минимума и максимума, (r+m)/2 и осциллирующую составляющую с частотой числа сторон, s и максимум амплитуды - минимум)/2 поверх нее, Math.cos(a*s)*(r-m)/2. Разумеется, в соответствии с состояниями Фурье мы могли бы иметь меньшие колебательные компоненты, но с шестиугольником вам не нужна дальнейшая итерация, а с треугольником, который вы, возможно, захотите. Итак, вот наше многоугольное представление в математике.

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

Теперь нам нужно рассчитать угол и расстояние нашей позиции мыши относительно центра многоугольника и сравнить его с приведенным выше математическим выражением, которое представляет наш многоугольник. Итак, все вместе наша магическая функция организована следующим образом:

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

Таким образом, следующий код демонстрирует, как вы можете решить проблему.

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