高效算法：找到一个点属于哪个六边形

Question

我正在寻找更有效的方法来确定一个点属于哪个六边形，以下是需要处理的内容：

1. 一组点的数组 - 假设有10000个点。 2. 六边形中心点的数组，大约有1000个六边形。 3. 每个点只属于一个六边形，有些（大多数）六边形是空的。 4. 这些六边形形成了一个完美的网格，其中一个六边形的点从左上角开始（它将重叠整个区域的边缘）。

我的当前解决方案虽然可以工作，但速度比较慢，我认为时间复杂度会是n * (m log m)，其中n=length(points)，m=length(hexagons)。

我怀疑我可以做得比这更好，其中一个解决方案是仅对点和六边形按照它们到某个任意点（可能是中心，也可能是角落）的距离排序（仅一次），然后遍历点和六边形的子集，从第一个距此点距离> =最后匹配的六边形开始。同样，我们可以在（点 - >参考点）和（六边形中心 - >参考点）之间的距离差大于六边形的“半径”时停止查看六边形。理论上，由于我们知道每个点都属于一个六边形，我甚至不必考虑这种可能性。

我的问题是：有比这更好的方法吗？从时间复杂度的角度来看，最坏情况下的复杂度会略微降低到n * m，但平均情况下应该非常好，可能在n * 20左右（例如，我们只需要查看每个点的20个六边形）。下面是我当前低效解决方案供参考。

points.forEach((p) => {
  p.hex = _.sortBy(hexes, (hex) => {
    const xDist = Math.abs(hex.middle.x - p.x);
    const yDist = Math.abs(hex.middle.y - p.y);
    return Math.sqrt((xDist * xDist) + (yDist * yDist));
  })[0];
});

- Zack Newsham

---

https://www.redblobgames.com/grids/hexagons/#pixel-to-hex 这个网页展示了通过公式将正方形的网格坐标映射到六边形的方法，这符合你要找的内容吗？ - Jason Aller

那真是太酷了 - 我不是100%确定，但我一定会去看看 - 我开始研究四叉树，因为它可能可以解决问题，但看起来效率可能会降低。 - Zack Newsham

@JasonAller 哇，那个资源太棒了！ - Bergi

1000个六边形中有10000个点，而大多数六边形为空并不正确。 - user1196549

@daoust 这些六边形是一个网格，点不应该均匀分布。它们会聚集在某些区域周围。 - Zack Newsham

Answer 1

对于任意一点，您可以通过以下两个步骤找到最近的六边形中心（假设排列方式与未来学家相同）：

• 将横坐标除以中心之间的水平距离，并四舍五入至最近的整数。

• 将纵坐标除以垂直距离的一半，并根据上面发现的奇偶性四舍五入为最接近的偶数或奇数整数。

• 考虑此中心及其周围的六个中心，并保留最靠近目标点的中心。

这将在常数时间内为您提供图块的索引。

- user1196549

Answer 2

更新：为了记录

我现在正在使用这里提供的代码：https://www.redblobgames.com/grids/hexagons/

一个非常重要的注意事项是，你的六边形网格必须以第一个六边形的中心点（0,0）为起点——如果不是这样，你将会得到极为奇怪的结果，即使在考虑到预期偏移量后，这些结果仍然看起来像是舍入误差。对于我来说，第一个六边形放在哪个位置都没关系，所以我把它设置成了（0,0），效果非常好。

旧解决方案

我仍然希望有一个最优解决方案，但最终我自己编写了一个只需要检查每个点的6个六边形，并需要一点额外开销（大约sqrt(m)），对于大约3000个点和768个六边形（其中310个被填充），它正确地分配了100%的时间（与暴力方法相比），耗时29毫秒，而暴力方法需要约840毫秒。

首先，我将六边形存储在一个地图中，其中键是"${column},${row}"。列在技术上重叠，因此对于第0行，第0列从-0.5 * hexWidth开始，对于第1行，第0列从0px开始。

接下来，我从左上角六边形的位置开始，项为"0,0"，应该也在位置0，并相应地递增y的高度或六边形的边长。当y大于点y时，我找到了可能的行，然后检查上下行。

对于行内的列，我取x / hexWidth的Math.floor和Math.ceil。

这样做可以检查6个六边形，从这一点出发，解决方案与问题中的解决方案相同。

从理论上讲，这可以用于仅使用x/y位置查找正确的六边形。然而，在实践中，由于偏移1个单位导致约5%的错误，可能是一个四舍五入问题。

我看过一些其他的东西:

1. 根据 @jason-aller 的建议，尝试了https://www.redblobgames.com/grids/hexagons/#rounding。不幸的是，这似乎假定在六边形网格上进行某种变换（旋转），并且不容易理解——不断引用尚未定义的函数。

2. QuadTree（各种实现）不幸的是，对于每个点，这返回了大约100个"潜在匹配项"，因此性能改进不大。我知道插入顺序会改变QuadTree的有用程度，我尝试了自然顺序、按距离从上到下排序和随机排序，但它们都表现得很糟糕。使用QuadTree的最优解可能涉及使用最接近中点的项填充树，然后将离中心点1/2的项分别移到每个角落，递归地进行。对我来说太难了！

- Zack Newsham

---

如果你在舍入算法方面遇到问题，首先决定你想使用哪个坐标系。参考链接 - Bergi

你指的是哪段代码？你指向了这个网站https://www.redblobgames.com/grids/hexagons/，但你指的是哪一段代码或方法？ - four-eyes

Answer 3

只是一个建议：假设您具有来自正六边形网格的每个正六边形的中心（如果我理解正确，这是您拥有的信息的一部分）。

         -----
       /       \
           -     -----        -----------> x - axis
       \       /       \
         -----     -    
       /       \       /
           -     -----
       \       /       \
         -----     -    
           |   \       /
           |     ----- 
           |  
           |          
           V
        y - axis

您可以认为您的坐标系从六边形的中心开始，位于左上角，并且 y 坐标轴垂直向下，而 x 轴水平从左到右运行。您的正六边形网格中心形成了正方形网格的图像，其中正方形网格的整数顶点通过将方格中的点的坐标乘以 2 x 2 的矩阵（一个剪切矩阵）来转换为多边形的中心。

A = a*[ sqrt(3)/2    0;

          1/2        1 ]

其中a是六边形网格的一个参数，指的是相邻两个边上六边形中心之间的距离。这提供了一种将整数索引[m n]分配给由六边形中心形成的网格的方法。在此之后，如果您已知在六边形网格中具有坐标[x y]的点，则可以应用A的逆矩阵。

 [u; v] = A^(-1)*[x; y] 

where 

A^(-1) = (2/(a*sqrt(3)))*[  1           0   ;

                           -1/2   sqrt(3)/2 ]

（[x; y]和[u; v]是列向量）然后取m = floor(u)和n = floor(v)来确定正方形网格的左上角的整数坐标（也是索引）[m = floor(u), n = floor(v)]（请注意，我们选择了两个网格的坐标都从左上角开始）。因此，您的点[u, v]在具有顶点[m,n] [m+1, n] [m, n+1] [m+1, n+1]的正方形中，这意味着原始点[x y]在其中一个四个六边形中，其中心具有索引[m,n] [m+1, n] [m, n+1] [m+1, n+1]。因此，您可以使用它来检查点[x y]位于哪个四边形中。

希望这可以帮助到您。

- Futurologist