c++ - 线段相交平面扫描算法中状态结构的使用

Question

我想在平面扫描算法中实现状态结构。我的扫描线在 y 方向上从上到下移动。

目前我正在使用 set(在 C++ 中预定义)根据 x 值存储段。

当扫描线向下移动时，每个段的 x 值发生变化，因此集合中的顺序应该改变，但是集合中的搜索键一旦添加就不能修改所以我的 x 值一旦分配就不会改变所以每次我移动到下一个事件点我必须删除完整的树并使用新的 x 值创建新树。

我的 segmentation 结构是:

struct Segment
{
    double x1;
    double x2;
    double y1;
    double y2;
    int name;
    double x;
    double y;
};

如何更新集合中的 x 值？

Answer 1

std::set 一般实现为红黑树。树中元素的顺序是通过将元素对传递给存储在 set 中的比较函数来控制的；在插入期间检查元素在排序顺序中的位置，并假定此后不会更改。 (您可能已经知道所有这些......只是提供一些背景知识。)

平面扫描算法通常还使用自平衡树作为其状态结构，例如红黑树。然而——相似之处仅此而已。状态结构中的元素(段)没有固有的整体顺序；顺序是根据特定的 y 坐标定义的，并将随 y 坐标而变化。最重要的是，在交叉事件点，两个段将交换位置，这种操作对于 std::set 甚至没有意义。

底线:std::set 和其他排序容器类通常不适合实现平面扫描算法的扫描状态，即使底层数据结构是合适的。您应该使用较低级别的直接公开的红黑树实现，这将允许您交换元素。