正六边形网格化(Hexagonal Grids)原理与实现

 在路径规划、游戏设计栅格法应用中,正六边形网格不如矩形网格直接和常见,但是正六边形具有自身的应用特点,更适用于一些特殊场景中,比如旷阔的海洋、区域或者太空。本文主要讲述如何对正六边形进行几何学分析、网格化环境建模、坐标系转换以及正六边形间的关系求解等。六边形的具体代码实现可以参见github: https://github.com/wylloong/HexagonalGrids .

几何学分析:正六边形的边长相等,内角都是120度,其它性质可以参见百度百科。在正六边形网格化布局设计中,典型的正六边形方向有水平方向(pointy topped,图1)和垂直方向(flat topped,图2)两类,两者性质类似。篇幅所限,本文主要讨论pointy topped类型的正六边形网格化布局。

图 1. pointy topped

图 2. flat topped

如图3所示的正六边形布局,针对pointy topped型的正六边形,设其边长为size,则六边形的宽width=sqrt(3)/2*size,和相邻六边形的水平距离hori=sqrt(3)/2*size,六边形的高是height=size*2,和相邻六边形的垂直距离是vert=1.5*size。

图 3. pointy topped型的正六边形几何示意图

坐标系选择:假设实现六边形网格化,那么六边形位置关系的表达有很多方式,有Offset coordinates、Cube coordinates、Axial coordinates等。本文推荐使用Cube coordinates作为主要的展示方式,Axial coordinates作为网格存储单位和显示坐标系。

  Offset coordinates:最常用的坐标系,以左上角为坐标系原点,以横向为column轴,以纵向为roe轴,对行和列进行偏置。其中,针对flat topped型的正六边形,具有奇和偶两种表示方式,如下图所示。

  Cube coordinates:一种全新的看待正六边形的方式,它把正六边形看作具有三个轴,并且满足x+y+z=0的性质,并且我们可以使用标准的方法实现坐标系的加减乘除和求距离。Cube坐标系的原理和其它性质可以参见文献。

  因为我们已经有针对方形网格和cube网格的计算方法,使用cube坐标系允许我们对六边形采用这些算法。当这个算法要和其他坐标系交互时,我会把其他坐标系转换为cube坐标系,然后计算结束后在转换为其他坐标系。

  Axial coordinates:该坐标系是由cube坐标系中三个轴中的两个组成的。因为在cube坐标系有x+y+z=0的限制,所以第三个轴是多余的。Axial coordinates主要应用于地图存储和对用户的显示。Axial coordinates相比offset grids的优点是坐标系更清楚,劣势是当存储一个长方形地图时显得有点怪异。

  总结:Offset coordinates因为符合square grids通用的笛卡尔坐标系,是我们最容易想到的坐标系,但是因为两轴中的一轴必须跟随变化,是一件复杂的事情;Cube and axial systems随着增长而变化并且具有相对简单的计算方法,但是在存储时具有一定的复杂度。

Coordinate conversion:我们通常在项目中使用axial or offset coordinates,但是很多算法使用cube坐标系更容易去表达,所以我们需要在坐标系之间转换。

  Axial coordinates和cube coordinates联系紧密,所以转换公式相对简单。

  Offset coordinates和cube coordinates转换有点复杂。本文主要针对even-q offset和odd-q offset进行研究。

邻近网格:cube coordinates容易求出相邻的6个邻近正六边形网格,但是offset坐标系却比较复杂。

  Cube coordinates:在正六边形上移动一个网格,涉及到改变cube坐标系中两个轴,一个+1,另一个-1,所以共有六种可能性,每一种可能性对应于六边形的一个方向。

  Axial coordinates:如前所示,我们以cube为起点,由cube转换为axil坐标系即可,如下图所示。

Distance: 在cube坐标系中,每一个六边形是一个在cube里面的3d空间。在六边形中相邻的六边形距离是1,但是在cube grid里面距离是2,这会让距离求解变得简单和快速。在square grid中,Manhattan distances are abs(dx) + abs(dy). In a cube grid, Manhattan distances are abs(dx) + abs(dy) + abs(dz).

所以,在cube坐标系中,距离可以表示为

  在Axial coordinates,第三个坐标系是缺省的,所以通用的做法是先转变为cube坐标系,再求距离。

  在offset坐标系中,正如Axial coordinates坐标系,我们把offset转变为cube坐标系再求取距离。

 路径规划:如果使用基于图论的A*或者Dijkstra算法,在六边形中寻找最短路径和正方形网格并没有太多不同。其中,不同的是邻近网格位置获取方法不同,需要用到前面的方法获取临近网格。

启发函数:A*算法使用heuristic功能求出两个位置的距离。可以使用距离公式求出距离,乘以移动代价。

  参考文献和资料:

1、http://www.redblobgames.com/grids/hexagons/

2、Her I. Geometric transformations on the hexagonal grid[J]. IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society, 1995, 4(9):1213-22.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

【干货】Python大数据处理库PySpark实战——使用PySpark处理文本多分类问题

【导读】近日,多伦多数据科学家Susan Li发表一篇博文,讲解利用PySpark处理文本多分类问题的详情。我们知道,Apache Spark在处理实时数据方面...

8.7K9
来自专栏开源FPGA

基于MATLAB的中值滤波算法实现

  在实时图像采集中,不可避免的会引入噪声,尤其是干扰噪声和椒盐噪声,噪声的存在严重影响边缘检测的效果,中值滤波是一种基于排序统计理论的非线性平滑计数,能有效平...

2544
来自专栏专知

【论文推荐】最新5篇知识图谱相关论文—强化学习、习知识图谱的表示、词义消除歧义、并行翻译嵌入、图数据库

【导读】专知内容组整理了最近五篇知识图谱(Knowledge Graph)相关文章,为大家进行介绍,欢迎查看! 1. DeepPath: A Reinforce...

4164
来自专栏PPV课数据科学社区

【学习】常用的机器学习&数据挖掘知识点

Basis(基础): MSE(Mean Square Error 均方误差),LMS(LeastMean Square 最小均方),LSM(Least Squa...

34812
来自专栏CVer

谷歌CVPR 2018最全总结:45篇论文,Ian Goodfellow GAN演讲PPT下载

谷歌在今年的CVPR上表现强势,有超过200名谷歌员工将在大会上展示论文或被邀请演讲,45篇论文被接收。在计算机视觉领域,生成对抗网络GAN无疑是最受关注的主题...

3413
来自专栏专知

【论文推荐】最新十二篇情感分析相关论文—自然语言推理框架、网络事件、多任务学习、实时情感变化检测、多因素分析、深度语境词表示

2096
来自专栏生信技能树

第4篇:对ATAC-Seq/ChIP-seq的质量评估(一)——phantompeakqualtools

在下游分析前,最好是先对peak calling 后的ChIP-Seq数据进行质量评估。

4293
来自专栏专知

【论文推荐】最新六篇视觉问答相关论文—深度嵌入学习、句子表征学习、深度特征聚合、3D匹配、细粒度文本摘要

【导读】专知内容组为大家推出近期六篇图像检索(Image Retrieval)相关论文,欢迎查看!

1252
来自专栏专知

【论文推荐】最新七篇图像检索相关论文—草图、Tie-Aware、场景图解析、叠加跨注意力机制、深度哈希、人群估计

2453
来自专栏数据结构与算法

P1719 最大加权矩形

为了更好的备战NOIP2013,电脑组的几个女孩子LYQ,ZSC,ZHQ认为,我们不光需要机房,我们还需要运动,于是就决定找校长申请一块电脑组的课余运动场地,听...

39813

扫码关注云+社区