平面扫描算法：如何在交点之后对线段进行排序

Question

3

我正在尝试在C++代码中实现基于此书的线段相交平面扫描算法。他们建议使用平衡二叉搜索树来实现平面扫描的状态结构。

我使用std :: set结构来实现状态结构，但我遇到了问题，无法重新排序包含点“p”的线段及其上端点为点“p”的情况。它们具有相同的坐标点，这意味着我不能将它们插入std :: set，因为它不允许重复值...我尝试使用它们的下端点将其插入，但是，它们将失去通过“p”下方的扫描线相交的顺序。

书中的伪代码如下：

1.将U(p)∪C(p)中的线段插入Tao。Tao中线段的顺序应与它们被扫描线从下方相交的顺序相对应。如果有一个水平线段，则它将出现在包含p的所有线段的最后。

2.（*删除和重新插入C(p)的线段会颠倒它们的顺序。*）

我不知道它们将如何颠倒它们的顺序。当我将线段插入状态结构时，我按其x上端点坐标进行排序。我不知道如何在相交后交换它们的顺序。

有任何想法吗？

更新：书在这里：https://books.google.com/books?id=C8zaAWuOIOcC，但有些页面不显示。它在第2章的24、25和26页。希望它可以提供一些背景

最好的祝福

- andrestoga

3个回答

-2

编写比较函数，使主要排序在y上，次要排序在x上。然后，只要x不同，就可以插入具有重复y值的段。（如果您有两个相同的段，您需要为交点测试特别处理）。

- Malcolm McLean

是的，问题在于当您有多个具有相同上端点（相同的x和y坐标）的线段时，如何在状态结构中对它们进行排序？ - andrestoga

-2

std::set用作平面扫描状态数据结构的排序谓词必须按照以下方式工作：

请注意，上述要求1意味着谓词对象必须持有对扫描线位置变量的引用，以便随着扫描线的推进正确地比较线段。扫描线位置不能存储在谓词本身中，因为然后您将无法从算法中更新它（std::set不提供对其谓词的引用访问）。

编辑

请注意，维护集合中线段的正确顺序（即根据需要交换它们）的责任仍然在于算法 - 具有此类谓词的std::set不会自动重新排序其元素。

- Leon

1

这不是一个好方法。std::set需要一个比较器，它的输出不能随时间改变，违反这一点将会导致错误。仅仅因为std::set是使用平衡二叉树实现的，并不意味着它可以用作原始平衡二叉树;扫描线算法使用它的方式需要手动交换而不是排序函数，并且std::set并没有为此设置。 - Sneftel

@Sneftel 我从未意味着 std:set 会自动维护状态中段的正确顺序。在处理交点事件时，您仍然需要交换这些段。 - Leon

1

这不仅仅是维护正确的顺序。std::set 不希望其比较函数发生变化。如果它发生了变化，你的程序很可能会崩溃。 - Sneftel

@Sneftel 如果比较函数的更改不影响集合中元素的当前顺序，为什么程序会崩溃？ - Leon

它在你特定的情况下有效，但这仍然违反了标准。尽管我认为如果你删除所有相交的段，后门更改比较，然后重新插入相交的段，它就会符合标准（虽然实现起来很复杂，比正常算法慢）。 - Sneftel

显示剩余7条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gue · Accepted Answer

当使用 std::set 时，假设你使用适合于 std::set 的比较器，两个或多个项目在 公共 y 值 上的出现不应该是一个问题。我建议，除了 y 值之外，按斜率进行比较和排序。

（std::set 的比较器示例）

关于扫描线算法的一般方法：

状态（扫描线状态）代表了在扫描线上某个特定时间的线段顺序。对于扫描线状态，在我的理解中，应该使用平衡二叉树（如 @Sneftel 所提到的）。然后，你可以通过交换与交点相对应的线段来自己维护正确的状态顺序，在整个扫描线过程中保持正确的状态顺序，只有 事件队列 必须是某种优先级队列。