Группировка/связывание в кластере

Question

Я использую обработку, и до сих пор у меня есть эскиз, который рисует случайные шары и рисует линию при соединении в пределах определенного радиуса.

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); 
      } 
     } 
     } 
    } 

Это прекрасно работает, чтобы визуально показать, какие группы группируются вместе. Но как я могу сохранить эту группу связанных объектов в ArrayList, пока они связаны? Поэтому я могу вспомнить их для других функций.

Как я имею в виду, я могу легко визуально видеть, когда на экране связаны 4 человека. Но как я могу сказать компьютеру, что все они связаны?

Ссылки хранятся в каждом списке соединений объектов. Но как каждый отдельный объект знает о соединениях других объектов, чтобы сгруппировать их.

Так что я могу нарисовать вокруг себя «групповой blob», в то время как они связаны.

Я пробовал кучу вещей, но я всегда сталкиваюсь с ошибками рекурсии/stackoverflow. Потому что, очевидно, я просто рекурсивно просматриваю все соединения, чтобы связать их, и это слишком много.

Любая идея, как я могу хранить связанные строки в виде групп в ArrayList?

Answer 1

Похоже, у вас есть класс под названием Person, поэтому я бы включил ArrayList в класс. Не зная ваш полный код, он может выглядеть следующим образом:

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): 
     } 
    } 
    } 
} 

Это первый очищает ArrayList, а затем проверяет расстояние между собой и всеми остальными. Если расстояние достаточно короткое (в моем примере 100px), то оно добавляется в ArrayList.

Отредактировано на ваш комментарий:
Это по существу вопрос о графах и узлов. См. this examples в качестве отправной точки.

Answer 2

Я предполагаю, что вы определяете «кластер» как набор объектов, которые являются 0 пикселями от любого другого объекта в этом кластере. Другими словами, кластер представляет собой группу из Person объектов, связанных их списком connections. Обратите внимание, что на самом деле это не «кластер» в традиционном понимании компьютерной науки, поэтому он может отбросить ваши поисковые запросы.

Как первый удар, вы можете подумать об организации своих кластеров в ArrayList от ArrayLists из Person объектов. Назовем это ArrayList<ArrayList<Person>> clusters. Каждый внутренний ArrayList представляет собой «кластер» связанных объектов Person. У вас также есть еще один ArrayList<Person>, представляющий Person объектов, которые вы уже посетили, назовите это visited. Затем основы того, что вы пытаетесь сделать бы:

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); 
    } 
} 

Обратите внимание, что я не проверял этот код, но основы есть: вам нужно следить за кем вы уже посетили , и пропустить их, чтобы избежать бесконечной рекурсии. Это ваш базовый футляр.

Также обратите внимание, что вы можете захотеть взглянуть на «настоящие» алгоритмы кластеризации. Google - ваш друг для этого, поскольку кластеризация - это целая область сама по себе.