algorithm - Hexagonal Grids、ポイントがどの六角形にあるかをどのように見つけますか?

Question

六角形の行と列で構成されたマップがあります

これは私が使用している 16 進マップの実際の画像ではありませんが、同じサイズと形状の六角形を使用しています

ユーザーがクリックしたときに、マウスがどちらの上にあるかを判断できるようにする必要があります。

各 Hexagon は「Tile」クラスのインスタンスによって表されますが、これは場所固有のデータやポリゴンさえも保持しないため、基本的に特定の六角形がどこにあるかを知る唯一の方法は、その位置を知ることです。 2D 配列。

以前に正方形のグリッドを使用したことがあり、ピクセルも正方形であるため、どの正方形が選択されているかを比較的簡単に把握できました。

// Example where each square is 10 by 10 pixels:
private void getClickedSquare(MouseEvent me)
{
    int mouseX = me.getX(); // e.g. 25
    int mouseY = me.getY(); // e.g. 70

    int squareX = (int)(mouseX / 10); // in this case 2
    int squareY = (int)(mouseY / 10); // in this case 7

    // Then to access the tile I would do
    map.squares[squareX][squareY].whatever();
}

しかし、Hexagons をどこから始めればよいかさえわかりません。経験のある人はいますか?

ポリゴン (Java) は使用できません。画面上でマップを移動し、サイズを大きくすると、フレームごとに膨大な量のポリゴンを更新する際に問題が発生するためです。ただし、ポイントがマップのタイルのポリゴンに含まれているかどうかを確認することはできます!

現時点では、表示されている六角形は単なる BufferedImages です。

さらに詳しい情報を知りたい場合は、お問い合わせください。お時間をいただきありがとうございます:D

Answer 1

(更新: よりわかりやすく効率的にするためにコードをリファクタリング) (更新: 回答の長さの短縮、コードのバグの修正、画像の品質の向上)

この画像は、六角形のグリッドの左上隅を示しており、青い正方形のグリッドが重ねられています。ポイントがどの正方形の内側にあるかを見つけるのは簡単で、これにより、どの六角形も大まかに近似できます。六角形の白い部分は、正方形と六角形のグリッドが同じ座標を共有する場所を示し、六角形の灰色の部分はそれらが共有しない場所を示します。

解決策は、ポイントがどのボックスにあるかを見つけ、ポイントが三角形のいずれかにあるかどうかを確認し、必要に応じて答えを修正するだけです。

private final Hexagon getSelectedHexagon(int x, int y)
{
    // Find the row and column of the box that the point falls in.
    int row = (int) (y / gridHeight);
    int column;

    boolean rowIsOdd = row % 2 == 1;

    // Is the row an odd number?
    if (rowIsOdd)// Yes: Offset x to match the indent of the row
        column = (int) ((x - halfWidth) / gridWidth);
    else// No: Calculate normally
        column = (int) (x / gridWidth);

この時点で、ポイントが入っているボックスの行と列があります。次に、ポイントが上の六角形のいずれかにあるかどうかを確認するために、六角形の 2 つの上端に対してポイントをテストする必要があります。

    // Work out the position of the point relative to the box it is in
    double relY = y - (row * gridHeight);
    double relX;

    if (rowIsOdd)
        relX = (x - (column * gridWidth)) - halfWidth;
    else
        relX = x - (column * gridWidth);

相対座標があると、次のステップが簡単になります。

上の画像のように、ポイントのyが> mx + cの場合、ポイントが線の上にあることがわかります。この場合、現在の行と列の左上にある六角形です。Java の座標系の y は画面の左上に 0 から始まることに注意してください。数学では通常のように左下ではなく、左端に負の勾配が使用され、右端に正の勾配が使用されます。

    // Work out if the point is above either of the hexagon's top edges
    if (relY < (-m * relX) + c) // LEFT edge
        {
            row--;
            if (!rowIsOdd)
                column--;
        }
    else if (relY < (m * relX) - c) // RIGHT edge
        {
            row--;
            if (rowIsOdd)
                column++;
        }

    return hexagons[column][row];
}

---

上記の例で使用されている変数の簡単な説明:

m はグラデーションなので、m = c / halfWidth

Answer 2

編集:この質問は最初に思ったよりも難しいです。いくつかの作業で回答を書き直しますが、ソリューションパスが他の回答の改善であるかどうかはわかりません。

質問は言い換えることができます: 任意の x,y が与えられたとき、中心が x,y に最も近い六角形を見つけます

つまり、dist_squared( Hex[n].center, (x,y) ) を n で最小化します (2 乗は、CPU を節約する平方根について心配する必要がないことを意味します)

ただし、最初にチェックする六角形の数を絞り込む必要があります。次の方法で最大 5 つまで絞り込むことができます。

したがって、最初のステップはUV空間でポイント（x、y）を表現することです。つまり、（x、y）=ラムダU +ミューVなので、UV空間で=（ラムダ、ミュー）

これは単なる 2D マトリックス変換です (線形変換を理解していない場合はhttp://playtechs.blogspot.co.uk/2007/04/hex-grids.htmlが役立つ場合があります)。

ポイント (ラムダ、ミュー) が与えられた場合、両方を最も近い整数に丸めると、次のようになります。

緑の広場内のどこでも (2,1) にマップされます

したがって、その緑色の四角形内のほとんどの点は正しいでしょう。つまり、それらは六角形 (2,1) にあります。

ただし、一部のポイントは六角形 # (2,2) を返す必要があります。つまり、次のようになります。

同様に、一部は六角形 # (3,1) を返す必要があります。そして、その緑色の平行四辺形の反対側の角には、さらに 2 つの領域があります。

要約すると、int(lambda,mu) = (p,q) の場合、おそらく六角形 (p,q) の内側にいますが、六角形 (p+1,q)、(p,q+1) の内側にもある可能性があります。 、(p-1,q) または (p,q-1)

これらのどれが当てはまるかを判断するいくつかの方法。最も簡単な方法は、これら 5 つの六角形すべての中心を元の座標系に変換し、ポイントに最も近いものを見つけることです。

しかし、距離チェックを行わない時間の最大 50%、距離チェックを 1 回行う時間の最大 25%、距離チェックを 2 回行う残りの時間の約 25% に絞り込むことができます (私は推測しています)。各チェックが機能する領域を見ることによる数字）：

p,q = int(lambda,mu)

if lambda * mu < 0.0:
    // opposite signs, so we are guaranteed to be inside hexagon (p,q)
    // look at the picture to understand why; we will be in the green regions
    outPQ = p,q

else:
    // circle check
    distSquared = dist2( Hex2Rect(p,q), Hex2Rect(lambda, mu) )

    if distSquared < .5^2:
        // inside circle, so guaranteed inside hexagon (p,q)
        outPQ = p,q

    else:
        if lambda > 0.0:
            candHex = (lambda>mu) ? (p+1,q): (p,q+1)
        else:
            candHex = (lambda<mu) ? (p-1,q) : (p,q-1)

最後のテストは次のように整理できます。

     else:
        // same sign, but which end of the parallelogram are we?
        sign = (lambda<0) ? -1 : +1
        candHex = ( abs(lambda) > abs(mu) ) ? (p+sign,q) : (p,q+sign)

これで、別の可能な六角形に絞り込んだので、どちらが近いかを見つける必要があります。

        dist2_cand = dist2( Hex2Rect(lambda, mu), Hex2Rect(candHex) )

        outPQ = ( distSquared < dist2_cand ) ? (p,q) : candHex

Dist2_hexSpace(A,B) 関数は、さらに整理します。

Answer 3

私は @pi の回答https://stackoverflow.com/a/23370350/5776618を見て始め、UVW 空間 (2D、軸方向、UV -スペース）。

次の方程式は (x,y) => (u,v,w) をマップします。

u = (2/3)*x;
v = -(1/3)*x + (1/2)*y;
w = -(1/3)*x - (1/2)*y;

次に、u、v、および wを最も近い整数に丸め、 x,yに変換するのと同じくらい簡単です。しかし、大きな落とし穴が…。

上記の回答では、UV 空間での丸めには、正しくマッピングされない領域がいくつかあることに注意してください。

これは、キューブ座標を使用する場合にも発生します。

オレンジ色の三角形の領域は、六角形の中心から 0.5 単位以上離れており、丸めると中心から離れて丸められます。赤い三角形 (u=1.5 の線の左側) 内にあるものはすべて、u=2 ではなく u=1 に誤って丸められるため、これは上に示されています。

ただし、ここでいくつかの重要な観察結果があります...

1. オレンジ/赤の問題領域は重複していません

2. 立方体座標では、有効な 16 進数の中心は u + v + w =​​ 0 です。

以下のコードでは、丸められた座標の合計がゼロにならない場合にのみ、丸めとして最初から u、v、および w がすべて丸められます。

uR = Math.round(u);
vR = Math.round(v);
wR = Math.round(w);

これらの合計がゼロにならない場合、問題のある領域が重複していないため、正しく丸められていない座標が 1 つだけになります。この座標は、最も丸められた座標でもあります。

arr = [ Math.abs(u-uR), Math.abs(v-vR), Math.abs(w-wR) ];
var i = arr.indexOf(Math.max(...arr));

問題の座標が見つかった後、反対方向に丸められます。最終的な (x,y) は、丸め/修正された (u,v,w) から計算されます。

nearestHex = function(x,y){

  u = (2/3)*x;
  v = -(1/3)*x + (1/2)*y;
  w = -(1/3)*x - (1/2)*y;

  uR = Math.round(u);
  vR = Math.round(v);
  wR = Math.round(w);

  if(uR+vR+wR !== 0){
    arr = [ Math.abs(u-uR), Math.abs(v-vR), Math.abs(w-wR) ];
    var i = arr.indexOf(Math.max(...arr));

    switch(i){
      case 0:
        Math.round(u)===Math.floor(u) ? u = Math.ceil(u) : u = Math.floor(u);
        v = vR; w = wR;
        break;

      case 1:
        Math.round(v)===Math.floor(v) ? v = Math.ceil(v) : v = Math.floor(v);
        u = uR; w = wR;
        break;

      case 2:
        Math.round(w)===Math.floor(w) ? w = Math.ceil(w) : w = Math.floor(w);
        u = uR; v = vR;
        break;
    }
  }

  return {x: (3/2)*u, y: v-w};

}

Answer 4

これは SebastianTroy's answer の補遺です。コメントとして残しますが、まだ十分な評判がありません。

ここで説明されているように軸座標系を実装する場合: http://www.redblobgames.com/grids/hexagons/

コードにわずかな変更を加えることができます。

それ以外の

// Is the row an odd number?
if (rowIsOdd)// Yes: Offset x to match the indent of the row
    column = (int) ((x - halfWidth) / gridWidth);
else// No: Calculate normally
    column = (int) (x / gridWidth);

これを使って

float columnOffset = row * halfWidth;
column = (int)(x + columnOffset)/gridWidth; //switch + to - to align the grid the other way

これにより、座標 (0, 2) が (0, 0) の真下ではなく、(0, 0) および (0, 1) と同じ対角線上に配置されます。

Answer 5

それが誰かに役立つかどうかはわかりませんが、もっと簡単な解決策を思いつきました。六角形を作成するときは、それらに中間点を与えるだけで、マウスの座標で最も近い中間点を見つけることで、どちらがオンになっているかを見つけることができます!

Answer 6

私はこれが非常に遅いことを知っていますが、現在六角形のグリッドで作業しており、この問題の解決策を見つけようとしていました. 重い数学メソッドは私にはやり過ぎに思えますが、なぜ、どのように機能するのかは理解できました。ほとんど偶然に、数行のコードで実現できる非常にシンプルなソリューションを見つけました。

私の例では、六角形の中心の (x, y) を格納するメンバ Point 変数を含むカスタム Hexagon クラスがあります。次に、この中心値に基づいて六角形を計算して描画します。

各 Hexagon クラスは、行と col 変数 (グリッドが描画されたときに与えられる) を格納する Tile クラスにも関連付けられます。

必要な変数: - 半径 - グリッド行 - グリッド列 - 六角形の中心点 - マウス クリック ポイント (または他の指定されたポイント) - タイル/六角形のリスト

私のマウスリスナー：

addMouseListener(new MouseAdapter() {
        @Override
        public void mouseClicked(MouseEvent e) {
            super.mouseClicked(e);
            System.out.println("Mouse Click Registered");
            double closestDistance = Double.MAX_VALUE;
            int closestIndex = -1;
            for (int i = 0; i < tiles.size(); i++) {
                double distance = tiles.get(i).getDistance(new myPoint(e.getX(), e.getY()));
                if (distance < closestDistance) {
                    closestDistance = distance;
                    if (closestDistance <= radius) {
                        closestIndex = i;
                    }
                }
            }
            if (closestIndex > -1) {
                Tile t = tiles.get(closestIndex);
                System.out.println("Selected tile: " + t.getCol() + ", " + t.getRow());
            }
        }
    });

Tile クラスから実行された私の計算:

public double getDistance(myPoint p) {
    myPoint center = this.hexagon.getCenter();
    double xd = center.x - p.x;
    double yd = center.y - p.y;
    return Math.abs(Math.sqrt((xd * xd) + (yd * yd)));
}

これは何をしますか。マップ上の六角形のリストを調べ、指定した点と六角形の中心点からの距離の絶対値を計算します。距離が以前に計算された距離よりも小さい場合、その値を最小値として設定します。その数値が半径より小さい場合は、closestIndex をそのインデックス # に設定します。タイル ループの最後まで続行します。

ループの後、値インデックスが保存されていることを確認し、保存されている場合はそのインデックスを選択します。

注: これは、指定されたポイントから行/列を計算することによって、さらに最適化される可能性があります。その情報を使用して、ループするタイルの量を、そのポイントを鳴らしているタイルに制限できます。