用AVL树实现Bentley–Ottmann算法的java

Question

我在用java实现这个方法时遇到了一个问题。我正在计算几何第三版中具体实现算法FINDINTERSECTIONS，使用AVL BST树作为状态。书中的描述如下所示：

我遇到的问题是在HANDLEEVENTPOINT中实现步骤5。当事件点是交点时，状态不再完全按顺序排列，因为对于交点线，它们在交点处相交，需要在状态中交换。由于我使用的BST是一个AVLTree，因此delete方法失败，因为重新平衡方法需要元素的正确顺序（即delete方法假设树的顺序正确，并根据顺序执行旋转以保持对数（n）高度）。此外，我使用的状态将数据存储在节点中，而不是图中所示的叶子中。如果我理解正确，书中说可以使用任何一种树

Answer 1

更新：在你从那本书中发布的算法中，反转相交线段顺序的交换是通过删除完成的，然后是重新插入。LEDA对这些掉期使用反向_items（）。这是一种更有效的方法，可以在不使用比较器的情况下进行节点和项目的子序列反转。搜索_rs_树。c查看LEDA源或参见下文

// reverse a subsequence of items, assuming that all keys are
// in the correct order afterwards
//
void rs_tree::reverse_items( rst_item pl, rst_item pr )
{
  int prio ;
  register rst_item ppl = p_item(pl),  // pred of pl
  ppr = s_item(pr),  // succ of pr
  ql, qr ;

  while( (pl!=pr) && (pl!=ppl) ) {  // pl and pr didnt't
// met up to now
// swap all of pl and pr except the key
// swap parents
    ql = parent(pl) ;  qr = parent(pr) ;  
    if( pl==r_child(ql) )
      r_child(ql) = pr ;
    else
      l_child(ql) = pr ;
    if( pr==r_child(qr) )
      r_child(qr) = pl ;
    else
      l_child(qr) = pl ;
    parent(pl ) = qr ; parent(pr) = ql ;  
// swap left children
    ql = l_child(pl) ;  qr = l_child(pr) ;
    if( ql != qr ) {    // at least one exists
      l_child(pl) = qr ; parent(qr) = pl ;
      l_child(pr) = ql ; parent(ql) = pr ;
    }
// swap right children
    ql = r_child(pl) ;  qr = r_child(pr) ;
    if( ql != qr ) {    // at least one exists
      r_child(pl) = qr ; parent(qr) = pl ;
      r_child(pr) = ql ; parent(ql) = pr ;
    }
// swap priorities
    prio = pl->prio ;  pl->prio = pr->prio ;  
    pr->prio = prio ;
// swap pred-succ-ptrs
    s_item(ppl) = pr ;  p_item(ppr) = pl ;
    ql = pl ;  pl = s_item(pl) ;   // shift pl and pr
    qr = pr ;  pr = p_item(pr) ;
    s_item(ql) = ppr ;  p_item(qr) = ppl ;
    ppl = qr ;  ppr = ql ;  // shift ppl and ppr
  }
  // correct "inner" pred-succ-ptrs
  p_item(ppr) = pl ;  s_item(ppl) = pr ;
  if( pl==pr ) {    // odd-length subseq.
    p_item(pl) = ppl ;  s_item(pr) = ppr ;  
  }
}

另外：排序序列数据结构可以使用AVL树、ab树、红黑树、散点树或跳过列表。与LEDA**中使用的搜索树相比，a=2，b=16的ab树的速度最好

**S.纳伯。LEDA中搜索树数据结构的比较。个人沟通

Answer 2

首先使用一个平衡二叉搜索树的叶子版本，无论是红黑还是AVL。我用红黑色

获取Peter Brass关于高级数据结构的书，因为在几乎所有的标准算法/数据结构书中都很难找到这些叶树上的任何内容。我相信它们也被称为外生树

http://www-cs.engr.ccny.cuny.edu/~peter/

此外，您还可以查看Mehlhorn和Sanders的“算法和数据结构：基本工具箱”，该工具箱进入“排序序列”数据结构。当树木被使用时，他们只借助树叶树来创建这些。他们也是开发LEDA的一些人

另外，看看LEDA在线图书bc，它有一章介绍如何实现该算法以及如何处理所有“问题案例”我认为这是第9章，可能因为英语不是作者的母语，所以有点难理解。。。皮塔

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

您可以将叶节点数据项双重链接在一起，并且您已经创建了一个排序序列，其中树作为指向链接项列表的导航结构。这就是LEDA和in think CGAL如何做到的

重复项在事件队列中的处理方式与扫描行状态结构不同。对于事件队列，只需将项目的链接列表添加到叶中（参见Brass的书）。在这里，每个叶对应一个事件点，并且有一个包含所有段的列表，其起点和终点与事件点相同。因此，有些将有空列表，如交叉点事件点和结束事件点。至少有些实现是这样做的

用于扫描状态结构。重叠的平行段由段ID区分。他们不会在你正在阅读/参考的书中谈论这些。然而，LEDA的书告诉你如何处理这些问题。因此，尽管扫描状态树比较器说两个段具有相同的端点和方向，但比较器通过使用段数据库、数组或其他任何内容中的段索引打破了这种联系

还有一些更重要的观点：

台球积分！这个公共点池是基本的，然后组成段，并在所有数据结构中使用。使用该池可以通过测试标识来测试点的相等性！这避免了使用比较器，因为比较器会减慢速度并可能引入错误

关键是尽可能避免使用树比较器

当检查线段是否属于同一个束或是您有疑问的三个集合的成员（即扫描线上的开始、结束或兴趣点和事件点）时，不要使用比较器

相反，使用这样一个事实，即属于同一捆绑包的段可以在列表中具有某种“信息属性”，即当段与事件点相交时指向事件队列，或者如果段与后续项重叠，则指向列表中的后续项，否则指向空值。因此，您需要在事件队列和sweepline状态结构之间进行一些交叉链接。您的套件和捆绑包非常快速且容易找到。转到与状态树关联的链表的开头或结尾，并通过一个非常简单的测试逐项检查它

底线。获得正确的排序序列/平衡二叉树数据结构，并在实现Bentley Ottmann的其余部分之前进行大量工作

这是真正的关键，这本书没有指出这一点，但不幸的是，这不是它的意图，因为这个实现是棘手的。另外，请注意，本书在导航树的内部节点中增加了一个指向关联叶节点的额外链接。这只会使查找速度加快一点，但如果您不熟悉树叶树，则可能不明显。叶树中的键通常会在叶节点和树的内部节点的其他位置找到两次

国际泳联伊利

像LEDA/CGAL这样的软件包使用精确的算法使事情顺利进行。LEDA开发人员花了10年时间才把事情做好，这主要是由于使用了精确的算法。你也许可以用一个基本的交叉积测试来定位，但如果你需要一个精确的版本，那么你可以在他的网站上找到Jonathan Shewchuk教授的精确算术软件包

我猜你的书只是把这一切作为“读者/学生的练习”遗漏了哈哈