webdevqa.jp.net

六角形グリッド、ポイントがどの六角形にあるかをどのようにして見つけますか?

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

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

ユーザーがクリックしたときにマウスが上にあるものを識別できるようにする必要があります。

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

33
Troyseph

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

Hexagonal grid with an overlayed square grid

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

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

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);

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

Generic equation for a straight line

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

    // 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];
}

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

enter image description hereenter image description here

mは勾配なので、 m = c/halfWidth

55
Troyseph

編集:この質問は私が最初に思ったよりも難しいです、私はいくつかの作業で私の回答を書き直しますが、解決策が他の回答の改善であるかどうかはわかりません。

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

つまり、dist_squared(Hex [n] .center、(x、y))をn以上に最小化します(平方とは、平方根について心配する必要がないため、CPUを節約できます)

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

enter image description here

したがって、最初のステップは、UV空間でのポイント(x、y)の表現、つまり(x、y)= lambdaU + muVなので、= (ラムダ、ミュー)UV空間

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

ここでポイント(lambda、mu)が与えられ、両方を最も近い整数に丸めると、次のようになります。

enter image description here

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

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

しかし、いくつかのポイントは六角形#(2,2)を返します。つまり、

enter image description here

同様に、一部は六角形#(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

enter image description here

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

enter image description here

    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)

これで、もう1つの六角形に絞り込んだので、どちらが近いかを見つけるだけです。

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

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

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

9
P i

私は@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空間での丸めでは、正しくマッピングされない領域がいくつかあることが指摘されています。

enter image description here

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

enter image description here

オレンジ色の三角形の領域は、六角形の中心から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};

}
4
Steve Ladavich

これはSebastianTroyの回答の補遺です。コメントとして残しておきますが、まだ評判が足りません。

ここで説明するように軸座標系を実装する場合: 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)と同じ対角列になります。

4
NeoShaman

http://playtechs.blogspot.co.uk/2007/04/hex-grids.html をもう一度見ましたが、数学的には非常に整然としています。

しかし、セバスチャンのアプローチは追いかけっこになり、驚くほど少ないコード行でタスクを達成するようです。

コメントセクションを読むと、誰かがPython実装 http://Gist.github.com/58318 を作成していることがわかります

私はそれを後世のためにここに貼り直します:

# copyright 2010 Eric Gradman
# free to use for any purpose, with or without attribution
# from an algorithm by James McNeill at
# http://playtechs.blogspot.com/2007/04/hex-grids.html

# the center of hex (0,0) is located at cartesian coordinates (0,0)

import numpy as np

# R ~ center of hex to Edge
# S ~ Edge length, also center to vertex
# T ~ "height of triangle"

real_R = 75. # in my application, a hex is 2*75 pixels wide
R = 2.
S = 2.*R/np.sqrt(3.)
T = S/2.
SCALE = real_R/R

# XM*X = I
# XM = Xinv
X = np.array([
    [ 0, R],
    [-S, S/2.]
])
XM = np.array([
    [1./(2.*R),  -1./S],
    [1./R,        0.  ]
])
# YM*Y = I
# YM = Yinv
Y = np.array([
    [R,    -R],
    [S/2.,  S/2.]
])
YM = np.array([
    [ 1./(2.*R), 1./S],
    [-1./(2.*R), 1./S],
])

def cartesian2hex(cp):
    """convert cartesian point cp to hex coord hp"""
    cp = np.multiply(cp, 1./SCALE)
    Mi = np.floor(np.dot(XM, cp))
    xi, yi = Mi
    i = np.floor((xi+yi+2.)/3.)

    Mj = np.floor(np.dot(YM, cp))
    xj, yj = Mj
    j = np.floor((xj+yj+2.)/3.)

    hp = i,j
    return hp

def hex2cartesian(hp):
    """convert hex center coordinate hp to cartesian centerpoint cp"""
    i,j = hp
    cp = np.array([
        i*(2*R) + j*R,
        j*(S+T)
    ])
    cp = np.multiply(cp, SCALE)

return cp
3
P i

それが誰かを助けることになるかどうかはわかりませんが、私ははるかに簡単な解決策を考え出しました。私が六角形のimを作成するとき、それらに中間点を与えるだけで、マウスcoordonateを使用して最も近い中間点を見つけることで、1つのimを見つけることができます!

2
user5021355

マウスが六角形にあるかどうかを確認する別の方法を見つけました。少しのトリガーを使用して、マウスと六角形の中心との間の線の角度を見つけることができます。この角度を使用して、線が六角形の中心から六角形のエッジまでの距離を計算できます角度。次に、マウス間の線の長さが六角形のエッジまでの予想される長さよりも短いことを確認します。誰かがサンプルコードを望んでいるなら、私は共有できます。

0
HazzaLad