さまざまなおもちゃ、通常の六角形で舗装された平面上を移動するキャラクターを観察した後、私は質問に夢中になりました-そのような平面で線がどのように見えるべきか？ 実際、六角形Aから六角形Bへのキャラクターの最適な移動のタスク（平面上に障害物がないことを意味し、六角形の最小数で発生するように最適な移動を意味します）は、さまざまな方法で解決でき、ルートもユニークではありませんただし、正方形で覆われた平面上では。 しかし、Bresenhamアルゴリズムに従って構築された画像はラインセグメントに近いため、ルートをラインセグメントに近づけたいと思います。同時に、実装はかなり透明でシンプルでなければなりません。
実数のフィールドで計算を使用すると、次のアプローチが最も透過的になります。開始と終了の中心の座標があると仮定します。 線の一部がすでに作成されていると仮定します（たとえば、最初の六角形の「ピクセル」が設定されています）。 最後に構築されたピクセルから、その近傍（他の6つの六角形がある）でその六角形を選択する必要があり、その中心から構築中のセグメントの開始と終了までの距離の合計は最小です（実際には、2つまたは2つ低いケースを考慮するのに十分です） 、またはいくつかの条件に応じて、右下と右下に表示されます。これについては以下で説明します）。 アルゴリズム自体は、実数の分野での計算、平方根の計算を必要としますが、これは本当にしたくないです。
まず、ラスターの各「ピクセル」を一意に識別する座標系を選択すると便利です。 いくつかのオプションを検討した後、私は最も単純なものに決めました。
各六角形には、座標xとyが含まれます。便宜上、「ラスター」と呼び、「幾何」と呼ばれる点の座標と区別します。
問題を解決する過程で、それは2つのケースに分けられました。解決の過程で私が受け取った分離の条件。 以下でこれが起こる理由が明らかになりますが、今のところは条件を示します。 セグメントの開始の座標を（0、0）として、終了を（x、y）としてとると、条件x≥[y / 2]で、したがって、x <[y / 2]の場合、最初のケースが取得されます。部品全体のキャプチャを示します。 これらの条件は、モザイクを2つの等しくないセクションに分割し、その境界は次のとおりです。
最初のケース：x≥[y / 2]
最初に、最初のケースの解決策を示します。これはおそらく最も明白です。 「額に」ブレゼンハムアルゴリズムを適用しても、望ましい効果が得られないことは驚くべきことです。 実際、その中でxは各反復で増加し、yはエラー値がオーバーフローするときに増加します。 しかし、偶数行から奇数行に切り替えると、xとyの同時成長によりギャップが生じます。 たとえば、六角形（2、2）の両方の座標を1つ増やすと、六角形（3、3）が得られます。これは、上の図からわかるように、最初の共通の境界線を持っています。 しかし、（2、2）から（2、3）のポイントに移動し、（3、3）に移動した場合、ギャップはありません。 モザイクは次のように変形できます。
また、一時的に座標を変更します。
最後の図は、分割セグメントがBresenhamアルゴリズムのオクテット境界を正確に通過することを示しています。したがって、この状況では、アルゴリズムは既に適用可能になっています。 さらに、アルゴリズムの反復中の次の各ポイントは、元のモザイクの前のポイントに隣接しています。 したがって、座標が変更された変形モザイクにBresenhamアルゴリズムを適用し、すべてを元の場所に戻すと、六角形ラスタに直線が得られます。 下の写真は、アルゴリズムのいくつかの図です。
線の長さ（構築に関係する六角形の数）は、x + [（y + 1）/ 2] + 1です。角括弧は、全体が同じです。 幾何学的には、これは水平線の数に偶数行から奇数行に切り替えた数を加えたものです（一番上の行は番号0なので、偶数です）。
2番目のケース：x <[y / 2]
2番目の場合、行の長さがy + 1を超えてはならないことは明らかです。従来のBresenhamアルゴリズムとは異なり、この場合は最初の対称ではありませんが、手順は似ています-上記の変形を実行して線を描画しますが、別のオクテットの規則に従って、 y軸に沿って発生します。
Javaコード
public final class Line implements Iterable<Point> { private final Point begin; private final int dx; private final int dy; private final int sx; private final int sy; public Line(final Point begin, final Point end) { this.begin = begin; int dx = end.x - begin.x; int dy = end.y - begin.y; if (dx < 0) { dx = -dx; sx = -1; } else { sx = 1; } if (dy < 0) { dy = -dy; sy = -1; } else { sy = 1; } this.dx = dx + (dy + 1) / 2; this.dy = dy; } @Override public Iterator<Point> iterator() { return dx > dy ? new LineIterator1() : new LineIterator2(); } private final class LineIterator1 implements Iterator<Point> { private int x = 0; private int y = 0; private int error = 0; @Override public boolean hasNext() { return x <= dx; } @Override public Point next() { if (x > dx) return null; Point point = new Point(begin.x + (x - (y + 1) / 2) * sx, begin.y + y * sy); x++; if (x <= dx) { error += dy; if (2 * error >= dx) { y++; error -= dx; } } return point; } @Override public void remove() { throw new UnsupportedOperationException(); } } private final class LineIterator2 implements Iterator<Point> { private int x = 0; private int y = 0; private int error = 0; @Override public boolean hasNext() { return y <= dy; } @Override public Point next() { if (y > dy) return null; Point point = new Point(begin.x + (x - (y + 1) / 2) * sx, begin.y + y * sy); y++; if (y <= dy) { error = error + dx; if (2 * error >= dy) { error -= dy; x++; } } return point; } @Override public void remove() { throw new UnsupportedOperationException(); } } }
クラスポイント
public final class Point { public final int x; public final int y; public Point(final int x, final int y) { this.x = x; this.y = y; } }
繰り返しになりますが、これは自転車の発明であると認めます。この場合にかかる時間についておIび申し上げます。