Hans, I'm not really sure but I think the answer is no. As Sander points out, Nearest already has its own internal analog to sorting. Ordering by y or other values is not likely to offer much unless one can find a way to make it cooperate with calls to a NearestFunction. I don't know how to do that (which does not mean it can't be done).

@ Daniel: Very cool. I gave it a vote. And I think it leaves more opportunities than the image-processing, but that may be wrong.

Could one gain additional speed if ordering the sticks according to their - say - y-coordinate?

Thanks Daniel, very nice addition! Wasn't comfortable enough so as to implement your binning suggestion in the code (new to Community, and not entirely familiar how one should use/credit others). The VertexShape function seems to be dependent on VertexSize for some reason and that's why you only obtain the nodes and not the sticks, I believe. I had to deduce it empirically as 250 for my n=250 case (it doesn't seem to always vary linearly with n though).

Huge difference in speed! wow! I wouldn't have thought it would be that much! Nice code!

Going off of the ideas of treating this as a Graph and the geometric intersections Daniel and Sanders proposed above respectively. I use the same setup as the initial question by the user in the attachment, I just change n to 250 (to get percolation in both x and y directions from edge nodes).

We find the intersections of line segments explicitly by modifying the determinants method, (as given by the Mathworld page). given both in uncompiled and compiled versions for comparison:

lineIntersections[{a_, b_}, {c_, d_}] := 
 Block[{detBottom = Det[{a - b, c - d}], pt},
  If[Chop[detBottom] == 0, Infinity, 
   pt = ((Det[{a, b}] (c - d) - Det[{c, d}] (a - b))/detBottom);
   If[Sign[b - a] == Sign[b - pt] && Sign[a - b] == Sign[a - pt] && 
     Sign[d - c] == Sign[d - pt] && Sign[c - d] == Sign[c - pt], pt, 
    0]]]

lineIntComp = Compile[{{u, _Real, 2}, {v, _Real, 2}},
   Block[{a = u[[1]], b = u[[2]], c = v[[1]], d = v[[2]], pt, 
     detBottom},
    detBottom = 
     u[[2, 2]] (v[[1, 1]] - v[[2, 1]]) + 
      u[[1, 2]] (-v[[1, 1]] + v[[2, 1]]) + (u[[1, 1]] - 
         u[[2, 1]]) (v[[1, 2]] - v[[2, 2]]);
    If[Chop[detBottom] == 0, {10^6, 10^6}, 
     pt = ({(-u[[1, 2]] u[[2, 1]] + u[[1, 1]] u[[2, 2]]) (v[[1, 1]] - 
             v[[2, 1]]) + (u[[1, 1]] - 
             u[[2, 1]]) (v[[1, 2]] v[[2, 1]] - 
             v[[1, 1]] v[[2, 2]]), (-u[[1, 2]] u[[2, 1]] + 
             u[[1, 1]] u[[2, 2]]) (v[[1, 2]] - 
             v[[2, 2]]) + (u[[1, 2]] - 
             u[[2, 2]]) (v[[1, 2]] v[[2, 1]] - v[[1, 1]] v[[2, 2]])}/
        detBottom);
     If[Sign[b - a] == Sign[b - pt] && Sign[a - b] == Sign[a - pt] && 
       Sign[d - c] == Sign[d - pt] && Sign[c - d] == Sign[c - pt], 
      pt, {10^6, 10^6}]]
    ]];

We can then apply this on all pairs using Outer (definitely inefficient but perhaps sufficient, or user can apply earlier suggestions on scaling?)

full = Sort /@ Transpose[{stickend1, stickend2}];
mat = Outer[lineIntersections, full, full, 1]; // Timing
(*Out[16]= {1.98438,Null}*)
matComp = Outer[lineIntComp, full, full, 1]; // Timing
(*Out[17]= {0.21875,Null}*)

One can then create an Adjacency Matrix, connecting only intersecting nodes (sticks) and generate the graph whereby VertexCoordinates can be specified as the lines defined earlier by the user.

linked[mat_] := Map[Boole[VectorQ[#]] &, mat, {2}]
linkedComp[mat_] := Map[Boole[# != {1. 10^6, 1. 10^6}] &, mat, {2}]

linkedComp[matComp] == linked[mat]
ag = AdjacencyGraph[linked[mat], VertexCoordinates -> centers, 
  EdgeStyle -> White, 
  VertexShape -> 
   Thread[Range[n] -> (Graphics[{Opacity[.5], #}] & /@ lines)], 
  VertexSize -> 250]

Now we can use various graph functionality to evaluate things like percolation. Here, I just define some extreme points for visualization purposes:

bottomMost = First@Ordering[centers[[All, 2]], 1]
topMost = First@Ordering[centers[[All, 2]], -1]
leftMost = First@Ordering[centers[[All, 1]], 1]
rightMost = First@Ordering[centers[[All, 1]], -1]

Vertical percolation:

With[{vert = FindShortestPath[ag, bottomMost, topMost]}, 
 HighlightGraph[ag, vert, ImageSize -> 700, 
  VertexShape -> 
   Thread[vert -> (Graphics[{Red, Thick, #}] & /@ lines[[vert]])]]]

Horizontal percolation:

With[{vert = FindShortestPath[ag, leftMost, rightMost]},
 HighlightGraph[ag, vert, ImageSize -> 700, 
  VertexShape -> 
   Thread[vert -> (Graphics[{Red, Thick, #}] & /@ lines[[vert]])]]]

all connected components to bottomMost stick:

With[{vert = 
   Reap[BreadthFirstScan[ag, bottomMost, {"PrevisitVertex" -> Sow}]][[
    2, 1]]},
 HighlightGraph[ag, vert, ImageSize -> 700, 
  VertexShape -> 
   Thread[vert -> (Graphics[{Red, Thick, #}] & /@ lines[[vert]])]]]

Hope this helps.

Best, George

Didn't think about the NearestFunction[..][x,{inf,r}] ! that is indeed also fast. Fast and easy implementation. $m\times n\times \log(n)$ scaling right? where $m$ is the average number of candidates in the vicinity?

Indeed a very nice answer!

If Thomas wants to to prevent close-calls, then one has to just do it 'geometrically', this is however much more tricky and time-consuming I'm afraid...

Finding the overlaps can be done in $n^2$ time as Hans said, but it can be done faster if one bins (the centers of) the sticks in bins with a width of the length of the bins. Then only check 'overlaps' for elements in 1 bin, and it's neighbours. This should reduce the $n^2$ a lot if the density is low. If the total 'area' is $A$ then the average density is $n/A$. So in a box of size $L$ you will find roughly $n\times L^2/A$ straws. So you want to check the straws in a box + neighbours it will be at most $ n^2 \times \frac{9L^2}{A}$. So if you're area is big compare to $L^2$, binning and checking neighbours might be a lot faster (binning just takes $n$ time).

Thanks again, Henrik

To proceed in the more crude way: this gives a matrix T. If T[[ i , j ]] equals 1, the lines i and j cross each other.

    intsec[Line[{A_, B_}], Line[{U_, V_}]] := Module[{},
      dd = Det[{A - B, V - U}];
      If[Abs[dd] < 0.0001, 0,
       {t1, t2} = Inverse[{A - B, V - U}].(V - B);
       If[(0 <= Abs[t1] <= 1) && (0 <= Abs[t2] <= 1), 1, 0]
       ]
      ]

T = Table[
intsec[lines[[j]], #] & /@ lines, {j, 1, n}];
T // Short[#, 15] &

OK, T is a square matrix, which is symmetrical, so we could reduce memory used by either considering the upper (lower) triangle, or a sparse array object, but I have no experience with these.

Hi Henrik,

thank you very much!At first I have thought of an approach following graph theory, but this image analysis is sufficient. I thought about using Gwyddion, but I#d prefer keeping all in Mathematica.

Regards

Sounds complicated..... My crude proposal would be: you have a list of sticks (straight lines from A to B). Pick the first one and see, whether it is crossed by another one, then pick this one and do the same and so on, and look whether you reach the opposite end of your domain.

regards Hans

You need to provide some more detail. What comprises percolability? (Is that even a word? I guess it is now.) Is it the existance of a vertical path with few or no collisions? Can the angles change during motion? If so, what are the allowed changes? Is there something that happens on collisions? Is there a "depth" wherein some number of sticks are allowed to overlap?

The above is probably not exhaustive. Before anyone can offer suggestions it is really necessary to pin down what exactly you are trying to simulate.