六边形相关的数学知识

本文翻译自Ruslan的博客，感谢分享相关知识。

均匀的六角形网格是计算机游戏和图形应用程序中的重复模式。

有些操作可能需要在使用六边形格子时实现：

1. 通过其在网格中的索引找到六角形的位置；

2. 用鼠标挑选一个六角形；

3. 寻找相邻的格子；

4. 查找六角形的中心坐标等。

尽管这些东西看起来并不困难（有点像小学水平的几何/算术运算法则 ），但它并不像矩形网格那样简单。

尝试咨询互联网后，我在CodeProject上找到了一篇整洁的文章，该文章恰好解决了所提到的问题。它的评分很高，我想这确实是需要的东西。

但是，令我感到困惑的是，提出的解决方案（和代码）似乎比人们预期的要复杂：

1. 六边形的位置通过迭代寻找，根据先前计算的位置迭代找到六边形位置；

2. 在此过程中需要处理了一些极端/边界情况；

3. 每个六边形都存储了大量状态；

4. 对于替代的六边形定向模式（又称“尖头”定向），有一个单独的代码路径，它与主模式相交；

5. 要用鼠标选择一个六边形，代码将在六边形数组上进行迭代，并使用存储的角点坐标对每个六边形进行通用的“多边形点”测试。

我们可以做得更简单吗？ 根据六角格特性，让我们检查六角形的几何特性并定义一些常数：

1.png

我们通过其半径R定义六角形，并根据其半径找到其他一些参数，例如W（“宽度”），S（“侧面”）和H（“高度”）。

现在，让我们看一下六角形网格本身：

2.png
通过数组索引查找六边形位置

从该图片中，可以得出通过其数组索引（i，j）查找六边形单元的左上角位置的公式：

3.png

考虑到对于奇数列i％2（从i除以2所得的值）等于1，对于偶数列等于0，我们可以重写它：

4.png

通过一个点找到六边形索引

另一个操作是从屏幕上的点坐标中找到六边形数组坐标，该坐标用于鼠标点击。

根据观察，六角形网格可以完全被一组矩形块(宽度S，高度H)所覆盖，在上图中，它们被绘制成带有紫色三角形的绿色矩形。每个瓦片有三个六边形重叠。

找到我们的选择点进入的那些六边形并不太难:

5.png

在这里 (it，jt)被点选中的矩形图形的列/行。这些花哨的括号是a 向下取整。

从矩阵的行列转换成六边形的行列：

6.png

做完这些之后，现在我们可以找出三个可能的六边形中的哪一个与我们的点相对应。为此，我们放大矩形单元格的坐标系统，并构建分离线(图中的粗红线)的绘图。它的功能是 xt = R | 0.5-yt/H|，对于直线以上的所有点(它们都在绿色区域内)，我们得到 xt > R |0.5t/ H|。

对于矩形内的所有其他点，我们必须选择左边的上六边形或下六边形。这是根据它的值来决定的 yt。

一般来说，我们必须注意奇数/偶数行索引的差异(因为六边形数组中的行是锯齿形的)。

考虑以上因素，选中的六边形的最终数组下标是:

7.png

“尖”网格方向

到目前为止，我们只考虑了“平躺”网格方向(即六边形“躺”在它们的两侧)。

如果我们想要有另一个方向，当六边形的角向上时，我们应该重写所有的公式吗?

关于“尖”方向的一个简单观察是，你可以通过围绕对角轴镜像“平”方向来得到它。

这样做的直接结果是，“pointy”情况下的所有计算都可以通过以下方式执行:

• 交换输入坐标(即x<->y或i<->j;

• 应用上述公式;

• 交换输出坐标回来(“反镜像”它们):i<->j, x<->y。

这个操作在代码中是非常简单的(而不是为每种情况都有一个单独的代码路径)，我把它留给读者作为练习。

代码

下面是一个Java代码示例，它实现了公式:

<pre mdtype="fences" cid="n187" lang="" class="md-fences md-end-block ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">​
package com.rush;
​
/**
 * Uniform hexagonal grid cell's metrics utility class.
 */
public class HexGridCell {
 private static final int[] NEIGHBORS_DI = { 0, 1, 1, 0, -1, -1 };
 private static final int[][] NEIGHBORS_DJ = { 
 { -1, -1, 0, 1, 0, -1 }, { -1, 0, 1, 1, 1, 0 } };
​
 private final int[] CORNERS_DX; // array of horizontal offsets of the cell's corners
 private final int[] CORNERS_DY; // array of vertical offsets of the cell's corners
 private final int SIDE;
​
 private int mX = 0; // cell's left coordinate
 private int mY = 0; // cell's top coordinate
​
 private int mI = 0; // cell's horizontal grid coordinate
 private int mJ = 0; // cell's vertical grid coordinate
​
 /**
 * Cell radius (distance from center to one of the corners)
 */
 public final int RADIUS;
 /**
 * Cell height
 */
 public final int HEIGHT;
 /**
 * Cell width
 */
 public final int WIDTH;
​
 public static final int NUM_NEIGHBORS = 6;
​
 /**
 * @param radius Cell radius (distance from the center to one of the corners)
 */
 public HexGridCell(int radius) {
 RADIUS = radius;
 WIDTH = radius * 2;
 HEIGHT = (int) (((float) radius) * Math.sqrt(3));
 SIDE = radius * 3 / 2;
​
 int cdx[] = { RADIUS / 2, SIDE, WIDTH, SIDE, RADIUS / 2, 0 };
 CORNERS_DX = cdx;
 int cdy[] = { 0, 0, HEIGHT / 2, HEIGHT, HEIGHT, HEIGHT / 2 };
 CORNERS_DY = cdy;
 }
​
 /**
 * @return X coordinate of the cell's top left corner.
 */
 public int getLeft() {
 return mX;
 }
​
 /**
 * @return Y coordinate of the cell's top left corner.
 */
 public int getTop() {
 return mY;
 }
​
 /**
 * @return X coordinate of the cell's center
 */
 public int getCenterX() {
 return mX + RADIUS;
 }
​
 /**
 * @return Y coordinate of the cell's center
 */
 public int getCenterY() {
 return mY + HEIGHT / 2;
 }
​
 /**
 * @return Horizontal grid coordinate for the cell.
 */
 public int getIndexI() {
 return mI;
 }
​
 /**
 * @return Vertical grid coordinate for the cell.
 */
 public int getIndexJ() {
 return mJ;
 }
​
 /**
 * @return Horizontal grid coordinate for the given neighbor.
 */
 public int getNeighborI(int neighborIdx) {
 return mI + NEIGHBORS_DI[neighborIdx];
 }
​
 /**
 * @return Vertical grid coordinate for the given neighbor.
 */
 public int getNeighborJ(int neighborIdx) {
 return mJ + NEIGHBORS_DJ[mI % 2][neighborIdx];
 }
​
 /**
 * Computes X and Y coordinates for all of the cell's 6 corners, clockwise,
 * starting from the top left.
 * 
 * @param cornersX Array to fill in with X coordinates of the cell's corners
 * @param cornersX Array to fill in with Y coordinates of the cell's corners
 */
 public void computeCorners(int[] cornersX, int[] cornersY) {
 for (int k = 0; k < NUM_NEIGHBORS; k++) {
 cornersX[k] = mX + CORNERS_DX[k];
 cornersY[k] = mY + CORNERS_DY[k];
 }
 }
​
 /**
 * Sets the cell's horizontal and vertical grid coordinates.
 */
 public void setCellIndex(int i, int j) {
 mI = i;
 mJ = j;
 mX = i * SIDE;
 mY = HEIGHT * (2 * j + (i % 2)) / 2;
 }

 /**
 * Sets the cell as corresponding to some point inside it (can be used for
 * e.g. mouse picking).
 */
 public void setCellByPoint(int x, int y) {
 int ci = (int)Math.floor((float)x/(float)SIDE);
 int cx = x - SIDE*ci;
​
 int ty = y - (ci % 2) * HEIGHT / 2;
 int cj = (int)Math.floor((float)ty/(float)HEIGHT);
 int cy = ty - HEIGHT*cj;
​
 if (cx > Math.abs(RADIUS / 2 - RADIUS * cy / HEIGHT)) {
 setCellIndex(ci, cj);
 } else {
 setCellIndex(ci - 1, cj + (ci % 2) - ((cy < HEIGHT / 2) ? 1 : 0));
 }
 }
}</pre>

测试代码

为了测试代码，我编写了一个小型Java applet程序。

这是一个六边形版本的游戏，叫做 “灯”(我借用了这个概念 在这里)。

游戏开始时，所有的“灯”都是亮着的(所有的六边形都是黄色的)，目标是关掉所有的灯(这样所有的六边形都变成灰色)。

8.png

每当用户点击一个六边形时，它就会切换它的灯光，以及所有邻近的六边形。

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="" cid="n202" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">package com.rush;
​```
import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
​
import javax.swing.JFrame;
import javax.swing.JOptionPane;
​
/**
 * Example applet which uses hexagonal grid. It's a hexagonal version of the
 * "lights out" puzzle game: http://en.wikipedia.org/wiki/Lights_Out_(game)
 */
public class HexLightsOut extends Applet implements MouseListener {
 private static final long serialVersionUID = 1L;
​
 private static final int BOARD_WIDTH = 5;
 private static final int BOARD_HEIGHT = 4;
​
 private static final int L_ON = 1;
 private static final int L_OFF = 2;
​
 private static final int NUM_HEX_CORNERS = 6;
 private static final int CELL_RADIUS = 40;
​
 //  game board cells array
 private int[][] mCells = { {    0, L_ON, L_ON, L_ON,    0 }, 
 { L_ON, L_ON, L_ON, L_ON, L_ON }, 
 { L_ON, L_ON, L_ON, L_ON, L_ON },
 {    0,    0, L_ON,    0,    0 } };
​
 private int[] mCornersX = new int[NUM_HEX_CORNERS];
 private int[] mCornersY = new int[NUM_HEX_CORNERS];
​
 private static HexGridCell mCellMetrics = new HexGridCell(CELL_RADIUS);
​
 @Override
 public void init() {
 addMouseListener(this);
 }
​
 @Override
 public void paint(Graphics g) {
 for (int j = 0; j < BOARD_HEIGHT; j++) {
 for (int i = 0; i < BOARD_WIDTH; i++) {
 mCellMetrics.setCellIndex(i, j);
 if (mCells[j][i] != 0) {
 mCellMetrics.computeCorners(mCornersX, mCornersY);
​
 g.setColor((mCells[j][i] == L_ON) ? Color.ORANGE : Color.GRAY);
 g.fillPolygon(mCornersX, mCornersY, NUM_HEX_CORNERS);
 g.setColor(Color.BLACK);
 g.drawPolygon(mCornersX, mCornersY, NUM_HEX_CORNERS);
 }
 }
 }
 }
​
 @Override
 public void update(Graphics g) {
 paint(g);
 }
​
 /**
 * Returns true if the cell is inside the game board.
 * 
 * @param i cell's horizontal index
 * @param j cell's vertical index
 */
 private boolean isInsideBoard(int i, int j) {
 return i >= 0 && i < BOARD_WIDTH && j >= 0 && j < BOARD_HEIGHT
 && mCells[j][i] != 0;
 }
​
 /**
 * Toggles the cell's light ON<->OFF.
 */
 private void toggleCell(int i, int j) {
 mCells[j][i] = (mCells[j][i] == L_ON) ? L_OFF : L_ON;
 }
​
 /**
 * Returns true if all lights have been switched off.
 */
 private boolean isWinCondition() {
 for (int j = 0; j < BOARD_HEIGHT; j++) {
 for (int i = 0; i < BOARD_WIDTH; i++) {
 if (mCells[j][i] == L_ON) {
 return false;
 }
 }
 }
 return true;
 }
​
 /**
 * Resets the game to the initial position (all lights are on).
 */
 private void resetGame() {
 for (int j = 0; j < BOARD_HEIGHT; j++) {
 for (int i = 0; i < BOARD_WIDTH; i++) {
 if (mCells[j][i] == L_OFF) {
 mCells[j][i] = L_ON;
 }
 }
 }
 }
​
 @Override
 public void mouseReleased(MouseEvent arg0) {
 mCellMetrics.setCellByPoint(arg0.getX(), arg0.getY());
 int clickI = mCellMetrics.getIndexI();
 int clickJ = mCellMetrics.getIndexJ();
​
 if (isInsideBoard(clickI, clickJ)) {
 // toggle the clicked cell together with the neighbors
 toggleCell(clickI, clickJ);
 for (int k = 0; k < 6; k++) {
 int nI = mCellMetrics.getNeighborI(k);
 int nJ = mCellMetrics.getNeighborJ(k);
 if (isInsideBoard(nI, nJ)) {
 toggleCell(nI, nJ);
 }
 }
 }
 repaint();
​
 if (isWinCondition()) {
 JOptionPane.showMessageDialog(new JFrame(), "Well done!");
 resetGame();
 repaint();
 }
 }
​
 @Override
 public void mouseClicked(MouseEvent arg0) {
 }
​
 @Override
 public void mouseEntered(MouseEvent arg0) {
 }
​
 @Override
 public void mouseExited(MouseEvent arg0) {
 }
​
 @Override
 public void mousePressed(MouseEvent arg0) {
 }
}</pre>

来源 github上可用。