Group Abstract Group Abstract

Message Boards Message Boards

4
|
14.4K Views
|
23 Replies
|
34 Total Likes
View groups...
Share
Share this post:
GROUPS:

Making percolation paths visible

Posted 10 years ago
POSTED BY: J F
23 Replies

Dear Vitaliy: Excellent solution - as always!

Dear Tommy: You can convert a graphic to an image (with a specific resolution) using:

Image[lineGraphics, ImageResolution -> 200]

Regards -- Henrik

POSTED BY: Henrik Schachner

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

POSTED BY: Sander Huisman
POSTED BY: Daniel Lichtblau

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?

POSTED BY: Sander Huisman

(It will probably work better if done without the factorial...). The scaling is somewhere in the vicinity of what you propose. Certainly the m*n part is there. The last factor is probably in the vicinity of log(n) though honestly I'm not sure what exactly is the behavior. There has to be a log(m) component because we maintain a binary heap of size m. But I suspect there is an additive component here that is bigger, likely in the ballpark of log(n).

POSTED BY: Daniel Lichtblau

I will give you just a crude idea using WatershedComponents. That function can find the "ridge" between so called "catchment basins". You have to read up on that to understand. Taht "ridge" is your percolation path. It can also be for example a path in a maze. Alternatively, for general education for percolation coding, take a look at Finding a percolation path, Wolfram Demos, and NKS Book.

So let's go with WatershedComponents now. Your code a bit adjusted for around a percolation threshold:

L = 0.1;
n = 900;
SeedRandom[1]
centers = RandomReal[{0, 1}, {n, 2}];
? = RandomVariate[NormalDistribution[?/2, (1/2.3548)*?/4], n];
stickend1 = centers + Transpose[L {Cos[?], Sin[?]}/2];
stickend2 = centers - Transpose[L {Cos[?], Sin[?]}/2];
lines = Map[Line, Transpose[{stickend1, stickend2}]];
i = Binarize[ColorNegate[Graphics[{Thickness[.0], lines}, PlotRangePadding -> -.02]]]

enter image description here

Now you can find all the ridges, - those are 0-value components spanning the outer boundaries of the catchment basins:

Colorize[MorphologicalComponents[
  WatershedComponents[i, CornerNeighbors -> True] /. {0 -> 1, x_Integer /; x > 0 -> 0}]]

enter image description here

For percolating cluster you select the largest one:

path = SelectComponents[MorphologicalComponents[
    WatershedComponents[i, CornerNeighbors -> True] /. {0 -> 1, x_Integer /; x > 0 -> 0}], 
   "Count", -1] // Image

enter image description here

And you can highlight it on the original image too:

HighlightImage[i, path, Method -> {"Boundary", 2}]

enter image description here

POSTED BY: Vitaliy Kaurov

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.

POSTED BY: Hans Dolhaine
Posted 10 years ago

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

POSTED BY: J F

Hi Thomas,

one could use mathematical morphology:

lineGraphics = Graphics[lines, Frame -> False];
ColorNegate @ Colorize[MorphologicalComponents[ColorNegate @ lineGraphics]]

which gives:

enter image description here

Maybe this might serve as a start.

Regards -- Henrik

POSTED BY: Henrik Schachner

A plausible next step is to form a graph wherein sticks are vertices and edges are based on incidence (that is, overlap) relations. Designate sticks at the top as initial vertical vertices, ones at the bottom as terminal, do similarly for those at left and right. Then graph/network metods can be used to determine existence or number of paths connecting initials to terminals.

Obviously this would take some coding, I just wanted to outline an approach one might pursue following up on this nice use of morphological component separation.

POSTED BY: Daniel Lichtblau
Posted 10 years ago

Thanks again, Henrik

POSTED BY: J F

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

POSTED BY: Hans Dolhaine
POSTED BY: Daniel Lichtblau
Posted 10 years ago

Making percolation paths visible

POSTED BY: J F
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard
Be respectful. Review our Community Guidelines to understand your role and responsibilities. Community Terms of Use