haskell - 在实现 Birdson 的泊松盘分布时使用哪种数据结构

Question

我正在尝试编写一个函数来创建一组点 ( :: (Float,Float))使用 Haskell 的泊松盘分布。我正在使用 Birdson 算法 如 described在 Mike Bostock's blog .

点被保存在一个网格中，这样每个单元格永远不会超过一个点。通过这样做，最近邻问题从 O(n) 减少到 O(1)。

我的问题是该网格使用什么样的数据结构。 JavaScript 使用可变数组和 for 循环，因为命令式语言倾向于这样做。我可以使用 Vectors 复制这种方法，但我觉得可能有更好的功能数据结构。

什么样的结构适合这个网格？这是一个使用的地方共济会 ?

Answer 1

对于最近邻问题，有一种称为 Voronoi 图的通用结构。通过该图上的点位置，您可以在 O(log n) 中找到最近的邻居。我认为 O(1) 是不可能的，除非您的问题有其他特定的特征。对于点定位，可以使用 Edelsbrunner 的链式方法，或者 Sleator 和 Tarjan 的持久二叉搜索树。您可以在 GLib 中找到 C 实现。 .希望你也能找到用 javascript 实现的这些算法和数据结构:js voronoi .