查找点属于哪个六角形的高效算法

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

Answer 1

更新：为后代留下以下评论

我现在使用此处提供的代码：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。

接下来，我从左上角六边形 item 的位置开始"0,0"，该位置也应该位于位置 0，并y相应地增加六边形的高度或六边形的边长。当yis > the points时y，我找到了可能的行，然后检查上面和下面的行。

对于行内的列，我采用 theMath.floor和Math.ceilof x / hexWidth。

这样做会给出 6 个六边形来检查，从这一点来看，解决方案与问题中的解决方案相同。

理论上，这可以用于使用 x/y 位置查找正确的六边形。然而在实践中，这对我来说不起作用，大约 5% 的时间有 1 个错误，可能是一个舍入问题。

我看过的其他一些东西：

1. 正如 @jason-aller 所建议的，https://www.redblobgames.com/grids/hexagons/#rounding。不幸的是，这似乎假设了六角网格上某种形式的变换（旋转）并且不容易遵循 - 不断引用尚未定义的函数。

2. 不幸的是，QuadTree（各种实现）为每个点返回了大约 100 个“潜在匹配”，因此性能改进并不好。我知道插入顺序改变了四叉树的有用程度，我尝试了自然顺序，按距顶部、左侧和洗牌的距离排序，它们的表现都同样糟糕。四叉树的最佳解决方案可能涉及使用最接近中点的项目填充树，然后递归地使用从中点到每个角 1/2 的项目填充树。对我来说太辛苦了！