扫描线多边形三角剖分：如何找到当前顶点的左边？
Sweep Line Polygon triangulation: How to find edge left to current vertex?
我目前正在编写一个 y 单调扫描线算法来对非凸多边形进行三角剖分。
实现这一点的第一步是使多边形 y 单调。
MakeMonotone 的伪代码，来自“Mark de Berg 的计算几何”一书 (https://archive.org/details/computationalgeo00berg)：
现在回答我的问题：
在那本书和我找到的所有其他网站中，没有解释如何对提到的“二叉搜索树 T”中的边进行精确排序。参考书中唯一提到的是“T的叶子从左到右的顺序对应边的从左到右的顺序”。但是 properties/attributes 树中的边是根据什么排序的？
我也不清楚边应该如何在二叉树中表示（起点？终点？两者的组合？）。
我最天真的方法是找出 T 中的所有边与扫掠和线的交点，并计算它们中哪一个最接近当前顶点。但是考虑到在每个 book/university 幻灯片中，T 的内部工作没有进一步解释，它一定更容易。
二叉搜索树应该支持以下操作：
- 插入一条新边
- 查找扫掠线上当前顶点左侧的边
- 删除一条边
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 处于活动状态的所有边排序。
不过，这是一个 hack。这里有效且正确的方法是在边上不使用排序函数，只使用将顶点与边进行比较的函数。
我目前正在编写一个 y 单调扫描线算法来对非凸多边形进行三角剖分。 实现这一点的第一步是使多边形 y 单调。
MakeMonotone 的伪代码，来自“Mark de Berg 的计算几何”一书 (https://archive.org/details/computationalgeo00berg)：
现在回答我的问题：
在那本书和我找到的所有其他网站中，没有解释如何对提到的“二叉搜索树 T”中的边进行精确排序。参考书中唯一提到的是“T的叶子从左到右的顺序对应边的从左到右的顺序”。但是 properties/attributes 树中的边是根据什么排序的？ 我也不清楚边应该如何在二叉树中表示（起点？终点？两者的组合？）。
我最天真的方法是找出 T 中的所有边与扫掠和线的交点，并计算它们中哪一个最接近当前顶点。但是考虑到在每个 book/university 幻灯片中，T 的内部工作没有进一步解释，它一定更容易。
二叉搜索树应该支持以下操作：
- 插入一条新边
- 查找扫掠线上当前顶点左侧的边
- 删除一条边
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 处于活动状态的所有边排序。
不过，这是一个 hack。这里有效且正确的方法是在边上不使用排序函数，只使用将顶点与边进行比较的函数。