Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Hello fellow programmers!

I have a 2D graph which is best described as a Cartesian grid with traversible and non-traversible cells. I'd like to be able to detect subsets of this graph where the diffusion behaves anisotropically, i.e.: it is constrained by corridor-like passages.

I initially turned to diffusion tensor imaging in neuroscience, but I'm having a great deal of trouble digesting the material. I'm wondering if any of this has already been distilled into a usable algorithm, or if there are other approaches that could be fruitful.

Specifically, I'd like to be able to determine the following:

  1. Areas in which diffusion is anisotropic: highly constrained to two directions (think of water flowing through a 2D slice of a straw).
  2. Areas in which diffusion is isotropic: largely unconstrained (i.e., water is diffusing through a large, though irregularly-shaped space.

Since the graph only contains very narrow or open areas, it would be sufficient to determine either anisotropic or isotropic diffusion and deduce the other one with a simple contrast.

TL;DR: How can I find the "average" direction of a diffusion in a flood-fill or similar operation?

EDIT: Here's an example of my graph as an image:

enter image description here

share|improve this question
    
Could you post an image example of your grid? –  leonbloy Apr 17 '13 at 15:15
    
@leonbloy, I hesitate because it's unpublished scientific data. I'll see if I can post a dummy example, or some sort of schematic representation. –  blz Apr 17 '13 at 15:19
    
@leonbloy, I've added a representative example. Does this help? –  blz Apr 17 '13 at 15:45
1  
If you add n "random walkers" to a n random start nodes, make them move to a random neighboor each time step, count how many times each node are 'touched' by a random walker after (many) iterations, you're probably going to have something close to what you want. I did something like that to find tortuosity of a porous media back in college. Google for 'random walker' –  Vitor Apr 17 '13 at 20:06
1  
@blz Yes, you got the idea. I remember it being slow as hell for many iterations (about 10^7 back when I did it). I was in college then, so I could just submit a job to a HPC cluster instead of running it on my laptop. If you're in a research setting, you probably have access to a similar resource. I'd send you my paper but it's in Portuguese... –  Vitor Apr 17 '13 at 21:37

1 Answer 1

I'm not aware of any known solutions, but at first thought a simple flood fill that fills based on connectivity might work.

Assumptions:

  • Every node's 'openness' will be a function of its connectivity to other nodes. That is, in a bi-directional graph that simulates a square grid, a completely open node will have 8 edges.

Untested, but the following pseudocode might be capable of finding open areas.

public class graph
{
    private static List<node> GetArea(node n)
    {
        if (isConnectedEnough(n))
        {
            yield n;
            yield! GetArea(n.neighbours)
        }
    }

    private static bool isConnectedEnough(node n)
    {
        return n.neighbours.Count >= 3;
            /* better: a connectivity threshold function */
    }
}

I envisioned calling GetArea sequentially on the list of all nodes in the graph sorted by connectivity until an area of sufficient size was found. Depending on the characteristics of your graph(s) that might not be sufficient, but I was going on the assumption that the graph was structured such that there were numerous areas separated by passageways (ie. rooms connected by hallways).

The connectivity threshold is the key in this situation. Some experimentation would be required here based on the characteristics of your graph(s) because:

  • If the average connectivity of the neighbouring nodes is equal to the connectivity of n then the area is very possibly consistent in size (ie. not approaching a choke point, also not expanding in size).
  • If the average connectivity of the neighbouring nodes is larger than the connectivity of n then we may be expanding into an area. Depending on how you define an area, that may be fine, (potentially describes a "pinch" in an area). Careful consideration should be considered here because this also describes corners and "corridors" of width 2 nodes/1 edge (min threshold of 3 would permit corners in the area).

That's all I've got for now, but I'll check back in here. This is an interesting problem.

share|improve this answer
    
This sounds like a very interesting approach, and I'll give it due consideration =) My only concern is in scalability. My math isn't very well-honed, but it doesn't seem like this is something that can easily be vectorized (or am I wrong)? My gut feeling is that there's something to be done with diffusion tensor fields, but I'm severely limited by my mathematical skills there as well. Lots to think about, in any case -- thanks! EDIT: another thing here is that I don't see how we could get the diffusion direction with this method. It's not essential, but it would be extremely helpful. –  blz Apr 17 '13 at 16:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.