平面扫描算法：如何对交点后的线段进行排序
Plane sweep algorithm: How to order the segments after intersection point
我正在尝试在 C++ 代码中实现基于本书的线段交叉点的平面扫描算法：http://www.cs.uu.nl/geobook/。他们建议使用平衡二叉搜索树来实现平面扫描的状态结构。
我正在使用 std::set 结构来实现状态结构，但我在重新排序包含点 "p" 且其上端点是点 "p".它们具有相同的坐标点，这意味着我无法将它们插入 std::set 中，因为它不允许重复值...我尝试将它们与它们的下端点一起插入，但随后，它们将丢失顺序它们与 "p".
下面的扫描线相交
书中的伪代码如下：
- Insert the segments in U(p) ∪C(p) into Tao. The order of the segments in Tao should correspond to the order in which they are intersected by
a sweep line just below p. If there is a horizontal segment, it comes
last among all segments containing p.
- (∗ Deleting and re-inserting the segments of C(p) reverses their order. ∗)
我不知道他们将如何颠倒顺序。当我在状态结构中插入段时，我按它们的 x 上端点坐标对它们进行排序。我不知道如何在交叉路口后交换他们的订单。
有什么想法吗？
更新：这本书在这里：https://books.google.com/books?id=C8zaAWuOIOcC 但有些页面没有出现。它在第 2 章第 24、25 和 26 页。希望它有助于提供一些上下文
最佳，
编写比较函数，使主要排序在 y 上，次要排序在 x 上。然后您可以插入具有重复 y 值的段，只要 x 不同即可。 （如果你有两个相同的段，你需要专门处理交叉测试）。
用作平面扫描状态数据结构的std::set的排序谓词必须按如下方式工作：
它必须（动态地）计算给定线段与扫掠线的交点坐标，作为扫掠线的当前位置。
在平局的情况下（当两个线段似乎在同一坐标处与扫掠线相交时）它还必须比较两个线段的角度 - 这将允许找出扫描线未来位置状态中的段。
请注意，上面的要求 1. 意味着谓词对象必须持有对扫描线位置变量的引用，以便它可以在扫描线前进时正确比较段。扫描线位置不能存储在谓词本身中，因为那样您将无法从您的算法中更新它（std::set 不通过引用提供对其谓词的访问）。
编辑
请注意，维护集合中段的正确顺序（即根据需要交换它们）的责任仍在算法中 - 具有此类谓词的 std::set 不会自动重新排序其元素。
当使用 std::set 时，在 共同 y 值 上出现两个或多个项目应该不是问题，假设您为 std::set。我建议，除了 y 值之外， 按斜率 进行比较和排序。
（std::set 的比较器示例）
我建议不要使用 std::set，而是使用 std::vector。使用 std::vector 可以交换 (std::swap) 对某些线段的引用，如果线段 starts/ends，也可以在 O(log n) 时间内交换 insert/remove，其中 n 是线段的数量。这个想法是，您通过交换与交叉点对应的线段，在整个线扫描过程中自己维护状态的正确顺序，只有事件队列是优先级队列。
（由于@Sneftel 的评论而被删除，感谢您的见解。）
关于扫掠线算法的一般方法：
状态 (sweep line status) 确实代表线扫描中特定（当前）时间线段的顺序。对于扫描线状态，在我的理解中，应该使用平衡二叉树（如@Sneftel 所述）。然后，您可以通过交换对应于交叉点的线段，在整个线扫描过程中自行维护状态的正确顺序，只有 event queue 必须是某种优先级队列。
我正在尝试在 C++ 代码中实现基于本书的线段交叉点的平面扫描算法：http://www.cs.uu.nl/geobook/。他们建议使用平衡二叉搜索树来实现平面扫描的状态结构。
我正在使用 std::set 结构来实现状态结构，但我在重新排序包含点 "p" 且其上端点是点 "p".它们具有相同的坐标点，这意味着我无法将它们插入 std::set 中，因为它不允许重复值...我尝试将它们与它们的下端点一起插入，但随后，它们将丢失顺序它们与 "p".
下面的扫描线相交书中的伪代码如下：
- Insert the segments in U(p) ∪C(p) into Tao. The order of the segments in Tao should correspond to the order in which they are intersected by a sweep line just below p. If there is a horizontal segment, it comes last among all segments containing p.
- (∗ Deleting and re-inserting the segments of C(p) reverses their order. ∗)
我不知道他们将如何颠倒顺序。当我在状态结构中插入段时，我按它们的 x 上端点坐标对它们进行排序。我不知道如何在交叉路口后交换他们的订单。
有什么想法吗？
更新：这本书在这里：https://books.google.com/books?id=C8zaAWuOIOcC 但有些页面没有出现。它在第 2 章第 24、25 和 26 页。希望它有助于提供一些上下文
最佳，
编写比较函数，使主要排序在 y 上，次要排序在 x 上。然后您可以插入具有重复 y 值的段，只要 x 不同即可。 （如果你有两个相同的段，你需要专门处理交叉测试）。
用作平面扫描状态数据结构的std::set的排序谓词必须按如下方式工作：
它必须（动态地）计算给定线段与扫掠线的交点坐标，作为扫掠线的当前位置。
在平局的情况下（当两个线段似乎在同一坐标处与扫掠线相交时）它还必须比较两个线段的角度 - 这将允许找出扫描线未来位置状态中的段。
请注意，上面的要求 1. 意味着谓词对象必须持有对扫描线位置变量的引用，以便它可以在扫描线前进时正确比较段。扫描线位置不能存储在谓词本身中，因为那样您将无法从您的算法中更新它（std::set 不通过引用提供对其谓词的访问）。
编辑
请注意，维护集合中段的正确顺序（即根据需要交换它们）的责任仍在算法中 - 具有此类谓词的 std::set 不会自动重新排序其元素。
当使用 std::set 时，在 共同 y 值 上出现两个或多个项目应该不是问题，假设您为 std::set。我建议，除了 y 值之外， 按斜率 进行比较和排序。
（std::set 的比较器示例）
我建议不要使用 std::set，而是使用 std::vector。使用 std::vector 可以交换 (std::swap) 对某些线段的引用，如果线段 starts/ends，也可以在 O(log n) 时间内交换 insert/remove，其中 n 是线段的数量。这个想法是，您通过交换与交叉点对应的线段，在整个线扫描过程中自己维护状态的正确顺序，只有事件队列是优先级队列。
（由于@Sneftel 的评论而被删除，感谢您的见解。）
关于扫掠线算法的一般方法：
状态 (sweep line status) 确实代表线扫描中特定（当前）时间线段的顺序。对于扫描线状态，在我的理解中，应该使用平衡二叉树（如@Sneftel 所述）。然后，您可以通过交换对应于交叉点的线段，在整个线扫描过程中自行维护状态的正确顺序，只有 event queue 必须是某种优先级队列。