宾利奥特曼算法的推广 [英] The Generalization of Bentley-Ottmann Algorithm

问题描述

本特利-奥特曼算法被用于行的列表的确定的交点。但是这里提到在维基的，也有一些缺点：

Bentley-Ottmann Algorithm is used to determined the intersection point of a list of lines. However as mentioned here in Wiki, there are a few drawbacks:

该算法假定线   段不是垂直的，该行   段终点不撒谎其他   线段，该口岸是   通过仅两条线段形成的，并   没有两个事件点具有相同的   x坐标。然而，这些一般   位置的假设是不   合理的大多数应用   线段相交。

The algorithm assumes that line segments are not vertical, that line segment endpoints do not lie on other line segments, that crossings are formed by only two line segments, and that no two event points have the same x-coordinate. However, these general position assumptions are not reasonable for most applications of line segment intersection.

我的问题是有没有这种算法可以克服的一般化/克服上述困难？

My question is is there a generalization of this algorithm can overcome/overcome the above difficulties?

推荐答案

您链接到维基百科的文章对<一节href="http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm#Special_position_and_numerical_$p$pcision_issues">handling这些特殊的位置，这表明这些修改的基本算法：

The Wikipedia article you linked to has a section on handling these special positions, which suggests these modifications to the basic algorithm:

• 按照惯例，一个点是左的一个点垂直上方的;因此，垂直线的左的终点是它的下的终点。
• 的事件可能由两个的以上的线交叉的。
• 当到达一个事件点，其入射段必须的逆转的在扫描线（不只是交换，由于可能有两个以上）。
• 的交叉处理后，有可能的多于两个的旧的事件点被移除或多于两个的要被插入的新的事件点。

• By convention, a point is to the "left" of a point vertically above it; thus the "left" endpoint of a vertical line is its lower endpoint.
• Events may consist of the crossings of two or more lines.
• When an event point is reached, its incident segments must be reversed in the sweep line (not just swapped, as there may be more than two).
• After a crossing is handled, there may be more than two old event points to be removed or more than two new event points to be inserted.

这篇关于宾利奥特曼算法的推广的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！