The problem I solved before required calculating interesections of line segments, but at that time, I only implemented naive algorithm for it.

After I read this good survey about Bentley-Ottmann algorithm, I'm so fascinated by this concept of *sweep line* and its subtlety around iteration procedure (coinductive?) and data structure.
So, here I made a simple implementation Bentley-Ottmann algorithm in Haskell: BentleyOttmann.hs.

# Algorithm Explanation

Given $n$ line segments and assuming those line segments make $k$ intersection points. This algorithm will loop for $2n + k$ times, which we call $s_1, ..., s_{2n + k}$ for each step. Each loop represents three types of special moments (events) where sweeping horizontal line comes across:

- left end of a line segment
- right end of a line segment
- intersection of two line segments

Obviously, we know nothing about such special moments beforehand, but the algorithm leads us so that we'll know what $s_{i + 1}$ is when we're in $s_i$. As an example, those loops are depicted as below:

Through each loop, we manage two types of collections, x-collection and y-collection. We also call those collections $X_i$ and $Y_i$ corresponding each loop index, respectively. We manage $X_i$ and $Y_i$ in the way they satisfy below:

$X_i$ keeps "possible" points (segment endpoints or interesections) which a sweep line will come across when it moves from $s_i$ to $s_{i+1}$

$Y_i$ keeps a horizontal order of line segments which intersect with a sweep line when it moves from $s_i$ to $s_{i+1}$

The time efficiency of this algorithm comes from the fact we'll maintain $X_i$ as small as possible. In fact, we're going to keep at most $3n - 1$ elements in $X_i$ by removing intersections of non-neighboring lines at each moment, then we only keeps at most $2n$ line endpoints and at most $n - 1$ line intersections.

# Implementation

Here is type definitions and main procedure from my implementation:

```
type Point = (Double, Double)
type Line = (Point, Point)
data XElem = LeftEnd Point Line
| RightEnd Point Line
| Intersect Point Line Line
type XColl = BT.BinTree XElem
type YColl = BT.BinTree Line
intersections :: [Line] -> [Point]
intersections lines =
let
initial = (xInitialize lines, yEmpty, []) :: (XColl, YColl, [Point]) -- <1>
finalResult = (`fix` initial) $ \loop (xcoll, ycoll, result) -> -- <2>
case xDropMin xcoll of -- <2.1>
Nothing -> result
Just (el, xcoll') ->
case el of
LeftEnd (x, _) l -> -- (i)
let
(ycoll', newNeighbors, newNonNeighbors) = yInsert x l ycoll
xcoll'' = updateXColl x newNeighbors newNonNeighbors xcoll'
in
loop (xcoll'', ycoll', result)
RightEnd (x, _) l -> -- (ii)
let
(ycoll', newNeighbors, newNonNeighbors) = yDelete x l ycoll
xcoll'' = updateXColl x newNeighbors newNonNeighbors xcoll'
in
loop (xcoll'', ycoll', result)
Intersect p@(x, _) l0 l1 -> -- (iii)
let
(ycoll', newNeighbors, newNonNeighbors) = ySwap x l0 l1 ycoll
xcoll'' = updateXColl x newNeighbors newNonNeighbors xcoll'
in
loop (xcoll'', ycoll', p:result)
in
finalResult
```

Explaining in natural language:

- initialize
*x-collection*with given line segments' endpoints- empty
*y-collection* - empty
*result*

- loop until x-collection is empty
- x-collection isn't empty, so you can take left-most element from it
- (i), (ii), (iii). update x-collection and y-collection depending on the type of taken element

- return result

How to update x-collection and y-collection (step 2 (a), (b), (c)) is explained graphically in the survey. So, I only shows one case at $s_4$ from the above example.

Point is that the point $(b)$ is removed from x-collection at $s_4$ since $l_2$ and $l_3$ are not neighboring each other when sweep line is going from $s_4$ to $s_5$.

# Subtlety

- Comparison function for lines in y-collection changes along with sweep lines moving. So, you need to accept such function as an argument for each operation of binary search tree (e.g.
`insertWith`

,`swapWith`

and`deleteWith`

). - I thought I can use heap (priority queue) for x-collection, but it turned out it requires arbitrary
*delete*operation in order to remove existing line intersection. So, I used binary search tree.