Bentley

2024-07-09 10:57| 来源: 网络整理| 查看: 265

Bentley-Ottmann算法：求N条线段的交点 Bentley-Ottmann算法算法复杂度1. 使用暴力求解，遍历每一条线段 i ，固定 i 遍历 j 与 i 是否存在交点：2. 此时我们可以稍微优化一点算法复杂度，判断过 i, j 是否相交以后，j, i 就不用再判断了：3. Bentley-Ottmann算法算法案例（流程）1. 问题描述2. 名词介绍（1）Event Queue（事件队列）：后续用Q表示（2）Sweep Status（扫描线）：后续用L表示（3）交点：用 x i j x_{ij} xij 表示， i , j i, j i,j 表示相交的两条线段的下标 3. 案例讲解（1）排序：将所有端点按照 y y y 坐标大小进行排序，存在 Q Q Q 中，得到第 "-" 行。案例按照 y y y 从大到小排序（2）3个原子操作：a. 当扫描线扫描到线段初始点时，进行出队操作，取出队顶元素，判断相邻线段与当前线段是否相交。相交时将交点入队，将其插入到按 y y y 排序的队列中；b. 当扫描线扫描到线段交点时，将交点 x i j x_{ij} xij 进行出队操作，并且将 L L L 中对应的 i , j i,j i,j 交换位置，在重新判断 i , j i,j i,j 与各自相邻线段是否相交，相交时，将其插入到按 y y y 排序的队列中；c. 当扫描线扫描到线段末尾点时，将右端点进行出队操作，从 L L L 中将 s i s_i si 去除。此时判断与 s i s_i si 相邻的两个线段是否相交，相交时，将其插入到按 y y y 排序的队列中。（3）按照表格左侧 Event 来解析每一步的含义最后

Bentley-Ottmann算法

如果说你想知道这个方法的历史，那么推荐几篇远古论文：

来自Michael Ian Shamos和Dan Hoey在1976年发表的： M. I. Shamos and D. Hoey, “Geometric intersection problems,” 17th Annual Symposium on Foundations of Computer Science (sfcs 1976), 1976, pp. 208-215, doi: 10.1109/SFCS.1976.16. 上链接： http://euro.ecom.cmu.edu/people/faculty/mshamos/1976GeometricIntersection.pdf作者Bentley和Ottmann改进了上面的方法： Bentley and Ottmann, “Algorithms for Reporting and Counting Geometric Intersections,” in IEEE Transactions on Computers, vol. C-28, no. 9, pp. 643-647, Sept. 1979, doi: 10.1109/TC.1979.1675432. 上链接：http://www.itseng.org/research/papers/topics/VLSI_Physical_Design_Automation/Physical_Verification/DRC/Geometric_Intersection_Problems/1979-Bentley.pdf 算法复杂度

我们求N条线段中任意两条线段的交点的个数：

1. 使用暴力求解，遍历每一条线段 i ，固定 i 遍历 j 与 i 是否存在交点： // 暴力求解 for(int i = 0; i

【本文地址】

公司简介

联系我们