algorithm - 六边形网格，你如何找到一个点在哪个六边形中？

Question

我有一张由六边形的行和列组成的 map

这不是我使用的六边形 map 的实际图像，但使用了相同大小和形状的六边形

我需要能够在用户点击时判断鼠标悬停在哪一个上，

每个六边形都由“Tile”类的一个实例表示，但是它不包含任何位置特定数据，甚至不包含多边形，所以基本上判断特定六边形位置的唯一方法是知道它是二维数组中的位置。

我以前用过正方形的网格，比较容易搞清楚选的是哪个正方形，因为像素也是正方形的，

// 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();
}

但我什至不确定从哪里开始使用六边形，有人有经验吗？

我不能使用多边形 (Java)，因为当我开始在屏幕上四处移动 map 并增加它的大小时，我会遇到每帧更新大量多边形的问题。虽然这样我就可以检查 map 的任何图 block 的多边形中是否包含一个点!

目前显示的六边形只是 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);

此时我们有了我们点所在的框的行和列，接下来我们需要针对六边形的两个顶部边缘测试我们的点，看看我们的点是否位于上面的任一六边形中:

    // 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