neighbourhood clustering graph, marking pts in an array as we pass through them

Replies to This Discussion

Permalink Reply by Benjamin Golder on October 25, 2009 at 3:19am

I've been thinking about a similar problem. Maybe you could create a two-dimensional array containing the indexes for the list of points in one column, and a list of 0s and 1s in the other column (representing booleans for visited or not). The entire second column starts out as 0s, and then as you visit each one you add a 1 to the corresponding boolean "cell" of the index of the point you visited. It would be really helpful to see what state your script is in, or even some "psuedoscript" in which you describe the steps in detail. I'm not really sure what you mean by "bridge between groupings". Is there a single loop that drives the iteration through the pts? You would need to write to the two-dimensional "visitation" array within the loop that iterates between the points, so it adds the boolean value right after visiting a point and before moving on to another. I hope that helps. I am still pretty new to scripting, but I think all that I mentioned is possible. I'm curious to see how you work this one out, it sounds cool . . .

Permalink Reply by Benjamin Golder on October 25, 2009 at 3:27am

I don't know if you already have something better than this, but you could make another two dimensional array in which you start out with (by column): the indexes of the points, a list of boolean "visitation" values, the number of neighbors for each point, and then a series of columns (with number of columns equal to the max number of neighbors) in which list you add the indexes of each point's neighbors, cell by cell. As you go through the index of points you could call out all of its neighbors, knowing the quantity of neighbors to call out. So some loop would go through the master index points, call out each neighbor, call out the corresponding boolean values of those neighbors, and then write to the boolean visitation cell of the now-visited point. I think it would be a big two-dimensional array and a bunch of nested loops.

Permalink Reply by Gabriel on October 25, 2009 at 2:36pm

im a little fuzzy on this one...

why would you have to have a "number of neighbours" entry? couldn't you just do a count of all in the list at runtime? and why would you need a cell for each neighbour? couldn't they be in one list?

My version is a recursive function. It goes through each pt, checks if they've been visited. If they haven't then it creates a new list and searches through its neighbouring points to see if they are in fact neighbourly - they may actually be quite far away from each other...maybe there could be some other criteria but im using distance. then if they pass this gate they are passed to the same function with the list...I have mocked something up in vb but I'm still not quite getting it. I think it might be time to understand how to make classes...i was looking at something someone else did with classes and it didn't look as scary as I imagined it would...

but I'll send you my stuff and maybe we can sort something out. I could totally use the help
best!

Permalink Reply by Gabriel on October 25, 2009 at 2:30pm

hey thanks for the reply

yeah, i have a script that works in java/processing - I will post when I get a chance. But given your newness to scripting i think you have a decent handle on things. I'm new too, and haven't touched vb in a few months...maybe you could help me get it going.

I was thinking about the 2d array as well...but I'm a little foggy on how to access or retrieve each of the cells within a data array in vb. i know how to write to them...I mean i have done so in primitive ways in the past but I'm not so clear on reading from them.

Permalink Reply by Gabriel on October 25, 2009 at 11:20pm

so here's the main bit in the java code:

for(int i = 0; i < z.animals.size(); i++)
((Animal)z.animals.get(i)).visited = false;

for(int i = 0; i < z.animals.size(); i++)
{
Animal a = (Animal)z.animals.get(i);
if(a.visited == true)
continue;
else
{
ArrayList newCluster = new ArrayList();
findAllNeighbors(i, newCluster);
if(newCluster.size() > 1)
clusters.add(newCluster);
}
}

return clusters;
}

void findAllNeighbors(int i, ArrayList members)
{
members.add(i);
Animal a = (Animal)z.animals.get(i);
a.visited = true;
for(int j = 0; j < a.neighbors.length; j++)
{
int bNum = a.neighbors[j];
if(bNum != -1)
{
Animal b = (Animal)z.animals.get(bNum);
if(b.visited == false)
findAllNeighbors(bNum, members);
}
}
}

I have sketched out a couple ways of attacking it but Im having trouble wrapping my head around arrays at the moment...just rusty i guess if you have any ideas, let me know...

Permalink Reply by Gabriel on October 25, 2009 at 11:54pm

and in grasshopper

Dim neighbourData As New DataTree(Of Integer)

For i As Integer = 0 To pts.Count - 1
Print(index(i))
Dim pathA As New EH_Path(index(i), 0)
Dim pathB As New EH_Path(index(i), 1)

'idex number of eac point in list
neighbourData.Add(index(i), pathA)
'visitation value
neighbourData.Add(0, pathB)

Dim pathC As New EH_Path(index(i), 2)

For j As Integer = 0 To neighbours.Count - 1
Print(neighbours(j))
'neighbours indices
neighbourData.Add(neighbours(j), pathC)

Next

Next

'and this next phas is really hazy - i just sorted the data array above, it works but now im not sure how to call the recursive function

For i As Integer = 0 To pts.Count - 1

If counter(i) = True

Else
'Dim path As New EH_Path(i)

findClusters(pts(i), i, path, pts, neighbours, counter, gate, clusters)

End If

Next

Sub findClusters(ByRef ptA As On3dPoint, ByVal k As Integer, ByRef path As EH_Path, ByRef pts As list(Of On3dpoint), ByRef neighbours As list(Of Integer), ByRef counter As list(Of Boolean), ByRef gate As Double, ByRef clusters As DataTree(Of On3dPoint))

clusters.Add(ptA, path)
counter(k) = True

For j As Integer = 0 To neighbours.count - 1
Print(neighbours(j))
Dim ptB As New On3dPoint
ptB = pts(neighbours(j))

Dim distance As New Double
distance = ptA.DistanceTo(ptB)

If distance < gate Then

'If ptB hasn't been visited - you need integer number for this to access its place in the boolean list - rethink
If counter(neighbours(j)) = False Then
' findClusters(ptB, j, path, pts, neighbours, counter, gate, clusters)
Else
End If

Else

End If

Next

End Sub

Permalink Reply by Gabriel on April 2, 2010 at 4:38pm

Hi Moritz

That was a while ago and I figured away around this...I dont think I ever quite resolved it fully. This weekend is kind of a busy one but I'll try and get back to you on Mon or Tues. I hope you can wait...

Best
Gabe