Расстояние между двумя шестиугольниками по шестиугольной сетке

У меня есть шестиугольная сетка:

с типом типа шаблона Т. Как я могу рассчитать расстояние между двумя шестиугольниками?

Например:

dist ((3,3), (5,5)) = 3

dist ((1,2), (1,4)) = 2

Ответ 1

Сначала примените преобразование (y, x) | → (u, v) = (x, y + floor (x/2)).

Теперь лицевая смежность выглядит как

 0 1 2 3
0*-*-*-*
 |\|\|\|
1*-*-*-*
 |\|\|\|
2*-*-*-*

Пусть точки be (u1, v1) и (u2, v2). Пусть du = u2 - u1 и dv = v2 - v1. Расстояние

if du and dv have the same sign: max(|du|, |dv|), by using the diagonals
if du and dv have different signs: |du| + |dv|, because the diagonals are unproductive

В Python:

def dist(p1, p2):
    y1, x1 = p1
    y2, x2 = p2
    du = x2 - x1
    dv = (y2 + x2 // 2) - (y1 + x1 // 2)
    return max(abs(du), abs(dv)) if ((du >= 0 and dv >= 0) or (du < 0 and dv < 0)) else abs(du) + abs(dv)

Ответ 2

Правильная явная формула для расстояния с вашей системой координат задается:

d((x1,y1),(x2,y2)) = max( abs(x1 - x2), 
                          abs((y1 + floor(x1/2)) - (y2 + floor(x2/2)))
                        )

Ответ 3

Вот что сделал:

Взятие одной ячейки в центр (легко видеть, выберете 0,0), ячейки на расстоянии dY образуют большой шестиугольник (с "радиусом" dY). Одна вершина этого шестиугольника имеет значение (dY2,dY). Если dX<=dY2, путь является зигзагом к овалу большого шестиугольника с расстоянием dY. Если нет, то путь - это "диагональ" к вершинам, плюс вертикальный путь от вершин ко второй ячейке, с добавлением ячеек dX-dY2.

Может быть, лучше понять: led:

dX = abs(x1 - x2);
dY = abs(y1 - y2);
dY2= floor((abs(y1 - y2) +  (y1+1)%2  ) / 2);

Тогда:

 d = d((x1,y1),(x2,y2)) 
   = dX < dY2 ? dY : dY + dX-dY2 + y1%2 * dY%2

Ответ 4

Сначала вам нужно преобразовать ваши координаты в "математическую" систему координат. Каждые два столбца вы меняете координаты на 1 единицу в направлении y. "Математические" координаты (s, t) можно вычислить из ваших координат (u, v) следующим образом:

s = u + floor (v/2) t = v

Если вы назовете одну сторону шестиугольников a, базисными векторами вашей системы координат являются (0, -sqrt (3) a) и (3a/2, sqrt (3) a/2). Чтобы найти минимальное расстояние между вашими точками, вам нужно вычислить расстояние в манхаттане в вашей системе координат, которое задается | s1-s2 | + | t1-t2 | где s и t - координаты в вашей системе. Расстояние на Манхэттене охватывает только ходьбу в направлении ваших векторов-оснований, поэтому она охватывает только такие ходы: |/но не идет так: | \. Вам необходимо преобразовать ваши векторы в другую систему координат с базисными векторами (0, -sqrt (3) a) и (3a/2, -sqrt (3) a/2). Координаты в этой системе задаются s '= s-t и t' = t, поэтому расстояние в манхэттене в этой системе координат задается формулой | s1'-s2 '| + | t1'-t2' |. Расстояние, которое вы ищете, - это минимум двух расчетных расстояний на Манхэттене. Ваш код будет выглядеть так:

struct point
{
  int u;
  int v;
}

int dist(point const & p, point const & q)
{
  int const ps = p.u + (p.v / 2); // integer division!
  int const pt = p.v;
  int const qs = q.u + (q.v / 2);
  int const qt = q.v;
  int const dist1 = abs(ps - qs) + abs(pt - qt);
  int const dist2 = abs((ps - pt) - (qs - qt)) + abs(pt - qt);
  return std::min(dist1, dist2);
}

Ответ 5

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

Ваша "короткая" ось - с точки зрения вашей координаты x, перемещаемой каждой другой строкой, - приведет вас к разным головным болям, пытаясь определить расстояния или сделать обратный путь позже, если это для какой-либо игры, Шестигранные сетки естественно поддаются трем осям, а сетка шестиугольников с квадратом с квадратом оптимально имеет некоторые отрицательные координаты, что позволяет упростить математику на расстояниях.

Здесь отображается сетка с (x, y), причем x возрастает до нижнего правого, а y увеличивается вверх.

Выправляя вещи, становится очевидной третья ось.

В этом отношении аккуратно, что три координаты взаимосвязаны - сумма всех трех координат всегда будет равна 0.

При такой согласованной системе координат атомное расстояние между любыми двумя гексами является наибольшим изменением между тремя координатами или:

d = max( abs(x1 - x2), abs(y1 -y2), abs( (-x1 + -y1) - (-x2 + -y2) )

Довольно просто. Но сначала вы должны исправить свою сетку!

Ответ 6

(Нечетно-г)

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

Основная идея - по диагонали, а затем по горизонтали. Но для этого нужно отметить:

1) Например, мы имеем 0; 3 (x1 = 0; y1 = 3), и чтобы перейти к y2 = 6, мы можем обрабатывать в пределах 6 шагов к каждой точке (0-6; 6) так: 0-left_border, 6 -right_border

2) Рассчитайте некоторые смещения

#include <iostream>
#include <cmath>

int main()
{
    //while(true){
    int x1,y1,x2,y2;
    std::cin>>x1>>y1;
    std::cin>>x2>>y2;
    int diff_y=y2-y1; //only up-> bottom no need abs
    int left_x,right_x;
    int path;

    if( y1>y2 ) { // if Down->Up  then swap
        int temp_y=y1;
        y1=y2;
        y2=temp_y;
        //
        int temp_x=x1;
        x1=x2;
        x2=temp_x;
    }                   // so now we have Up->Down

        // Note that it odd-r horizontal layout
        //OF - Offset Line  (y%2==1)
        //NOF -Not Offset Line (y%2==0)
    if( y1%2==1 && y2%2==0 ){ //OF ->NOF
        left_x = x1 - ( (y2 - y1 + 1)/2 -1 );  //UP->DOWN no need abs
        right_x = x1 + (y2 - y1 + 1)/2;  //UP->DOWN no need abs
    }
    else if( y1%2==0 && y2%2==1 ){ // OF->NOF
        left_x = x1 - (y2 - y1 + 1)/2;  //UP->DOWN no need abs
        right_x = x1 + ( (y2 - y1 + 1)/2 -1 );  //UP->DOWN no need abs

    }
    else{
        left_x = x1 - (y2 - y1 + 1)/2;  //UP->DOWN no need abs
        right_x = x1 + (y2 - y1 + 1)/2;  //UP->DOWN no need abs
    }
    /////////////////////////////////////////////////////////////
    if( x2>=left_x && x2<=right_x ){
        path = y2 - y1;
    }
    else {
        int min_1 = std::abs( left_x - x2 );
        int min_2 = std::abs( right_x - x2 );
        path = y2 - y1 + std::min(min_1, min_2);
    }
    std::cout<<"Path: "<<path<<"\n\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\n";
    //}

    return 0;
}

Ответ 7

Я считаю, что ваш ответ:

d((x1,y1),(x2,y2))=max(abs(x1-x2),abs(y1-y2));

Здесь вы можете найти хорошее объяснение по шестиугольной системе координат/расстояния:

http://keekerdc.com/2011/03/hexagon-grids-coordinate-systems-and-distance-calculations/