13

我有一个六边形网格：

六边形网格

使用模板类型坐标 T。如何计算两个六边形之间的距离？

例如：

距离（（3,3），（5,5））= 3

距离（（1,2），（1,4））= 2

4

7 回答 7

8

首先应用变换 (y, x) |-> (u, v) = (x, y + floor(x / 2))。

现在面部邻接看起来像

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

设点为 (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)
于 2013-04-10T13:14:59.630 回答
4

在我看到我的一篇博客文章后在这里发帖，这里的另一个答案获得了推荐流量。它被否决了，这是正确的，因为它不正确；但这是对我帖子中提出的解决方案的错误描述。

您的“波浪形”轴 - 就您的 x 坐标每隔一行移位而言 - 将导致您在尝试确定距离或稍后进行寻路时遇到各种头痛，如果这是为了某种游戏的话。六边形网格自然适合三个轴，六边形的“方形”网格最好有一些负坐标，这样可以更简单地计算距离。

这是一个映射出 (x,y) 的网格，x 向右下方增加，y 向上增加。

两个坐标和三个轴重叠的六边形网格

通过理顺事情，第三个轴变得显而易见。

三坐标三轴叠加的六边形网格

巧妙的是，三个坐标相互关联——所有三个坐标的总和始终为 0。

有了这样一个一致的坐标系，任意两个六边形之间的原子距离就是三个坐标之间的最大变化，或者：

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

很简单。但是你必须先修复你的网格！

于 2013-04-17T14:33:16.660 回答
2

这是 a 所做的：

以一个单元格为中心（如果选择 很容易看出0,0），远处的单元格dY形成一个大六边形（带有“半径” dY）。这个六边形的一个顶点是(dY2,dY).If dX<=dY2the path is a zig-zag to the ram of the big hexagon with a distance 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
于 2013-04-10T11:07:50.973 回答
1

首先，您需要将坐标转换为“数学”坐标系。每两列在 y 方向上移动坐标 1 个单位。“数学”坐标 (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'=st 和 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);
}
于 2013-04-10T12:35:09.563 回答
1

距离的正确显式公式以及您的坐标系由下式给出：

d((x1,y1),(x2,y2)) = max( abs(x1 - x2), 
                          abs((y1 + floor(x1/2)) - (y2 + floor(x2/2)))
                        )
于 2013-04-10T08:46:16.447 回答
0

(odd-r)(没有 z，只有 x,y)

我在上面的实现中看到了一些问题。抱歉，我没有全部检查，但是。但也许我的解决方案会对某人有所帮助，也许这是一个糟糕且未优化的解决方案。

主要思想是先对角线，然后是水平线。但为此我们需要注意：

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's 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;
}
于 2018-12-06T10:44:03.323 回答
-3

我相信您寻求的答案是：

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

您可以在这里找到关于六边形网格坐标系/距离的一个很好的解释：

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

于 2013-04-10T07:54:58.310 回答