我正在尝试根据这本书在 C++ 代码中实现线段相交的平面扫描算法：http://www.cs.uu.nl/geobook/ http://www.cs.uu.nl/geobook/。他们建议使用平衡二叉搜索树来实现平面扫描的状态结构。
我正在使用 std::set 结构来实现状态结构，但在重新排序包含点“p”且其上端点是点“p”的段时遇到问题。它们具有相同的坐标点，这意味着我无法将它们插入到 std::set 中，因为它不允许重复的值...我尝试用它们的下端点插入它们，但是随后，它们将丢失其中的顺序它们与“p”下方的扫描线相交。
书中的伪代码如下：
- 将 U(p) ∪C(p) 中的线段插入到 Tai 中。道中线段的顺序应与它们相交的顺序相对应
p 下方的扫描线。如果有水平线段，它就会出现
所有包含 p 的段中的最后一个。
- （* 删除并重新插入 C(p) 的段会颠倒它们的顺序。*）
我不知道它们将如何反转顺序。当我在状态结构中插入段时，我将按它们的 x 上端点坐标对它们进行排序。我不知道在交叉路口后如何交换他们的顺序。
任何想法？
更新：这本书在这里：https://books.google.com/books?id=C8zaAWuOIOcC https://books.google.com/books?id=C8zaAWuOIOcC但有一些页面没有出现。它位于第 2 章第 24、25 和 26 页。希望它有助于提供一些背景信息
Best,
使用时std::set两个或多个项目的外观共同 y 值应该不是问题，假设您使用合适的比较器std::set。我建议，除了 y 值之外，按斜率比较和排序。
（比较器的示例std::set https://stackoverflow.com/questions/2620862/using-custom-stdset-comparator)
I would suggest not to use std::set for it but something like std::vector. Using std::vector enables you to swap (std::swap) the references to certain line segments and also insert/remove in O(log n) time if a line segment starts/ends, where n is the number of line segments. The idea is that you maintain the correct order of the status yourself throughout the line sweep by swapping the line segments that correspond to an intersection, only the event queue is a priority queue.
(Removed due to the comment of @Sneftel, thanks for the insight.)
关于扫描线算法的一般方法：
状态（sweep line status) 确实代表线扫描中特定（当前）时间的线段顺序。对于扫描线状态，根据我的理解，应该使用平衡二叉树（如@Sneftel所述）。然后，您可以通过交换与交点对应的线段，在整个线扫描过程中自己保持状态的正确顺序，仅event queue必须是某种优先级队列。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
