geometry - 扫描线多边形三角剖分 : How to find edge left to current vertex?

Question

我目前正在编写一个 y 单调扫描线算法来对非凸多边形进行三角测量。
实现这一点的第一步是使多边形 y 单调。MakeMonotone的伪代码来自“Mark de Berg 的计算几何”一书(https://archive.org/details/computationalgeo00berg):

现在我的问题:
在我找到的那本书和所有其他网站中，没有解释如何对提到的“二叉搜索树 T”中的边进行精确排序。引用书中唯一提到的是“T的叶子的从左到右的顺序对应于边的从左到右的顺序”。但是该树中的边是根据什么属性/属性排序的？
我也不清楚，应该如何在二叉树中准确表示边(起点？终点？两者的组合？)。
我最天真的方法是找出 T 中所有边与扫描和线的交点，并计算它们中哪一个最接近当前顶点。但是考虑到在每本书/大学幻灯片中，都没有进一步解释 T 的内部工作原理，它肯定要容易得多。
二叉搜索树应支持以下操作:

插入一条新边

查找当前位于扫描线上的顶点左侧的边

移除边

Answer 1

T用于直接查找查询点左侧的边。所以 T 中的边缘需要水平排序。T上的关键查询是找到一个点左边的边。对于树中的任何边，找到与该点的 y 坐标相对应的边的 x 位置，并将其与该点的 x 坐标进行比较。 (或者，由于树中仅存储左边界，因此您可以直接在点的坐标上评估边的隐式方程，然后查看结果是负数还是正数。)
在该算法中，通过执行这样的查询然后直接在查询返回的边之后插入新边来完成对 T 的插入。
与二叉树的大多数其他用法相比，没有办法将数字“键”与每个节点相关联并按键排序。如果您想要一个可用于排序的不可变函数，您可以执行以下操作:

def less(e1, e2):
    yMin = max(e1.begin.y, e2.begin.y)
    yMax = min(e1.end.y, e2.end.y)
    y = (yMin + yMax) / 2
    return e1.xAtY(y) < e2.xAtY(y)

这依赖于该算法中的边已知为不相交的事实，以及仅在两条边都处于事件状态时才使用比较的事实；它不是对所有边的排序，只是在特定 y 处事件的所有边上排序。
不过，这是一个黑客。这里有效且正确的方法是在边上没有排序函数，只有一个将顶点与边进行比较的函数。