c++ - 平面扫描算法 : How to order the segments after intersection point

Question

我正在尝试用 C++ 代码实现基于这本书的线段交叉点的平面扫描算法:http://www.cs.uu.nl/geobook/ .他们建议使用平衡二叉搜索树来实现平面扫描的状态结构。

我正在使用 std::set 结构来实现状态结构，但我在重新排序包含点“p”且其上端点是点“p”的段时遇到问题。它们具有相同的坐标点，这意味着我不能将它们插入到 std::set 中，因为它不允许重复值...我尝试用它们的下端点插入它们，但随后，它们将丢失其中的顺序它们与“p”正下方的扫描线相交。

书中的伪代码如下:

6. 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.
7. (∗ Deleting and re-inserting the segments of C(p) reverses their order. ∗)

我不知道他们将如何颠倒顺序。当我在状态结构中插入段时，我按它们的 x 上端点坐标对它们进行排序。我不知道如何在交叉路口后交换他们的订单。

有什么想法吗？

更新:这本书在这里:https://books.google.com/books?id=C8zaAWuOIOcC但有一些页面没有出现。它在第 2 章第 24、25 和 26 页。希望它有助于提供一些背景信息

最好的，

Answer 1

当使用 std::set 时，公共(public) y 值 上的两个或多个项目的出现应该不是问题，假设您使用合适的比较器标准::设置。我建议，除了 y 值之外，按斜率进行比较和排序。 (std::set 的比较器示例)

我建议不要为它使用 std::set，而是像 std::vector 这样的东西。使用 std::vector 可以交换 (std::swap) 对某些线段的引用，如果线段开始/结束，还可以在 O(log n) 时间内插入/删除，其中 n 是线段的数量。这个想法是，您通过交换与交叉点对应的线段，在整个线扫描过程中自己维护状态的正确顺序，只有事件队列是优先级队列。 (由于@Sneftel 的评论而被删除，感谢您的见解。)

关于扫描线算法的一般方法: 状态 (sweep line status) 确实代表线段在特定(当前)时间在您的线扫描中的顺序。对于扫描线状态，在我的理解中，应该使用平衡二叉树(如@Sneftel 所述)。然后，您可以通过交换与交叉点对应的线段，在整个扫线过程中自行维护状态的正确顺序，只有事件队列必须是某种优先级队列。