Grouping/linking in a cluster

Question

I'm using processing and so far I have a sketch that draws random balls, and draws a line when the connect within a certain radius.

for(int i=0;i<=people.size()-1;i++){
   Person p = people.get(i);
      for(Person pp: people){
        if(pp!=p){
          if(p.isIntersecting(pp)){
            // Draw the line connecting the two here
            line(p.loc.x,p.loc.y,pp.loc.x,pp.loc.y);
            // Store the other person in this persons "connections" list
            if(!p.connections.contains(pp)){ p.connections.add(pp);}

          } else {
             p.connections.remove(pp);
          }
        }
      }
  }

This works perfectly fine to visually show which groups are clustering together. But now how could I store that group of connected objects into an ArrayList, while they're connected? So I can recall them for other functions.

Like what I mean is, I can easily visually see when 4 people are linked on screen. But how can I tell the computer that they're all linked?

The links are stored in each objects connections list. But how does each separate object know of the other objects connections to group them.

So I can draw a "group blob" around them, while they're linked.

I've tried a bunch of things, but I always seem to be running into recursion/stackoverflow errors. Because obviously I'm just recursively looking through all the connections to link them, and it's too much.

Any idea how I can store the connected lines as Groups in an ArrayList?

score 0 · Answer 1 · answered May 29 '15 at 14:06

I'm assuming you're defining a "cluster" as a set of objects that are < N pixels from any other object in that cluster. In other words, a cluster is a group of Person objects linked by their connections list. Note that this isn't really a "cluster" in the traditional computer science sense, so it might be throwing off your google searches.

As a first stab, you might think about organizing your clusters into an ArrayList of ArrayLists of Person objects. Let's call that ArrayList<ArrayList<Person>> clusters. Each inner ArrayList represents a "cluster" of connected Person objects. You'd also have another ArrayList<Person> representing Person objects you've already visited, call that one visited. Then, the basics of what you're trying to do would be:

ArrayList<Person> visited;
ArrayList<ArrayList<Person>> clusters;

void createGroups(){
   for(Person p : people){

      //if we've already added this Person, skip it
      if(!visited.contains(p)){
         //since we haven't seen this Person, it isn't clustered yet
         ArrayList<Person> newCluster = new ArrayList<Person>();
         clusters.add(newCluster);

         //start the recursion
         addMe(p, newCluster);
      }
   }
}

void addMe(Person p, ArrayList<Person> cluster){

   //if we've already added this Person, skip it
   if(visited.contains(p)){
      return;
   }

   //add me first
   cluster.add(p);
   //remember that we've already visited me
   visited.add(p);

   //now add my neighbors
   for(Person n : p.connections){
      addMe(n, cluster);
   }
}

Note that I haven't tested this code, but the basics are there: you need to keep track of who you've already visited, and skip over them to avoid infinite recursion. That's your base case.

Also note that you might want to look into "real" clustering algorithms. Google is your friend for that one, as clustering is an entire field in itself.

score -1 · Answer 2 · edited May 23 '17 at 12:02

-1

It looks like you have a class called Person, so I would include the ArrayList in the class. Not knowing your full code, it might look like this:

class Person {
  ArrayList<Person> connected = new ArrayList<Person>();

  Person() {
    // create as you already are doing
  }

  void checkConnections() {
    connected.clear();               // delete existing connections
    for (Person other : persons) {
      if (dist(x,y, other.x,other.y) < 100) {
        connected.add(other):
      }
    }
  }
}

This first clears the ArrayList, then checks the distance between itself and all others. If the distance is short enough (in my example 100px) then it is added to the ArrayList.

Edited per your comment:
This is essentially a question about graphs and nodes. See this examples as a starting point.

edited May 23 '17 at 12:02

Community

1
1

answered May 29 '15 at 02:50

JeffThompson

1,538
3
24
47

Thats already what im doing. Im pushing a connection into the persons connections array after checking if they intersect. Which is what your code above does as well. My real question is. How do I get ALL the connections from all the child connections. For instance....lets say theyre all linked in a line. 6 connections. each connected in a chain. How does the first element tell that its connected to the last element. When its actually connected through a series of connections. Not a direct connections. Im not sure if Im saying that in a way that makes sense? – Kylie May 29 '15 at 03:49
perhaps you need a Group class... to hold connected instances of Person? – v.k. May 29 '15 at 05:44
I see – that wasn't very clear from your question. See my updated answer with a link to an example. – JeffThompson May 29 '15 at 22:26

Grouping/linking in a cluster

2 Answers2