c++ - 使用 STL 在 C++ 中实现 Bentley-Ottmann

Question

我想基于此描述，使用 STL 元素实现 Bentley-Ottmann 线段交叉算法。 Bentley-Ottmann Wikipedia

我正在苦苦挣扎的是优先队列的实现。描述要求我删除任何交叉点:

If p is the left endpoint of a line segment s, insert s into T. Find the segments r and t that are immediately below and above s in T (if they exist) and if their crossing forms a potential future event in the event queue, remove it. If s crosses r or t, add those crossing points as potential future events in the event queue.

似乎不可能使用 STL 优先级队列作为事件队列，因为它的搜索复杂度是线性的，我需要找到并删除 s 和 的任何交叉>t。我应该改用一套吗？还是可以使用优先队列？

Answer 1

您可以从中快速删除优先级队列结构，但它们需要大量额外的内存。

实际上只将 r-t 交集留在队列中效率更高。然后，当需要处理事件时，如果它无效(因为 r 和 t 不相邻)或者如果它已经完成，则忽略它。

为了检测 r-t 何时已经完成，只需确保您的优先级队列按总排序排序，即不要只比较事件的 x 值。当多个事件具有相同的 x 值时，使用所涉及的段的标识符来打破平局。然后，当 r-t 在队列中出现多次时，所有出现的都在一起，你可以按顺序将它们全部弹出。