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).

Fluid between Two coaxial cylinders

Consider a non-viscous incompressible fluid lies between two coaxial cylinders . The domain occupied by the fluid is defined as $ 0<z<\xi$ , $ A<r<B$ The coaxial cylinders slowly rotate arround their z-axis with angular velocity $ \Omega$ Suppose that the height of this fluid at rest is H and the density $ \rho$ of the fluid is constant enter image description here

We use cylinderical coordinates $ $ \vec{V}=V_r \hat{e_r} +V_{\theta} \hat{e_{\theta}}+V_{z} \hat{e_z}$ $

My Question is about the boundary conditions

I have on the outer cylinder $ V_r =0$

Is there any conditions on the inner cylinder ?

RegionDifference not working with one Cuboid and large number of embedded cylinders

I am trying to create a Cuboid with embedded hollow cylindrical regions. It seems to work fine when I use a relatively small number of cylinders (about 20) but does not work when I use a large number of cylinders (typically more than 40). In my real application I need more than 100.

Any help would be greatly appreciated!

Herewith, please find the codes I used:

Clear[rcoord, matr, pts1, pts2, cyl3, regCyl3, matDiff] (* create a list of 3 pseudorandom reals between 0 and 1 *) rcoord := RandomReal[1., 3] (* generates the filled RVE cuboid *) scl2 = 0.1; matr = BoundaryDiscretizeGraphics[    Cuboid[{0, 0, 0} + {scl2, scl2, scl2}, {1, 1, 1} - {scl2, scl2,        scl2}]];  (* generate a list of random cylinders within Cuboid *) cylTot = 100;   (* total number of random cylinders *) cylRem = 20;  (* number of random cylinders to remove from cuboid *) pts1 = Table[rcoord, {cylTot}]; pts2 = Table[rcoord, {cylTot}]; rad = 0.02; cyl3 = Table[   Cylinder[{pts1[[i]], pts2[[i]]}, rad], {i,     Length[pts1]}];   (* list of all cylinders *) regCyl3 =   Table[BoundaryDiscretizeGraphics[cyl3[[i]]], {i, 1,     Length[cyl3]}];   (* list of all cylinderical regions *)  (* generate the hollow RVE cuboid by removing random cylinders from \ Cuboid *) (* works when I remove a small number only, typically less than \ 40  cylinders *) matDiff =   RegionDifference[matr,    regCyl3[[1]]];   (* remove first cylnderRegion from Cuboid *) matDiff = Fold[(RegionDifference[#1, #2]) &,   matDiff,    regCyl3[[2 ;;      cylRem]]];  (* remove rest of cylnderRegions from Cuboid *) HighlightMesh[matDiff, Style[2, Opacity[0.5]]] RegionPlot3D[matDiff, PlotStyle -> Directive[Yellow, Opacity[0.5]],   Mesh -> None] 

But I get error messages when I use a large number of Cylinders:

(* create new derived region by removing random cylinders from Cuboid \ *) (* Does not work when I try removing a large number of cylinders, \ typically more than 40 *) Clear[matDiffAll, cylRemAll]; cylRemAll = 60; matDiffAll =    RegionDifference[matr,     regCyl3[[1]]];   (* remove first cylnderRegion from Cuboid *) matDiffAll = Fold[(RegionDifference[#1, #2]) &,   matDiffAll,    regCyl3[[2 ;;       cylRemAll]]];  (* remove rest of cylnderRegions from Cuboid *) HighlightMesh[matDiffAll, Style[2, Opacity[0.5]]] RegionPlot3D[matDiffAll, PlotStyle -> Directive[Yellow, Opacity[0.5]],   Mesh -> None]