The Generalization of Bentley-Ottmann Algorithm

Question

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:

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?

Answer 1

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.

Answer 2

These are the modifications to the algorithm proposed by Skanthak here:.

The algorithm proceeds as follows: It first creates events for all start- and endpoints of input segments. It then handles all events in sorted order.
 For each event, it fetches the associated list L of segments starting at that point and finds and removes all segments in the search tree that intersect the current event point. It reports all those segments as intersections in that point. It then switches the order of the comparison function by changing the flag to be slightly after the current event. It reinserts all previously removed segments that do not have their endpoint at the current event point (because they have to be removed from the structure at this point anyways) and additionally insert the segments from L (that are starting at this point). It checks the top and bottom neighbors above and below the current event point for new intersections and adds them as event points if it finds any.
 This way the algorithm is robust against all kinds of degeneracies, including vertical segments and overlapping segments, as well as segments intersecting on their endpoints.

for all segments s do
  Create events for the endpoints of s
end for
while event queue not empty do
  Remove the smallest event point p from the queue
  Let L be the set of segments that start at p
  I ← all segments in the sweep line structure that contain p
  remove I from sweep line structure
  if |L| + |I| ≥ 2 then
     Report intersections of L ∪ I
  end if
  C ← {s ∈ I | p is not endpoint of s}
  Insert C in sweep line structure in reversed order
  Check for new intersections among segments above and below p
end while