财富算法-海滩线数据结构
我必须实现 Fortunes 算法 来构建 Voronoi 图。
该算法的重要部分是一个称为“海滩线数据结构”的数据结构。
它是一棵二叉平衡树，类似于 AVL，但不同之处在于数据仅存储在叶子上（还有其他差异，但对于问题来说并不重要）。
我不知道如何实施它。显然，“按原样”使用 AVL 是行不通的，因为平衡 AVL 树时，叶子节点可以成为内部节点，反之亦然。
我还尝试在维基百科上查看其他一些已知的数据结构，但没有一个适合需要。 我见过一些使用链表执行此操作的实现，但这并不好，因为搜索链表的时间复杂度为 O(n)，并且需要 O(log n) 才能使算法高效。
I have to implement Fortunes algorithm for constructing Voronoi diagrams.
Important part of the algorithm is a data structure called "Beach Line Data Structure".
It is a binary balanced tree, similar to AVL, but different in a way that data is stored only on the leafs (there are other differences, but are unimportant for the question).
I am not sure how to implement it. Obviously using AVL "as is" will not work because when balancing AVL tree leaf node can become inner node and vice versa.
I also tried to look at some other known data structures at wikipedia, but none suits the needs.
I have seen some implementations that do this with a linked list, but this is not good because searching linked list is O(n), and it needs to be O(log n) for the algorithm to be efficient.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
叶子确实存储（单个）点，事件结构的内部节点（“海滩线树”）存储抛物线/弧彼此相邻的点的有序元组。如果点 Pa 形成的抛物线位于 Pb 形成的抛物线的左侧（并且这些两个抛物线相交），内部节点存储有序元组(Pa, Pb)。
如果您担心在 AVL 树中存储不同类型的对象，一个简单的方案是将叶子也存储为元组。因此，不要将点 Pj 存储为叶子，而是存储元组 (Pj, Pj< /sub>) 相反。如果 Pj 作为叶子从事件树（海滩线）消失，其父级为 (Pi, P< sub>j)，只需将父级更改为 (Pj, Pj)，当然其父级也需要更改为(Pj, P?) 到 (Pi, P? sub>) 等。就像常规的 AVL 树一样：您沿着树向上走并修改需要更改和/或重新平衡的内部节点。
请注意，算法的良好实现不能轻易地写在 SO 答案中（至少，不是我！）。有关整个算法的正确解释，包括其使用的数据结构的描述，请参阅 计算几何：算法和应用Mark de Berg 等人。。第 7 章专门讨论 Voronoi 图。
The leaves indeed store (single) points and the inner nodes of the event structure (the "beach line tree") stores ordered tuples of points whose parabolas/arcs lie next to each other. If the parabola that point Pa forms lies to the left of the parabola formed by Pb (and these two parabola's intersect), the inner node stores the ordered tuple (Pa, Pb).
If you're worried about storing different types of objects in the AVL tree, a simple scheme would be to store the leaves as tuples too. So don't store point Pj as a leaf, but store the tuple (Pj, Pj) instead. If Pj as a leaf disappears from the event tree (beach line), and its parent is (Pi, Pj), simply change the parent into (Pj, Pj), and of course its parent will also needs to be changed from (Pj, P?) to (Pi, P?) etc. Just as with a regular AVL tree: you walk up the tree and modify the inner nodes that need to be changed and/or re-balanced.
Note that a good implementation of the algorithm can't be easily written down in a SO answer (at least, not by me!). For a proper explanation of the entire algorithm, including a description of the data structures used by it, see Computational geometry: algorithms and applications by Mark de Berg et al.. Chapter 7 is devoted solely to Voronoi diagrams.