Bentley-Ottmann线段求交算法

发表于 更新于 分类于 阅读次数： 本文字数： 456 阅读时长 ≈ 2 分钟

因为很喜欢我的伪代码所以备份一下

条件

  • 全部都是直线段
  • 没有重合的线段
  • 线段端点不重合
  • 没有三条及以上线段在同一点相交

基本算法思路

  1. 事件点优先队列Q
    将所有线段的端点作为事件点，分为起点和终点，按x坐标排序，若x坐标相同则按y坐标排序。使用一个红黑树存储点指针。
  2. 扫描线状态活动集S
    使用一个平衡二叉搜索树来维护当前扫描线与线段，按线段在扫描线上的y坐标排序。每当扫描线经过一个事件点时，更新树的状态。

    由于std::set底层不支持动态更新key值，所以自己实现了平衡搜索树。

  3. 处理事件点 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    //处理事件点伪代码 
    while(Q非空)
     {
         弹出事件点p;
         switch(p的类型)
         {
         case 起点:
             p的关联线段l插入到S;
             if(l的上邻居与l相交)
                 计算交点并插入Q;
             if(l的下邻居与l相交)
                 计算交点并插入Q;
             break;
         case 终点:
             if(l的上邻居与l的下邻居相交)
                 计算交点并插入Q;
             l从S中删除;
             break;
         case 交点:
             交点关联的两条线段为l1和l2;
             交换l1和l2在S中的位置;//设定交换后l1在上，l2在下
             if(l1的上邻居与l1相交)
                 计算交点并插入Q;
             if(l2的下邻居与l2相交)
                 计算交点并插入Q;
             break;
         }
     }
  4. 拆分线段
    记录每个线段对应的事件点指针。如果数量大于2，将线段删除并拆分成多个线段，重新插入到原链表中。

剩下的是付费内容（）