3D intersection algorithm for cylinders


The problem

Input is a list of $ N$ cylinders in 3D space, and output should be a list of $ M≤N(N-1)/2$ pairs of cylinders that intersect. ($ M$ depends on input data, obviously.)

If it matters, the cylinders are very thin (diameter less than 1% of the length for all cylinders), and a solution for “rounded cylinders” would work for me (it probably simplifies the geometry calculations). A “rounded cylinder” is a cylinder with half-spheres at the extremities; formally, for a start point $ S$ , an endpoint $ E$ and a radius $ r$ , the rounded cylinder $ (S, E, r)$ is defined as the set $ \{P|∃ Q ∈ [S,E], ||PQ|| ≤ r\}$ .

The obvious solution

It is easy enough to do in $ O(N^2)$ time and $ O(max(M, N))$ space: the pseudocode of my current implementation is (for rounded cylinders):

Ncyl = length(cylinder_list) output = {} for i = 1, 2, ... Ncyl:   for j = i+1, i+2, ... Ncyl:     (S1, E1, r1) = cylinder_list[i]     (S2, E2, r2) = cylinder_list[j]     find P∈[S1, E1], Q∈[S2, E2] such that ||PQ|| is minimal  # this is the costly line, says the profiler     if ||PQ|| < r1 + r2:       add (i, j) to output return output 

Better performance?

Any algorithm will have a (time and space) worst-case in $ O(N^2)$ (at least) because the output list can itself be of that length. However, the above algorithm guarantees $ O(N^2)$ time even on “friendly” data because it tests all possible intersections.

In my use case, the cylinders are fairly spread apart in space (the longest cylinder is less than one tenth of the diameter of the whole set of cylinders). Furthermore, they occupy a small fraction of space and $ M\sim N$ (for values of $ N$ up to 2000 or so, above that it times out). This suggests to me that there could be an improvement by some “sweeping plane” algorithm similar to Bentley-Ottmann. However, I did not find a straightforward way to do Bentley-Ottmann in 3D (in 2D after sweeping you end up ordering points on a line which is easy enough, but in 3D there is no obvious ordering for a plane).