algorithm - 扫线、交点降低点也是事件？

Question

您好，我正在尝试了解使用线扫描算法查找交叉点。但是我的书的作者与信息有点不一致，我知道我们将线段的上点添加为事件，我们将添加交点作为事件。但是当我们第一次创建事件列表时，在我们完全移动线之前，我们是否也将线段的较低点添加为事件？还是只有上点和交点有事件？

Answer 1

在算法的开始，您应该将段的两端添加到事件列表中。在扫描期间，当事件发生时，您将添加另一个事件(相应的段交集)。

在上面的点事件中，您正在向扫掠线添加线段。

在较低的点事件中，您正在从扫掠线中删除线段。

在交叉点事件中，您正在改变扫描线中线段的顺序。

当您在扫描线中插入、删除或更改部分的顺序时，您应该检查是否有新的交叉点。