知识卡片

普通读书笔记卡 · 8093.q.4 · 生成模型:未记录

扫描线在事件处更新活动顺序

理解等级:中级

将线段端点及发现的交点作为事件按扫描方向处理,活动集合维护与扫描线相交的线段顺序;新相邻线段可能产生未来交点,将其加入事件队列。事件发生时更新活动顺序并报告交点。

一般位置和合适平衡结构下,常见输出敏感复杂度为 O((n+k) log n),k为交点数;交点大量出现、重叠或多线共点时,需要明确输出定义及专门处理。

263强调少交点场景;大量交点时输出与事件维护开销增加,穷举实现虽然渐近不同,仍可能在小规模数据更简单或更快。

264用平衡树维护扫描线活动顺序与事件队列;比较器依扫描位置变化时,应在事件处按算法正确移除并重新插入相关线段,避免破坏树的不变式。

265的03423–03427维护事件点、扫描状态和线段集合;相同事件点需要合并,并在状态更新后检查邻居是否在后续位置相交。数值相等、多个线段同点与水平线段都需一致规则,否则可能漏报或重复。

266指出线性查找插入位置或线性查询事件成员会降低性能;优先队列可结合哈希表或索引支持成员检查,不必排除所有堆实现。

267说明事件队列最多 O(n+k) 个事件,活动集合最多n条线段;在一般位置与对数操作假设下,O((n+k) log(n+k)) 可化为 O((n+k) log n),因为线段对交点数至多 O(n²)。03428–03430实验展示交点多时管理常数可能使穷举更快。布丰投针公式还依针长不超过平行线间距等条件。

268指出存在性问题可以在找到第一个交点后终止;不同颜色线段交点是另一种有额外约束的变种。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 7 处

    • · 查看原书依据

      线段扫描算法是一个已经证明的高效算法,它在处理时关注数据的一个子集,而不是全部数据,这样能够提高效率。想象一下,扫描并且输出水平线L和输入线段的交点。图9-13是从上到下扫描时,线段L的状态。 图 9-13 在6条线段中检测到7个交点 线段扫描的创新在于将所有的线段从左至右按照y坐标进行排序[1]。

    • · 查看原书依据

      期望数目远远少于线段的个数时,此算法能够轻而易举地得到比穷举算法好很多的性能。如果有大量的交点,那么算法的记录管理功能会更加重要。

    • · 查看原书依据

      二叉平衡树,这样我们能够根据扫描线的某个点,得到线段的一个顺序。事件队列也可以是事件点的一棵二叉查找树。 为了简化算法的编码,二叉树通常使用一个增长平衡二叉树来表示扫描线状态,这棵树只有叶子节点才存储真正的信息。内部节点只是存储左子树中最左边线段和右子树中最右边线段的min和max信息。在这棵树中,

    • · 查看原书依据

      EventQueue和LineState类。 图 9-16 EventPoint类 图 9-17 LineState类 例9-3:线段扫描算法Java实现 EventQueue最开始存储2*n个EventPoint对象,每个对象存储的是以这个点为起点的ILineSegment(上部线段)和为终点的I

    • · 查看原书依据

      双向链表(一个能够快速找到前驱和后继线段的数据结构),那么由于需要在表中找到正确的插入位置,插入操作将会增加到O(s)。并且随着线段集S的增长,性能的退化需要引起更多的注意。 类似地,事件队列需要能够高效地查询某个事件点是否已经在队列中。使用基于堆的优先队列实现,在java.util.Priorit

    • · 查看原书依据

      O((n+k)log n)。 因为线段扫描算法的性能和输入的复杂程度有关(例如:交点的总数,任何时候扫描线维护的线段平均个数),我们使用特定的问题和输入数据来做算法的基准测试。我们现在讨论两个特定问题。 一个很有意思的数学问题是如何使用一些牙签和一张纸,计算π的一个近似值(叫做Buffon's ne

    • · 查看原书依据

      是否存在交点,而不是找出所有的焦点,这个算法在检测两个多边形是否相交时很有用,需要花费O(n log n)的时间。在平均情况下,这个算法能够快速地寻找到第一个交点。另一个变种则要处理这样的情况:输入的线段被标记为蓝色或者红色,我们只需要寻找到不同颜色线段之间的交点(Palazzi和Snoeyink,

    参考来源

    - 位置:《算法技术手册》第9章《线段扫描》(spine1655;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1618.html;u261-ch09-005)。 - 结论依据:261全文及03420–03422示意和伪代码实读。 - 原始内容:线段扫描算法是一个已经证明的高效算法,它在处理时关注数据的一个子集,而不是全部数据,这样能够提高效率。想象一下,扫描并且输出水平线L和输入线段的交点。图9-13是从上到下扫描时,线段L的状态。 图 9-13 在6条线段中检测到7个交点 线段扫描的创新在于将所有的线段从左至右按照y坐标进行排序[1]。 - 位置:《算法技术手册》第9章《使用环境》(spine1656;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1619.html;u263-ch09-005)。 - 结论依据:263强调少交点场景;大量交点时输出与事件维护开销增加,穷举实现虽然渐近不同,仍可能在小规模数据更简单或更快。 - 原始内容:期望数目远远少于线段的个数时,此算法能够轻而易举地得到比穷举算法好很多的性能。如果有大量的交点,那么算法的记录管理功能会更加重要。 - 位置:《算法技术手册》第9章《驱动因素》(spine1657;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1620.html;u264-ch09-005)。 - 结论依据:264用平衡树维护扫描线活动顺序与事件队列;比较器依扫描位置变化时,应在事件处按算法正确移除并重新插入相关线段,避免破坏树的不变式。 - 原始内容:二叉平衡树,这样我们能够根据扫描线的某个点,得到线段的一个顺序。事件队列也可以是事件点的一棵二叉查找树。 为了简化算法的编码,二叉树通常使用一个增长平衡二叉树来表示扫描线状态,这棵树只有叶子节点才存储真正的信息。内部节点只是存储左子树中最左边线段和右子树中最右边线段的min和max信息。在这棵树中, - 位置:《算法技术手册》第9章《解决方案》(spine1658;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1621.html;u265-ch09-005)。 - 结论依据:265的03423–03427维护事件点、扫描状态和线段集合;相同事件点需要合并,并在状态更新后检查邻居是否在后续位置相交。数值相等、多个线段同点与水平线段都需一致规则,否则可能漏报或重复。 - 原始内容:EventQueue和LineState类。 图 9-16 EventPoint类 图 9-17 LineState类 例9-3:线段扫描算法Java实现 EventQueue最开始存储2*n个EventPoint对象,每个对象存储的是以这个点为起点的ILineSegment(上部线段)和为终点的I - 位置:《算法技术手册》第9章《结论》(spine1659;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1622.html;u266-ch09-005)。 - 结论依据:266指出线性查找插入位置或线性查询事件成员会降低性能;优先队列可结合哈希表或索引支持成员检查,不必排除所有堆实现。 - 原始内容:双向链表(一个能够快速找到前驱和后继线段的数据结构),那么由于需要在表中找到正确的插入位置,插入操作将会增加到O(s)。并且随着线段集S的增长,性能的退化需要引起更多的注意。 类似地,事件队列需要能够高效地查询某个事件点是否已经在队列中。使用基于堆的优先队列实现,在java.util.Priorit - 位置:《算法技术手册》第9章《分析》(spine1660;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1623.html;u267-ch09-005)。 - 结论依据:267说明事件队列最多 O(n+k) 个事件,活动集合最多n条线段;在一般位置与对数操作假设下,O((n+k) log(n+k)) 可化为 O((n+k) log n),因为线段对交点数至多 O(n²)。03428–03430实验展示交点多时管理常数可能使穷举更快。布丰投针公式还依针长不超过平行线间距等条件。 - 原始内容:O((n+k)log n)。 因为线段扫描算法的性能和输入的复杂程度有关(例如:交点的总数,任何时候扫描线维护的线段平均个数),我们使用特定的问题和输入数据来做算法的基准测试。我们现在讨论两个特定问题。 一个很有意思的数学问题是如何使用一些牙签和一张纸,计算π的一个近似值(叫做Buffon's ne - 位置:《算法技术手册》第9章《变种》(spine1661;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1624.html;u268-ch09-005)。 - 结论依据:268指出存在性问题可以在找到第一个交点后终止;不同颜色线段交点是另一种有额外约束的变种。 - 原始内容:是否存在交点,而不是找出所有的焦点,这个算法在检测两个多边形是否相交时很有用,需要花费O(n log n)的时间。在平均情况下,这个算法能够快速地寻找到第一个交点。另一个变种则要处理这样的情况:输入的线段被标记为蓝色或者红色,我们只需要寻找到不同颜色线段之间的交点(Palazzi和Snoeyink,