Шестиугольные сетки, как вы находите, в каком шестиугольнике находится точка?

Ответ 1

(ОБНОВЛЕНО: обновленный код, чтобы сделать его более понятным и более эффективным) (ОБНОВЛЕНО: уменьшенная длина ответа, исправлены ошибки в коде, улучшенное качество изображений)

На этом изображении показан верхний левый угол шестиугольной сетки, а наложенная - синяя квадратная сетка. Легко найти, какой из квадратов находится внутри, и это дало бы грубое приближение, из которого тоже был шестиугольник. Белые части шестиугольников показывают, где квадратная и гексагональная сетка имеют одни и те же координаты, а серые части шестиугольников показывают, где они этого не делают.

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

private final Hexagon getSelectedHexagon(int x, int y)
{
    // Find the row and column of the box that the point falls in.
    int row = (int) (y / gridHeight);
    int column;

    boolean rowIsOdd = row % 2 == 1;

    // Is the row an odd number?
    if (rowIsOdd)// Yes: Offset x to match the indent of the row
        column = (int) ((x - halfWidth) / gridWidth);
    else// No: Calculate normally
        column = (int) (x / gridWidth);

В этот момент у нас есть строка и столбец окна, в котором находится наша точка, затем нам нужно проверить нашу точку на двух верхних краях шестиугольника, чтобы увидеть, находится ли наша точка в любом из шестиугольников выше:

    // Work out the position of the point relative to the box it is in
    double relY = y - (row * gridHeight);
    double relX;

    if (rowIsOdd)
        relX = (x - (column * gridWidth)) - halfWidth;
    else
        relX = x - (column * gridWidth);

Наличие относительных координат делает следующий шаг проще.

Как и на изображении выше, если y нашей точки > mx + c, мы знаем, что наша точка лежит над линией, а в нашем случае шестиугольник выше и слева от текущей строки и столбца. Обратите внимание, что система координат в java имеет y, начинающуюся с 0 в верхнем левом углу экрана, а не внизу слева, как обычно в математике, поэтому отрицательный градиент, используемый для левого края, и положительный градиент, используемый для правого.

    // Work out if the point is above either of the hexagon top edges
    if (relY < (-m * relX) + c) // LEFT edge
        {
            row--;
            if (!rowIsOdd)
                column--;
        }
    else if (relY < (m * relX) - c) // RIGHT edge
        {
            row--;
            if (rowIsOdd)
                column++;
        }

    return hexagons[column][row];
}

Быстрое объяснение переменных, используемых в приведенном выше примере:

m - градиент, поэтому m = c/halfWidth

Ответ 2

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

Вопрос можно перефразировать: если любые х, у найдут шестиугольник, центр которого ближе всего к х, у

то есть. минимизировать dist_squared (Hex [n].center, (x, y)) над n (квадрат означает, что вам не нужно беспокоиться о квадратных корнях, которые сохраняют некоторый процессор)

Однако сначала нужно сузить число шестиугольников для проверки - мы можем сузить его до максимума 5 следующим способом:

Итак, первый шаг. Выразите свою точку (x, y) в UV-пространстве (x, y) = lambdaU + muV, so = (lambda, mu) в УФ-пространстве

Это просто двумерное матричное преобразование (http://playtechs.blogspot.co.uk/2007/04/hex-grids.html может оказаться полезным, если вы не понимаете линейные преобразования).

Теперь, учитывая точку (lambda, mu), если мы округлим оба до ближайшего целого числа, мы получим следующее:

Всюду в зеленой площади возвращается обратно (2,1)

Таким образом, большинство точек в пределах этой Зеленого квадрата будут правильными, т.е. они находятся в шестиугольнике (2,1).

Но некоторые точки должны возвращать шестиугольник # (2,2), т.е.

Аналогичным образом некоторые должны возвращать шестиугольник # (3,1). А затем на противоположном углу этого зеленого параллелограмма будет еще две области.

Итак, если int (lambda, mu) = (p, q), то мы, вероятно, находимся внутри шестиугольника (p, q), но мы также можем быть внутри шестиугольников (p + 1, q), (p, q +1), (p-1, q) или (p, q-1)

Несколько способов определить, какой из них имеет место. Проще всего было бы преобразовать центры всех этих 5 шестиугольников обратно в исходную систему координат и найти наиболее близкую к нашей точке.

Но оказывается, что вы можете сузить это до ~ 50% времени, не проводя дистанционных проверок, ~ 25% времени, выполняющего одну дистанционную проверку, а оставшиеся ~ 25% времени делают 2 дистанционных проверки (I "Угадывая цифры, просматривая области, на которые каждая проверка работает):

p,q = int(lambda,mu)

if lambda * mu < 0.0:
    // opposite signs, so we are guaranteed to be inside hexagon (p,q)
    // look at the picture to understand why; we will be in the green regions
    outPQ = p,q

else:
    // circle check
    distSquared = dist2( Hex2Rect(p,q), Hex2Rect(lambda, mu) )

    if distSquared < .5^2:
        // inside circle, so guaranteed inside hexagon (p,q)
        outPQ = p,q

    else:
        if lambda > 0.0:
            candHex = (lambda>mu) ? (p+1,q): (p,q+1)
        else:
            candHex = (lambda<mu) ? (p-1,q) : (p,q-1)

И этот последний тест можно убрать:

     else:
        // same sign, but which end of the parallelogram are we?
        sign = (lambda<0) ? -1 : +1
        candHex = ( abs(lambda) > abs(mu) ) ? (p+sign,q) : (p,q+sign)

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

        dist2_cand = dist2( Hex2Rect(lambda, mu), Hex2Rect(candHex) )

        outPQ = ( distSquared < dist2_cand ) ? (p,q) : candHex

Функция Dist2_hexSpace (A, B) еще больше упростит процесс.

Ответ 3

Я начал с просмотра @pi answer fooobar.com/questions/192504/... и подумал, что было бы интересно попробовать что-то подобное в координатах куба с UVW-пространством (а не с 2D, осевое, УФ-пространство).

Следующие уравнения отображают (x, y) = > (u, v, w)

u = (2/3)*x;
v = -(1/3)*x + (1/2)*y;
w = -(1/3)*x - (1/2)*y;

Тогда это так же просто, как округление u, v и w до ближайшего целого числа и переход на x, y. Однако существует серьезная проблема...

В ответе выше, он отметил, что округление в УФ-пространстве будет иметь несколько областей, которые неверно отображают:

Это также происходит при использовании координат куба:

Любая область оранжевых треугольников составляет > 0,5 единицы от центра шестиугольника, а при округлении будет округлять AWAY от центра. Это показано выше, поскольку что-либо в красном треугольнике (слева от линии u = 1,5) будет неправильно округлено u до u = 1, а не u = 2.

Некоторые ключевые замечания здесь, хотя...

1. Оранжевые/красные проблемные области не перекрываются

2. В координатах куба действительные шестигранные центры имеют u + v + w = ​​0

В приведенном ниже коде, u, v и w, все округлены с самого начала, округляя только проблему, если округленные координаты не суммируются до нуля.

uR = Math.round(u);
vR = Math.round(v);
wR = Math.round(w);

Если они не суммируются с нулем, потому что проблемные области не перекрываются, будет только одна координата, которая будет округлена неправильно. Эта координата также является координатой, которая была округлена больше всего.

arr = [ Math.abs(u-uR), Math.abs(v-vR), Math.abs(w-wR) ];
var i = arr.indexOf(Math.max(...arr));

После того, как найдена координата задачи, она закруглена в другом направлении. Окончательные (x, y) затем вычисляются по округленному/скорректированному (u, v, w).

nearestHex = function(x,y){

  u = (2/3)*x;
  v = -(1/3)*x + (1/2)*y;
  w = -(1/3)*x - (1/2)*y;

  uR = Math.round(u);
  vR = Math.round(v);
  wR = Math.round(w);

  if(uR+vR+wR !== 0){
    arr = [ Math.abs(u-uR), Math.abs(v-vR), Math.abs(w-wR) ];
    var i = arr.indexOf(Math.max(...arr));

    switch(i){
      case 0:
        Math.round(u)===Math.floor(u) ? u = Math.ceil(u) : u = Math.floor(u);
        v = vR; w = wR;
        break;

      case 1:
        Math.round(v)===Math.floor(v) ? v = Math.ceil(v) : v = Math.floor(v);
        u = uR; w = wR;
        break;

      case 2:
        Math.round(w)===Math.floor(w) ? w = Math.ceil(w) : w = Math.floor(w);
        u = uR; v = vR;
        break;
    }
  }

  return {x: (3/2)*u, y: v-w};

}

Ответ 4

Это дополнение к ответу СебастьянТрой. Я бы оставил его в качестве комментария, но пока еще недостаточно репутации.

Если вы хотите реализовать осевую систему координат, как описано здесь: http://www.redblobgames.com/grids/hexagons/

Вы можете внести небольшую модификацию в код.

Вместо

// Is the row an odd number?
if (rowIsOdd)// Yes: Offset x to match the indent of the row
    column = (int) ((x - halfWidth) / gridWidth);
else// No: Calculate normally
    column = (int) (x / gridWidth);

используйте этот

float columnOffset = row * halfWidth;
column = (int)(x + columnOffset)/gridWidth; //switch + to - to align the grid the other way

Это заставит координату (0, 2) находиться в том же диагональном столбце, что и (0, 0) и (0, 1), а не быть непосредственно ниже (0, 0).

Ответ 5

У меня был другой взгляд на http://playtechs.blogspot.co.uk/2007/04/hex-grids.html, и он очень аккуратен математически.

Однако подход Себастьяна, похоже, прервет погоню и выполнит задачу в удивительно малых строках кода.

Если вы прочитаете раздел комментариев, вы можете обнаружить, что кто-то написал реализацию Python на http://gist.github.com/583180

Я отпишу, что здесь для потомков:

# copyright 2010 Eric Gradman
# free to use for any purpose, with or without attribution
# from an algorithm by James McNeill at
# http://playtechs.blogspot.com/2007/04/hex-grids.html

# the center of hex (0,0) is located at cartesian coordinates (0,0)

import numpy as np

# R ~ center of hex to edge
# S ~ edge length, also center to vertex
# T ~ "height of triangle"

real_R = 75. # in my application, a hex is 2*75 pixels wide
R = 2.
S = 2.*R/np.sqrt(3.)
T = S/2.
SCALE = real_R/R

# XM*X = I
# XM = Xinv
X = np.array([
    [ 0, R],
    [-S, S/2.]
])
XM = np.array([
    [1./(2.*R),  -1./S],
    [1./R,        0.  ]
])
# YM*Y = I
# YM = Yinv
Y = np.array([
    [R,    -R],
    [S/2.,  S/2.]
])
YM = np.array([
    [ 1./(2.*R), 1./S],
    [-1./(2.*R), 1./S],
])

def cartesian2hex(cp):
    """convert cartesian point cp to hex coord hp"""
    cp = np.multiply(cp, 1./SCALE)
    Mi = np.floor(np.dot(XM, cp))
    xi, yi = Mi
    i = np.floor((xi+yi+2.)/3.)

    Mj = np.floor(np.dot(YM, cp))
    xj, yj = Mj
    j = np.floor((xj+yj+2.)/3.)

    hp = i,j
    return hp

def hex2cartesian(hp):
    """convert hex center coordinate hp to cartesian centerpoint cp"""
    i,j = hp
    cp = np.array([
        i*(2*R) + j*R,
        j*(S+T)
    ])
    cp = np.multiply(cp, SCALE)

return cp

Ответ 6

Я не знаю, поможет ли это кому-либо, но я придумал гораздо более простое решение. Когда я создаю свой Hexagon im, просто давая им среднюю точку, и, найдя ближайшую среднюю точку с помощью мышиной координаты, я могу найти, как один из них!