188宝金博页面版

基 于 BM N 算 法 的 几 点 改 进曾凡光熊运余苏玲( 四川大学计算机学院四川成都610064)I ■应用科掌【摘要】交点算法是计算几何的一· 个基本算法．也是我们实现空间关系的一个基础。对BM N 算法从两方面做改进，一方面单独解决BM N 算法的5种特殊情况：另一方面是利用原有的数据结构而不是重新创建新的结构，这样带来效率优势和提高了可移植性．【关键词】交点BM N 算法B M N算法的改进中图分类号：TP391文献标识码：A文章编号：1671- -7597( 2008)1120133一02一、引育交点算法是计算几何的一个基本算法，也是我们实现空间关系的一个基础。交点算法可以分成两类：空『日J划分算法和空间排序算法。空间划分算法的思路是：把平面划分成为若干区域．这些区域之『日J 没有重叠的部分，然后求得在每个区域内部线段的交点．空间排序算法是一种“ 输}{{敏感型” 算法，即算法的复杂度和输出结果紧密的联系在一起，这类算法的时间复杂度的下限足0(n*logn+1)，空『丑】复杂度是0(n)。这类算法典型的有3种：BO 算法，B M N 算法，梯形扫描算法。本文主要在B M N 交点算法基础上作了改进，对B M N算法作了两方面的改进：特别的考虑了．交点特殊情况的交迭。即针对重叠边和多线共点两种特殊情况的交迭的对B M N 算法做了补充：改进了底层实现的数据结构，尽量用标准库的结构，而不是针对算法设计的特殊的数据结构，这极大提高了算法的适性和壮健性。=、B M N 算法要保证B O算法的正确。必须对输入的线段做一些假定，这包括：I) 不存在垂直的线段( 平行F扫描线SL)；)共点的情况；(3)线段的端点不能相等；(5)不存在交迭( 有公共边)的线段。由于}：面的五种情况在实际中存在的可能性很大，所以B O算法不能在实际中直接使用。很多的学者针对这些特殊的情况对B O 算法提出了改进，其中疑有名的足8M N 算法。B M N 算法改进的主要思路是把特殊的情况和一般的情况同等看待，也就是说，上面B0算法所认为的特殊情况．在B M N 算法看来是和一般情况一样的“ 一等公民” 。B删算法的改进有二三个方面；( 1) X(( 2)不存在三线(或者更多线段( 4) 线段端点或者交点的x值不能相等：B O算法定义的事件点的全序关系，根据的是事件点的x值大。珺 M N 算法则根据事件点的字典的排序：首先比较点的X值大。俦冉蟳值的大小。经过这样的改进，算法可以处理第四种特殊情况，即线段端点或交点的x值相等。(2)Y —St ructure中线段的全序关系B M N 算法使用一个无穷小的概念从数学角度严格定义了扫描线SL．从算法的角度，可以认为BM N 算法是用扫描点(或者说扫描射线) 替代了扫描线的概念。每当遇到事件点的时候，扫描线就会改变，BO 算法认为sL的改变仪依赖于事件点的Y 值。BM N算法则认为sL的改变依赖f 整个事件点．( 3) 多线相交对于多线相交的情况，算法应该整体的交换它们的次序。从数据结构的角度来讲。为了满足算法的复杂度的要求，X _Structure和Y—St ruct ure需要动态平衡二又树结构。B M N算法的实现在文献中有详细的论述。三、改避的BM N 算法B M N 算法很好的解决，线段相交的特殊情况，但是在使用中我们也发现了一些不足，这主要体现在以下两个面的5种特殊情况，但是在有些情况下．这些特殊情况会出现交迭。B M N 算面：l ，B M N 算法单独的解决了上法并没有给予特别的考虑。2在数据结构方面，B M N 算法使用了大量的私有数据结构，例如排序队列、加权队列等等。这限制了它的实际使用。由于B 0算一法的核心数据结构是一个动态平衡二：叉树，这在C ++STL中已经存在，应该考虑使用这些结构，而不是重新构造，这样会带来更大的效率优势和可移植性。我们首先考虑第一种情况。即特殊情况的交迭，如下图：● ———● ——— ——叫● ———●ACBD线段A B和CD 重叠线段A B。C D 和EF相交于点I图表I 特殊情况的交迭：重叠边和多线相交考虑图表I中的I，线段AB 和线段cD存在重叠边。当扫描点到达C点的时候，BM N 算法找到经过C 点的所有线段AB 和cD ，然后输出^B 和cD 相交于C点：同样当扫描点到达B 点的时候，会输出^B 和cD 相交于B 点。一般来说，这正是我们期颦的结果，我们并不期望输出的交点位于C B 之阃。考虑l 璺I表I中的2，在图表l 中的l的基础上添加了一条线段EF，恰好经过A B与cD的公共边．交点是I。同样，C和B 会作为AB 和cD 的交点输出。当扫描点到达l的时候，AB ，cD 和EFi 条线段被查找到，I作为EF和AB ，EF和cD 的交点输出是正确的，但是作为AB 和cD 的交点输出一般就不是所期望的了。要剔除这种情况，只要检查两条线段是否重叠，并且交点不是端点就可以了．我们现在考虑第二个改进，即B M N 算法的数据结构。BO 算法最复杂的结构是动态平衡二叉树，C++STL 有几种在底层使用动态平衡二叉树的结构，例如set和m ap，如果能够使用这些结构来实现BM N 算法，会带来很大的效率优势和可移植性。为此，我们需要考察C ++STL提供的结构是古满足x—Str uctur e和Y—Str ucture的接口要求和时间复杂度要求。C++STL 提供了两类的动态平衡二叉树的结构，一类是简单的关联式容器：set和m ult is et ，另一类是结对的关联式容器：m ap和m ul ti m ap。如果只是存储线段，可以选择使用set或者咖lt iset，我们现在假定这样。至于在set 和m ult iset 之间选择，这依赖于线段本身的性质，如果不存在等价的线段( 等价不是完全相等，参见)，可以选择使用set ，我们现在也假定这样．x—Structur e的接口实现比较简单，参见附录的X —Str ucture的实现。Y —Str ucture的前两个接口i ns er t，erase是set 提供的标准接u，后两个接D above和bel ow。是s et 迭代器的景加( ++)和递减(～) 操作．对于最后一个接口，我们需要简单的审视一下set的特点和限制：1．对于插入、删除和查找操作，set 保证其时问复杂度都是0(109n)；．匝