Bentley-Ottmann算法的推广
Bentley-
Ottmann算法用于确定线列表的交点。但是，如Wiki此处所述，存在一些缺点：
该算法假定线段不是垂直的，线段的端点不位于其他线段上，交叉仅由两个线段形成，并且没有两个事件点具有相同的x坐标。但是，这些一般位置假设对于线段相交的大多数应用是不合理的。
我的问题是该算法是否可以克服/克服以上困难？
回答：
您链接到的Wikipedia文章包含有关处理这些特殊位置的部分，该部分建议对基本算法进行以下修改：
- 按照惯例，一个点位于垂直上方的点的“左侧”。因此，垂直线的“左”端点是其 下 端点。
- 事件可能包括两条 或更多 条线的交叉。
- 当到达事件点时，其入射段必须在扫描线中 反转 （不能交换，因为可能会超过两个）。
- 处理过境后，可能要删除 两个 以上的旧事件点，或者要插入 两个以上的 新事件点。
以上是 Bentley-Ottmann算法的推广 的全部内容， 来源链接： utcz.com/qa/414988.html
