Bentley-Otmann Algorithm: Main Page

This project implements Bentley-Ottmann's algorithm. For a set of segment lines, it computes and returns all the intersections of segment lines of this set. In order to do that, we use the generalized algorithm given in M.de Berg, 0.Cheong, M.van Kreveld and M.Overmars, Computational Geometry: Algorithms and Applications, Third Edition.

This algorithm is based on the principle of sweeping line. We sweep a line from the left to the right (in some papers, it can be found from the top to the bottom) in the 2D plan. At every position of the line, the intersections on the left of the line has been computed and those on the right are waiting to be treated. The interesting positions for the sweeping line are the endpoints of the segment lines of the set and the crossing points. We call those points events.

We treat each event in a natural way :

if it is a left endpoint of a segment line, this segment line can now potentially be involved in an intersection.
if it is a right endpoint of a segment line, we don't have to care about this segment line anymore : all the intersections that involves this segment line are on the left of th sweeping line, so already computed.
if it is a crossing point of two or more segment, we compute this intersection and move on.

(Of course, a single event can be of more than one type.)

In order to realize that, we have to maintain two structures : one which gives the presently involved segment (those which are crossing the sweeping line) called the Y-structure and one giving the next event at every time called the X-structure. Since we want to compute all the intersections with a time complexity $O((n+k) \log n)$ with $ n,k $ respectively the number of segments and the number of intersections, we have to compute all the actions on the X,Y-structures with a time complexity $O(\log n)$ . Naturally, we choose to work with some trees. The X-structure is a priority queue determining the next event at every time. For some algorithmic reasons (we want to be able to know if an object is a member of the X-structure in a logarithmic way), we will use a binary search tree with the lexographic order on the (x,y)-coordinates of the events. For the Y-structure, a binary search tree is a natural choice to order the segment, insert and remove them.

An example of event with the three types of treatment.

At start, we push in the queue all the events corresponding to the endpoints of the segment lines of the set. Then, for each event :

we denote $\mathcal L$ the set of segment having the current event as left endpoints. (We suppose that this set is stored with the event to keep our time complexity.)
Finding all segment lines in the binary search tree that contains the event point, we partition those in $\mathcal R$ , which is the set of the segment lines having the event point as right endpoint, and $\mathcal I$ , which is the set of those strictly containing the event point.
If $\mathcal L \cup \mathcal I \cup \mathcal R$ contains strictly more than one element, we can report one intersection.
We now delete from the binary search tree the segment lines in $\mathcal I \cup \mathcal R$ (those from $\mathcal R$ because we does not need them anymore ; those from $\mathcal I$ to exchange the order on them when re-inserting)
It remains to treat the possibly new events introduced by the segment lines from :
- if $\mathcal L \cup \mathcal I = \emptyset$ (i.e. the event point was just a right endpoint of some segment lines, but was no left endpoint nor crossing point), then we find s and s' the segment immediately above and below the event point and check for any intersection between them ; if there is one greather than the current event and not already in the events's queue, then we push it.
- Else we find the lower segment line of $\mathcal L \cup \mathcal I$ s and the upper one s' ; searching for the below neighboor r of s and the above one r' of s', we check and insert if necessary any new intersection between r and r'.

(Of course, the several researches for neighboors depend of the existence of those neighboors. If they don't, we just have nothing to do relatively to it.)

The files bentley_ottmann.hpp and bentley_ottmann.cpp implement this algorithm. structures.hpp deals with the X,Y-structures using the STL and some customizations. All of that depends of a representation of some geometric objects, what is done in geometry.hpp and geometry.cpp.