logo标签列表

六边形网格上两个六边形之间的距离

c++algorithmdistancehexagonal-tiles
14

我有一个六边形网格：

hexagon grid

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

例如：

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

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

4
@OGH，在六边形网格中没有步距的公式，或者至少不像你所说的那样广为人知。 - Ivaylo Strandjev
1
https://dev59.com/AG445IYBdhLWcg3wAFq0 - QuantumKarl
@QuantumKarl，我尝试过了。对于我的网格不起作用。 - zodiac
你的单元格排序方式使得问题变得极为困难。以(2,2)为例，(3,3)的距离为1，而(1,1)的距离为2。这个网格使得坐标非常不对称。你有没有考虑选择一个更好的坐标系统呢？例如，向上移动总是将y加1，向右下移动总是将x加1？这样，距离公式就变得非常简单了。 - Shahbaz
@Shahbaz，不行，我做不出来。我在那个坐标系下面遇到了问题。 - zodiac
显示剩余5条评论
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)
4
在看到我的博客文章从这里得到了推荐流量后，我在这里发帖。它被投票下降了，这是正确的，因为它是不正确的；但它误解了我的帖子中提出的解决方案。
你的“波浪形”轴——就你的x坐标每隔一行就位移一次而言——如果这是某种游戏，将会给你在以后尝试确定距离或者进行路径规划时带来各种头痛。六边形网格自然倾向于三个轴，而一个六边形的“正方形”网格将具有一些负坐标，这允许更简单的距离数学计算。
这是一个带有(x,y)映射的网格，其中x向右下方增加，y向上增加。
通过整理，第三个轴变得很明显。
有趣的是，这三个坐标相互关联——所有三个坐标的总和始终为0。
由于这样一个一致的坐标系，任何两个六边形之间的原子距离都是三个坐标之间最大的变化，即：
请参见以下内容：
d = max( abs(x1 - x2), abs(y1 -y2), abs( (-x1 + -y1) - (-x2 + -y2) )

相当简单。但是您必须先修复您的网格！
2

使用您的坐标系统，正确的距离显式公式如下：

d((x1,y1),(x2,y2)) = max( abs(x1 - x2), 
                          abs((y1 + floor(x1/2)) - (y2 + floor(x2/2)))
                        )
@Serdalis，打错了，我的意思是用“-”代替“，”。 - flolo
它似乎比实际答案少返回1。（来自我的回答中Armin的评论示例） - Serdalis
@Serdalis：我试过了：dist((0,0),(5,4)) = max(5, abs((0 + 0/2) - (5 + 4/2)) = max(5,7) = 7; dist((3,3), (5,4)) = max (2, abs((3+3/2) - (5 + 4/2)) = max(2, 3) = 3。看起来没问题。 - flolo
啊，你又打错字了，“(y2 + floor(x2/2)” 应该是 “(x2 + floor(y2/2)” 。不过工作做得很好。 - Serdalis
@flolo 不起作用。尝试得很好，不过假设向右是x，向下是y的方法在尝试向右上移动时会出问题。 - user1944441
1
@Serdalis，d((0,2), (5,1)) = 4 != 5。这是因为 d = max(abs(y1 - y2), abs((x1 + floor(y1 / 2))) - (x2 + floor(y2 / 2)))。当我使用 d = max(abs(x1 - x2), ...) 时，d((1,0), (0,2)) = 1 != 2。 - zodiac
2

以下是我的做法：

以一个单元格为中心（如果选择0,0，则更容易理解），距离为dY的单元格形成一个大六边形（“半径”为dY）。这个六边形的一个顶点是(dY2,dY)。如果dX<=dY2，路径是一条蜿蜒到达大六边形边缘的路径，距离为dY。否则，路径是从顶点开始的“对角线”，加上从顶点到第二个单元格的垂直路径，需要添加dX-dY2个单元格。

可能更易理解的描述方式：

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
@zodiac。使用我的公式d=1，从图中也可以看出d=1。那么d=2在哪里？啊，好的，你在我最后一次编辑之前已经读过了。抱歉。简化公式中有一个错误，但在“原始”公式中是正确的。 - qPCR4vir
d((2,1), (3,1)): dx = 1, dy = 0, dy2 = 0，结果为d = 0 != 1。 - zodiac
@zodiac：你是对的！简化公式让我遇到了很多问题。但是“原始”的依然正确！ - qPCR4vir
d((3,2), (0,1)) = 3 != 4 - zodiac
d((3,3), (0,0)) = 6 != 4, 但是 d((0,0), (3,3)) = 4。为什么你只用了 y1 而没有用 y2？ - zodiac
1

首先，您需要将您的坐标转换为“数学”坐标系。每两列，您需要将坐标在y方向上移动1个单位。可以通过以下方式从您的坐标(u,v)计算出“数学”坐标(s,t):

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);
}
同样的错误。dist((2,1), (1,2))：dist1 = abs(2 - 1) + abs(1 - 2) = 2，dist2 = abs((2 - 1) - (1 - 2)) + abs(1 - 2) = abs(2) + abs(-1) = 3，结果是 2 != 1。 - zodiac
啊，现在我明白了，你没有使用数学意义上的坐标系。你需要先将你的坐标转换为数学坐标系。我会尝试更新我的答案。 - MadScientist
0

(奇数-r)(没有z，只有x，y)

我看到了一些实现上的问题。抱歉，我没有全部检查，但也许我的解决方案对某些人有帮助，也可能是一个不好的、未经优化的解决方案。

主要思路是按对角线和水平方向移动。但为此我们需要注意：

1）例如，我们有0；3（x1=0；y1=3），要到达y2=6，我们可以在每个点上处理6步，即：0-左边界，6-右边界

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;
}
-3
1
不行。对于dist((2,0), (5,2)) = 4 != max(3, 2) = 3无效。 - zodiac
1
这个方法无法确定其中一个示例的距离，即 dist((3,3), (5,5)) = 3。 - tafa
2
这个失败了，因为他们使用了不同的坐标系。 - flolo
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接