用STL在C++中实现宾利-奥特曼

Question

我想在此描述的基础上，利用STL元素实现Bentley-奥特曼线段交叉算法.宾利-奥特曼维基百科

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

如果p是线段s的左端点，则将s插入T中。找到T中紧接s以下和s以上的分段r和t(如果它们存在)，如果它们的交叉在事件队列中形成了潜在的未来事件，则将其移除。如果s跨越r或t，则在事件队列中添加这些交叉点作为潜在的未来事件。

使用STL优先级队列作为事件队列似乎是不可能的，因为它的搜索复杂度是线性的，我需要查找和删除任何s和t的交叉。我应该使用集合吗？或者，是否可以使用优先级队列？

Answer 1

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

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

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