我必须实现财富算法来构建 Voronoi 图。
该算法的重要部分是一种称为“海滩线数据结构”的数据结构。
它是一个二叉平衡树，类似于 AVL，但不同之处在于数据仅存储在叶子上（还有其他区别，但对问题不重要）。
我不确定如何实现它。显然，“按原样”使用 AVL 是行不通的，因为在平衡 AVL 时，叶子节点可以成为内部节点，反之亦然。
我还尝试在 wikipedia 上查看其他一些已知的数据结构，但没有一个适合需求。我已经看到一些使用链表执行此操作的实现，但这并不好，因为搜索链表是 O(n)，并且它需要 O(log n) 才能使算法有效。
叶子确实存储（单个）点，事件结构的内部节点（“海滩线树”）存储抛物线/弧彼此相邻的有序点元组。如果点P a形成的抛物线位于P b形成的抛物线的左侧（并且这两条抛物线相交），则内部节点存储有序元组(P a , P b )。
显然，“按原样”使用 AVL 是行不通的，因为在平衡 AVL 时，叶子节点可以成为内部节点，反之亦然。
如果您担心在 AVL 树中存储不同类型的对象，一个简单的方案是将叶子也存储为元组。所以不要将点P j存储为叶子，而是存储元组(P j , P j )。如果作为叶子的P j从事件树（海滩线）中消失，其父级为(P i , P j )，只需将父级更改为(P j , P j )，当然其父级也需要从(P j , P ? )更改为(P我，P ？)等等。就像使用常规的 AVL 树一样：您沿着树走并修改需要更改和/或重新平衡的内部节点。
请注意，算法的良好实现不能轻易写在 SO 答案中（至少，不是我！）。有关整个算法的正确解释，包括对其使用的数据结构的描述，请参阅Mark de Berg 等人的计算几何：算法和应用。. 第 7 章专门讨论 Voronoi 图。