Add Bentley-Ottmann algorithm

[juliohm]

The Bentley-Ottmann algorithm is a sweep-line algorithm for efficient pairwise segment-segment intersection in 2D space: https://youtu.be/nNtiZM-j3Pk?si=bwPt-btl2S0Ps8oO

I've started implementing this algorithm, but got stuck due to limitations in the AVLTree of the DataStructures.jl package. Below is the draft for future reference, in case someone finds the time to finish it up:

using Meshes
using DataStructures

"""
    bentleyottmann(segments)

Compute pairwise intersections between n `segments`
in O(n⋅log(n)) time using Bentley-Ottmann sweep line
algorithm.
"""
function bentleyottmann(segments)
  # adjust vertices of segments
  segs = map(segments) do s
    a, b = extrema(s)
    a > b ? reverse(s) : s
  end

  # retrieve relevant info
  s = first(segs)
  p = minimum(s)
  P = typeof(p)
  S = Tuple{P,P}

  # initialization
  𝒬 = AVLTree{P}()
  𝒯 = AVLTree{S}()
  ℒ = Dict{P,Vector{S}}()
  𝒰 = Dict{P,Vector{S}}()
  𝒞 = Dict{P,Vector{S}}()
  for s in segs
    a, b = extrema(s)
    push!(𝒬, a)
    push!(𝒬, b)
    haskey(ℒ, a) ? push!(ℒ[a], (a, b)) : (ℒ[a] = [(a, b)])
    haskey(𝒰, b) ? push!(𝒰[b], (a, b)) : (𝒰[b] = [(a, b)])
    haskey(ℒ, b) || (ℒ[b] = S[])
    haskey(𝒰, a) || (𝒰[a] = S[])
    haskey(𝒞, a) || (𝒞[a] = S[])
    haskey(𝒞, b) || (𝒞[b] = S[])
  end
  m = Point(-Inf, -Inf)
  M = Point(Inf, Inf)
  push!(𝒯, (m, m))
  push!(𝒯, (M, M))

  # sweep line
  I = Dict{P,Vector{S}}()
  while length(𝒬) > 0
    p = 𝒬[1]
    delete!(𝒬, p)
    handle!(I, p, 𝒬, 𝒯, ℒ, 𝒰, 𝒞)
  end
  I
end

function handle!(I, p, 𝒬, 𝒯, ℒ, 𝒰, 𝒞)
  ss = ℒ[p] ∪ 𝒰[p] ∪ 𝒞[p]
  if length(ss) > 1
    I[p] = ss
  end
  for s in ℒ[p] ∪ 𝒞[p]
    delete!(𝒯, s)
  end
  for s in 𝒰[p] ∪ 𝒞[p]
    push!(𝒯, s)
  end
  if length(𝒰[p] ∪ 𝒞[p]) == 0
    # n = search_node(𝒯, p)
  else
  end
end

We finished writing a better AVLTree in BinaryTrees.jl that is already registered: https://github.com/JuliaCollections/BinaryTrees.jl

Ideally, we can finish up the algorithm above with this new dependency instead.

The result of this function could be used in clipping algorithms such as the one in #1125.

cc: @souma4