我正在尝试在 Julia 中实现 Fortune 的算法来找到随机点数组的 Voronoi 多边形，但我真的很难找到海滩线。
我知道海滩线是几条抛物线的并集。每个抛物线都有阵列中的一个点作为其焦点，因此彼此相邻的抛物线的交点给出了两个 Voronoi 区域之间的“边缘”。 数组中的每个点都是海滩线所在的事件，但也会有一些称为“圆点”的东西对应于穿过三个“真实点”的圆的极点(在本例中为最低点) , 真正的点是随机点数组中的点。
我知道如何求抛物线的相交，我也知道当海滩线经过一个真实的点时，它的抛物线会是与之前点的抛物线相交的半条线，这个交点很容易找到。
您如何存储海滩线？在计算相邻抛物线的每个交点的事件中，您是否只存储交点？
我正在阅读 Mark de Berg 的Computational Geometry algorithms and applications，但我的母语不是英语，所以我有点难以理解一些东西。
所以，如果你能在这方面帮助我，那就太好了，在此先感谢。
最佳答案
在决定如何表示海滩线时，重要的考虑因素是您在算法过程中处理的每个“事件”必须仅对其进行局部修改。如果扫掠线移动了一点，但没有穿过任何事件，那么您对海滩线的表示不需要更改。
因此，海滩线数据结构不应包含海滩线上的任何实际点!
同样重要的是，您可以在 O(log N) 时间内找到要修改的部分。
最简单的表示只是一个二叉搜索树，其中包含按顺序为海滩线贡献抛物线的输入点。然后，在每个事件期间所做的修改包括添加或删除单个点。
关于algorithm - 什么包含了财富算法中的海岸线？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56325758/