实施宾利奥特曼算法AVL树 [英] Implementing Bentley–Ottmann Algorithm with an AVL tree

问题描述

我在实施这一方法在java中的一个问题。我专门实施计算几何第三版算法 FINDINTERSECTIONS 使用AVL BST树的状态。从书中的描述如下：

I'm having a problem implementing this method in java. I'm specifically implementing the algorithm FINDINTERSECTIONS in Computational Geometry 3rd Edition using an AVL BST tree for the status. The description from the book is shown below:

我有正在执行第5步中 HANDLEEVENTPOINT 的问题。当事件点是交叉点，则状态为不再全序那里，因为对于交线，它们跨越在其交叉点，需要在状态被交换。由于我使用的BST是AVLTree，删除方法失败，因为再平衡的方法需要的元素的正确顺序（即删除方法假定树正确排序，并进行旋转相对于顺序，以保持日志（n）的高度）。另外，我使用的存储状态中的节点，而不是叶子中的数据，如图中所示。如果我理解正确的话，这本书说，既可以用于种树。

The problem I'm having is implementing step 5 in HANDLEEVENTPOINT. When the event point is an intersection, the status is no longer totally ordered there, because for intersection lines, they cross at their intersection point and need to be swapped in the status. Since the BST I'm using is an AVLTree, the delete method fails because the rebalancing method requires proper ordering of the elements (i.e. the delete method assumes the tree is properly ordered, and performs rotations with respect to the order in order to maintain log(n) height). Also, the status I'm using stores the data in the nodes instead of the leaves as shown in the figure. If I understand correctly, the book says that either kind of tree can be used.

推荐答案

首先利用平衡二叉搜索树的叶子版本是否红黑或AVL。我用红黑色。

First off use a leaf version of a balanced binary search tree whether red-black or AVL. I used red-black.

获取先进的数据结构彼得黄铜的书，因为你将很难找到这些叶子的树木什么的几乎所有的标准算法/数据结构的书。我相信他们也被称为外生的树木。

Get Peter Brass's book on advanced data structures because you will have trouble finding anything on these leaf trees in virtually all the standard algorithm / data structure books. I believe they are also called exogenous trees.

http://www-cs.engr.ccny.cuny.edu/ 〜彼得/

另外，你可以看看算法与数据结构：基本工具箱，由Mehlhorn和桑德斯其中进入排序序列数据结构。他们创建这些只有叶树木的帮助，当树木被使用。这也是一些发达国家LEDA。

Also, you can look at "Algorithms and Data Structures: The Basic Toolbox" by Mehlhorn and Sanders which goes into the "sorted sequence" data structure. They create these with the help of only leaf trees when trees are used. These are also some of the folks that developed LEDA.

另外，也要看看勒达在线预订BC有关于如何执行这个算法，以及如何处理所有的一章有问题的个案。我觉得这是第9章，是一个有点难以遵循也许是因为英语不是的作者...... PITA的母语！

Also look at the LEDA book online bc it has a chapter on how to implement this algorithm and how to handle ALL the "problem cases." I think this is chapter 9 and is a bit hard to follow maybe because English is not the native tongue of the authors ... PITA!!

http://people.mpi-inf.mpg.de/~ mehlhorn / LEDAbook.html

您可以双叶节点的数据项链接在一起，并创建了带有树作为导航结构，以项目的链接列表排序的序列。这是LEDA在想怎么CGAL做到这一点。

You can doubly link the leaf nodes data items together and you have created a sorted sequence with the tree as a navigation structure to the linked list of items. That is how LEDA and in think CGAL do this.

重复的项目比扫描线状态结构中的事件队列处理方式不同。对于事件队列，只需添加到叶项的链表（见黄铜的书）。这里每个叶对应于事件点，并具有所有段的列表，包括一个起始端点这一点，相同的事件点​​。因此，一些具有类似的交集事件点和结束事件点空列表。至少这是一些实现如何做到这一点。

Duplicate items are handled differently in the event queue than the sweep line status structure. For the event queue, just add to a leaf a linked list of items (see Brass's book). Here each leaf corresponds to an event point and has a list of all segments with a starting-end-point this that same as the event point. So some will have empty lists like intersection-event-points and ending-event-points. At least that is how some implementations do this.

有关扫描状态结构。重叠并行段由发言权段ID来区分。他们不谈论这些在你正在阅读/参考书籍。然而，勒达本书告诉你如何处理这些。因此，即使扫描状态树木比较说两个段具有相同的终点和取向，比较打破平局通过使用在段数据库，阵列或任何段的索引。

For the sweep status structure. Overlapping parallel segments are differentiated by say segment ids. They do not talk about these in the book you are reading/referencing. However, the LEDA book tells you how to handle these. So even though sweep status trees comparator says two segments have the same end-point and orientation, the comparator breaks the tie by using the segments indexes in the segments database, array or whatever.

池穴！点的这个公共池是碱性，然后补足段，并在所有的数据结构被使用。使用池允许一个由刚测试的身份来测试点的平等！这避免了使用比较这会减慢速度，并可能产生错误。

Pool points! This common pool of points are basic and then make up the segments and are used in all the data structures. Using the pool allows one to test for point equality by just testing for identity! This avoids using a comparator which slows things down and can introduce errors.

您避免使用树比较尽可能这是关键。

It is key that you avoid using the tree comparators as much as possible.

当检查，如果段属于同一个包或者是你有一个约（即起点，终点或interesect与和事件点上扫线）问题的三个组的成员，请不要使用比较。

When checking if segments belong to the same bundle or are members of the three sets you are having a question about (i.e, start, end or interesect with and event point on the sweep-line), DO NOT USE THE COMPARATOR.

相反，使用这一事实，属于同一束段可以有一些信息属性说在列表要么指向当一个段相交的事件点，或指向后继项目列表中的事件队列如果该段重叠的继任者，或者指向否则返回null。所以，你需要与sweepline状态结构中的事件队列之间的一些交联。你套和捆绑是非常快速和容易找到。转至链接列表关联的状态树的开始或结束，并通过它去逐项一个非常简单的测试。

Instead, use that fact that segments belonging to the same bundle can have some "information property" say in the list that either points to the event queue when a segment intersects an event point, or points to the successor item in the list if the segment overlaps the successor, or points to null otherwise. So you will need some cross-linking between the event queue with the sweepline status structure. Your sets and bundles are the very fast and easy to find. Go to the start or end of the linked-list associate with the status tree and go through it item by item with a very simple test.

底线。获取排序序列/平衡二叉树的数据结构和工作的权利上实现宾利 - 奥特曼的其余部分之前很多。

BOTTOM LINE. Get the sorted sequence / balanced binary tree data structure right and work on that a lot before implementing the rest of Bentley-Ottmann.

这是真正的关键，而本书没有指出这一点，但在所有不幸的是，是不是它的意图，因为这个实现是棘手的。此外，请注意，这本书扩充导航树中指向相关联的叶节点树的内部节点的额外链接。这只是让发现有点快，但如果你不熟悉叶子的树木可能不明显。在一个叶树甲键经常发现两次，在叶节点和其他地方，在树的内部节点。

This is really the key and that book does not point that out at all but unfortunately that isn't it's intent since this implementation is tricky. Also, note that the book augments the navigation tree with an extra link in the internal nodes of the tree that point to associated leaf nodes. This just makes find a bit faster but may not be apparent if you are not familiar with leaf trees. A key in a leaf tree is often found twice, at the leaf node and elsewhere in an internal node of the tree.

包像LEDA / CGAL使用精确的算法的东西很好地工作。花了LEDA开发10年的事情做好，而主要是是由于使用精确的算法。你可能确定与用于定位一个基本的跨产品测试，但如果你需要一个确切的版本，那么你可以在他的网站上找到乔纳森Shewchuk教授精确的算法包。

Packages like LEDA/CGAL use exact arithmetic for things to work well. It took LEDA developers 10 years to get things right and that was mostly was due to using exact arithmetic. You maybe OK with a basic cross-product test used for orientation but if you need an exact version then you can find Prof. Jonathan Shewchuk exact arithmetic package on his site.

我想你的书刚离开这一切了作为一个演习为读者/学生。 LOL。

I guess your book just left all this out as an "exercise for the reader/student." LOL.

这篇关于实施宾利奥特曼算法AVL树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！