5

帮助找到在六角场上通过螺旋创建细胞的算法。

看图片：

替代文字

让我们想象一个无量纲的二维数组。X 轴是蓝线，Y 是水平线，螺旋线是红色。

我需要从中心点 x0y0 到点 N 通过螺旋添加单元格

请告诉我解决问题的方法。谢谢！

4

6 回答 6

7

我建议稍微更改单元格编号，以便在您向下和向右（或向上和向左）移动时 X 保持不变。然后像下面这样的简单算法应该可以工作：

  int x=0, y=0;   
  add(x, y); // add the first cell
  int N=1 
  for( int N=1; <some condition>; ++N ) {
    for(int i=0; i<N; ++i) add(++x, y);  // move right
    for(int i=0; i<N-1; ++i) add(x, ++y); // move down right. Note N-1
    for(int i=0; i<N; ++i) add(--x, ++y); // move down left
    for(int i=0; i<N; ++i) add(--x, y); // move left
    for(int i=0; i<N; ++i) add(x, --y); // move up left
    for(int i=0; i<N; ++i) add(++x, --y); // move up right
  }

这会产生如下点：

生成点图

转换后我们得到：

将生成的点转换为六角网格

于 2010-01-26T23:28:03.387 回答
1

在此处输入图像描述 （圆圈的直径为 1）

这是一个获取位置的函数i：

  void getHexPosition( int i, ref double x, ref double y )
  {
     if ( i == 0 ) { x = y = 0; return; }

     int layer = (int) Math.Round( Math.Sqrt( i/3.0 ) );

     int firstIdxInLayer = 3*layer*(layer-1) + 1;
     int side = (i - firstIdxInLayer) / layer; // note: this is integer division
     int idx  = (i - firstIdxInLayer) % layer;                  
     x =  layer * Math.Cos( (side - 1) * Math.PI/3 ) + (idx + 1) * Math.Cos( (side + 1) * Math.PI/3 );
     y = -layer * Math.Sin( (side - 1) * Math.PI/3 ) - (idx + 1) * Math.Sin( (side + 1) * Math.PI/3 );
  }

Math.Sqrt(.75)通过给出缩放结果

在此处输入图像描述

如果您对 shura 的回答中的倾斜坐标感兴趣：

  int[] h = { 1, 1, 0, -1, -1, 0, 1, 1, 0 };
  void getHexSkewedPosition( int i, ref int hx, ref int hy )
  {
     if ( i == 0 ) { hx = hy = 0; return; }

     int layer = (int) Math.Round( Math.Sqrt( i/3.0 ) );

     int firstIdxInLayer = 3*layer*(layer-1) + 1;
     int side = (i - firstIdxInLayer) / layer;
     int idx  = (i - firstIdxInLayer) % layer;

     hx = layer*h[side+0] + (idx+1) * h[side+2];
     hy = layer*h[side+1] + (idx+1) * h[side+3];
  }

  void getHexPosition( int i, ref double hx, ref double hy )
  {
     int x = 0, y = 0;
     getHexSkewedPosition( i, ref x, ref y );
     hx = x - y * .5;
     hy = y * Math.Sqrt( .75 );
  }
于 2016-09-29T21:12:52.653 回答
0

想象一下，您有一个带有正方形而不是六边形的普通网格，使用该网格创建螺旋形，然后通过将每个奇数 y 向左移动 m 个像素来绘制它，这会给您带来这种效果。

于 2010-01-26T21:06:40.413 回答
0

您可以一次选择一个格子，方法是使用适当的评分函数来选择六个尚未选择的相邻格子中最好的一个，以选择上一轮选择的格子。我认为一个有效的得分函数是选择最接近（0,0）（强制一次选择一个“外壳”中的六角形），通过选择最接近（1,0）来打破关系（强制一致的螺旋方向在新外壳中）。可以使用以下函数计算六角网格中的距离：

double grid_distance(int dx, int dy) {
  double real_dx = dx + y/2.0;
  double real_dy = dy * sqrt(3)/2.0;
  return sqrt(real_dx * real_dx + real_dy * real_dy);
}
于 2010-01-26T22:44:58.027 回答
0

你可以通过模拟方向来做到这一点。如果您的方向是“0 点向上”，则顺时针方向递增 1，应执行以下操作：

选择一个中心单元格。
选择第二个单元格（最好在方向 0）。
将方向设置为 2。

虽然您有更多要标记的单元格：
  如果 (direction+1)%6 中的单元格是空闲的：
    设置方向 = (方向+1)%6
  将当前单元格标记为已使用
  按方向前往单元格
于 2010-01-27T07:34:31.833 回答
0

我喜欢@shura 解决问题的方式，但无法让那个确切的算法起作用。此外，我使用的是 2x1 六边形间距（其中 x 单元格间隔 2，并且每个其他 x 项都被隐藏）。

这是我的工作（尽管在 JavaScript 中）：

    //Hexagon spiral algorithm, modified from 
    for(var n=1; n<=rings; ++n) {
        x+=2; add(x, y);
        for(var i=0; i<n-1; ++i) add(++x,++y); // move down right. Note N-1
        for(var i=0; i<n; ++i) add(--x,++y); // move down left
        for(var i=0; i<n; ++i) { x-=2; add(x, y); } // move left
        for(var i=0; i<n; ++i) add(--x,--y); // move up left
        for(var i=0; i<n; ++i) add(++x, --y); // move up right
        for(var i=0; i<n; ++i) { x+=2; add(x, y); }  // move right
    }
于 2015-11-16T00:34:20.250 回答