java - 用AVL树实现Bentley-Ottmann算法

Question

我在用java实现这个方法时遇到了问题。我在《计算几何》第三版中使用AVL BST树来实现算法FINDINTERSECTIONS书中的描述如下：
我遇到的问题是实现HANDLEEVENTPOINT中的步骤5。当事件点是交叉点时，状态不再完全按顺序排列，因为对于交叉线，它们在交叉点交叉，需要在状态中交换由于我使用的bst是avltree，delete方法失败，因为重新平衡方法需要元素的正确顺序（即delete方法假设树的顺序正确，并执行与顺序相关的旋转以保持log（n）高度）。另外，我使用的状态将数据存储在节点中，而不是如图所示的叶子中如果我理解正确，书上说这两种树都可以用。

Answer 1

首先，使用平衡二叉搜索树的叶版本，无论是红黑还是AVL我用了红黑色。
获取Peter Brass关于高级数据结构的书籍，因为在几乎所有的标准算法/数据结构书籍中，您都很难在这些叶树上找到任何东西。我相信它们也被称为外生树。
http://www-cs.engr.ccny.cuny.edu/~peter/
此外，您还可以查看mehlhorn和sanders的“算法和数据结构：基本工具箱”，它进入“排序序列”数据结构。当使用树木时，它们只借助于树叶树来创建这些树。他们也是开发LEDA的一些人。
另外，看看不列颠哥伦比亚在线的Leda图书，它有一章介绍了如何实现这个算法以及如何处理所有的“问题案例”。我认为这是第9章，有点难理解，也许是因为英语不是作者的母语……皮塔！啊！
http://people.mpi-inf.mpg.de/~mehlhorn/LEDAbook.html
您可以将叶节点数据项双重链接在一起，并且您已经创建了一个排序序列，该序列以树作为指向链接项列表的导航结构。莱达和in think cgal就是这样做的。
重复项在事件队列中的处理方式与扫描行状态结构不同。对于事件队列，只需将项目的链接列表添加到叶中（请参阅Brass的书）。在这里，每个叶对应于一个事件点，并且有一个所有段的列表，其起点和终点与事件点相同。所以有些会有空的列表，比如交集事件点和结束事件点。至少有些实现是这样做的。
对于扫描状态结构。重叠的平行段由所述段id来区分他们不会在你正在阅读/参考的书中谈论这些。然而，莱达的书告诉你如何处理这些因此，即使扫描状态树比较器说两个段具有相同的端点和方向，比较器还是通过使用段数据库、数组或其他任何东西中的段索引来打破这种联系。
更重要的是：
泳池积分！这个公共点池是基本的，然后组成段，并用于所有数据结构中。使用池可以通过测试身份来测试点相等性这样就避免了使用比较器，因为比较器会减慢速度，并且会引入错误。
关键是尽量避免使用树比较器。
当检查段是否属于同一束或是三组的成员时，你有一个问题（即，开始、结束或与扫描线上的事件点相交），不要使用比较器。
相反，可以使用这样一个事实，即属于同一捆绑包的段可以在列表中具有某些“信息属性”，例如，当段与事件点相交时指向事件队列，或者当段与后续项重叠时指向列表中的后续项，否则指向空值因此，您需要在事件队列与扫描线状态结构之间建立一些交叉链接你的套装和包裹很容易找到。转到与状态树相关联的链表的开始或结束处，并使用非常简单的测试逐项进行检查。
底线。在实现Bentley Ottmann的其余部分之前，正确地获得排序序列/平衡二叉树数据结构，并对其进行大量的研究。
这真的是关键，这本书根本没有指出，但不幸的是，这不是它的意图，因为这个实现是棘手的另外，请注意，该书在导航树的内部节点中添加了一个指向相关叶节点的额外链接。这只会让你更快地找到，但如果你不熟悉树叶树，可能就看不出来。在叶树中，键通常在叶节点和树的内部节点中的其他位置找到两次。
最后
像LEDA/CGAL这样的软件包使用精确的算法来保证工作正常leda开发人员花了10年时间才把事情弄对，这主要是因为使用了精确的算法。你也许可以用一个基本的交叉积测试来定位，但是如果你需要一个精确的版本，你可以在他的网站上找到jonathan shewchuk教授的精确算术包。
我猜你的书只是把这些作为“给读者/学生的练习”来写的。