5

Necesito desarrollar un algoritmo que me detecte las celdas de una rejilla que estén conectadas. Considerando como conectadas toda celda que esté a distancia 1 horizontal o verticalmente (no diagonalmente). Si dispongo de estos datos:

struct cell
{
    int x{}, y{};
};

using group = std::list<cell>;

group cells =
{
    {0,6},{0,7},
    {1,1},{1,2},{1,4},{1,6},{1,7},
    {2,1},{2,4},
    {3,3},{3,4},
    {4,3},{4,4},
    {5,0},{5,1},{5,2},{5,5},{5,6},{5,7},
    {6,0},{6,1},{6,2},{6,5},{6,7},
    {7,0},{7,1},{7,2},{7,5},{7,6},{7,7}, 
};

Que en una rejilla 7×7 se verían así:

  01234567
0       ##
1  ## # ##
2  #  #
3    ##
4    ##
5 ###  ###
6 ###  # #
7 ###  ###

Debería dar como resultado cinco grupos de celdas conectadas:

  1. {0, 6}, {1, 6}, {0, 7}, {1, 7}.
  2. {1, 1}, {1, 2}, {2, 1}.
  3. {1, 4}, {2, 4}, {3, 3}, {3, 4}, {4, 3}, {4, 4}.
  4. {5, 0}, {5, 1}, {5, 2}, {6, 0}, {6, 1}, {6, 2}, {7, 0}, {7, 1}, {7, 2}.
  5. {5, 5}, {5, 6}, {5, 7}, {6, 5}, {6, 7}, {7, 5}, {7, 6}, {7, 7}.

El algoritmo debe hacer el mínimo posible de comparaciones celda contra celda, de ahí que surja la idea de un solo pase. Mi primer intento es el siguiente:

int count = 0;

int distance(const cell &a, const cell &b)
{
    const auto dx = b.x - a.x;
    const auto dy = b.y - a.y;
    return (dx * dx) + (dy * dy);
}

bool near(const cell &a, const cell &b)
{
    ++count;
    return distance(a, b) == 1;
}

void nearby(group &source, group &target)
{
    for (auto b = target.begin(), e = target.end(); b != e; ++b)
    {
        if (auto found = std::find_if(source.begin(), source.end(), [b = *b](const auto &a)
        {
            return near(a, b);
        });
            found != source.end())
        {
            target.emplace_back(*found);
            source.erase(found);
            b = target.begin();
        }
    }
}

int main()
{
    std::list<group> b;

    while (cells.size())
    {
        group t{cells.back()};
        cells.pop_back();
        nearby(cells, t);
        b.emplace_back(std::move(t));
    }

    std::cout << count;
    return 0;
}

La función nearby recibe dos grupos de celdas (source y target) y busca las celdas de source cercanas a las de target y las mueve allí. Esto implica que cada vez que se añade una celda deben volverse a revisar todas las celdas de target lo que da como resultado 1199 comparaciones (casi cuarenta comparaciones por celda).

Así que he probado una estrategia diferente:

std::list<group> blobs(group g)
{
    std::list<group> result;

    while (g.size())
    {
        const auto b = g.front();
        g.pop_front();

        if (auto found = std::find_if(result.begin(), result.end(), [&b](const auto &g)
        {
            return std::any_of(g.begin(), g.end(), [&b](const auto &a) { return near(a, b); });
        });
            found != result.end())
        {
            found->push_back(b);
        }
        else
        {
            result.emplace_back(group{b});
        }
    }

    return result;
}

La función blobs también mantiene una lista de grupos de celdas, por cada celda a clasificar mira si está cerca de al menos una celda de cada uno de los grupos ya creados y la mueve ahí, esto da como resultado 380 comparaciones (algo más de doce comparaciones por celda) que es considerablemente menor a 1199 pero agrupa las celdas mal:

  1. {0, 6}, {0, 7}, {1, 6}, {1, 7}.
  2. {1, 1}, {1, 2}, {2, 1}.
  3. {1, 4}, {2, 4}, {3, 4}, {4, 4}.
  4. {3, 3}, {4, 3}.
  5. {5, 0}, {5, 1}, {5, 2}, {6, 0}, {6, 1}, {6, 2}, {7, 0}, {7, 1}, {7, 2}.
  6. {5, 5}, {5, 6}, {5, 7}, {6, 5}, {6, 7}, {7, 5}, {7, 6}, {7, 7}.

El grupo tres y cuatro son el mismo pero por la ordenación de las celdas cuando se intentó agrupar la celda {3, 3} la que es su celda vecina {3, 4} aún no estaba agrupada, así que se consideró que {3, 3} no tenía vecinas y la metió en un grupo propio.

Se pueden ver los diferentes algoritmos en TIO: 1199 comparaciones y 380 comparaciones.

¿De qué manera puedo hacer la búsqueda de celdas vecinas minimizando las comparaciones y obteniendo los grupos adecuados?

1 respuesta 1

2

Primera aproximación

Suponiendo que las celdas pueden venir desordenadas, una forma de proceder puede pasar por definir un rectángulo que incluye a cada grupo. De esta forma podemos comprobar rápidamente si una celda cae cerca del grupo o no:

  • Si la celda no está en la frontera del grupo o dentro del mismo la ignoramos.
  • Si la celda está en la frontera del grupo o dentro procedemos a comparar las celdas del grupo una a una.

Dicho con código:

bool isInRange(int value, int min, int max)
{
  return value >= min && value <= max;
}

std::list<group> eferionFunc(group g)
{
  cell topLeft, bottomRight;

  std::list<group> result;

  while( g.size() )
  {
    const auto b = g.front();
    g.pop_front();
    cell topLeft = b;
    cell bottomRight = b;

    group currentGroup;
    currentGroup.push_back(b);

    for( auto it = g.begin(); it != g.end(); )
    {
      cell currentCell = *it;
      if( isInRange(currentCell.x, topLeft.x-1, bottomRight.x+1) && isInRange(currentCell.y, topLeft.y-1, bottomRight.y+1) )
      {
        if( std::any_of(currentGroup.begin(), currentGroup.end(), [&currentCell ](const auto &a) { return near(a, currentCell); }) )
        {
          currentGroup.push_back(currentCell);
          topLeft     = { std::min(topLeft.x, currentCell.x),     std::min(topLeft.y, currentCell.y) };
          bottomRight = { std::max(bottomRight.x, currentCell.x), std::max(bottomRight.y, currentCell.y) };
          it = g.erase(it);
          continue;
        }
      }
      ++it;
    }
    result.push_back(currentGroup);
  }
  return result;
}

Esto debería reducir el número de comparaciones respecto a la versión blob, como así sucede:

Grupos: {0, 6} {0, 7} {1, 6} {1, 7} 
Grupos: {1, 1} {1, 2} {2, 1} 
Grupos: {1, 4} {2, 4} {3, 4} {4, 4} 
Grupos: {3, 3} {4, 3} 
Grupos: {5, 0} {5, 1} {5, 2} {6, 0} {6, 1} {6, 2} {7, 0} {7, 1} {7, 2} 
Grupos: {5, 5} {5, 6} {5, 7} {6, 5} {6, 7} {7, 5} {7, 6} {7, 7} 
Comparaciones: 73

Y está claro que comparar enteros es mucho más ligero que andar haciendo multiplicaciones ...

El problema es que sigue adoleciendo de ciertos problemas a la hora de crear los grupos. Básicamente es incapaz de fusionar grupos ya existentes.. de ahí que salga un grupo de más.

Segunda aproximación

Cambiamos el planteamiento. Ahora vamos a crear un mapa de regiones. Lo que vamos a hacer ahora es comprobar si cada celda linda o no con alguna región ya existente... si es así añadimos dicha celda a la región y, si no, creamos una región nueva.

Puede suceder que una celda sirva como punto de unión para dos o más regiones ya existentes... en este caso podemos aprovechar para fusionar todas estas regiones.

Esta función es un poco más extensa:

std::list<group> eferionFunc2(group g)
{
  std::map<cell, int> cellsMap;

  std::map<int, group> groups;

  int groupCounter = 0;
  // First step: grouping some cells
  for( cell const& currentCell : g )
  {
    std::set<int> nearGroups;

    if( auto it = cellsMap.find({currentCell.x-1, currentCell.y}); it  != cellsMap.end() )
    {
      nearGroups.insert(it->second);
    }

    if( auto it = cellsMap.find({currentCell.x+1, currentCell.y}); it != cellsMap.end() )
    {
      nearGroups.insert(it->second);
    }

    if( auto it = cellsMap.find({currentCell.x, currentCell.y-1}); it != cellsMap.end() )
    {
      nearGroups.insert(it->second);
    }

    if( auto it = cellsMap.find({currentCell.x, currentCell.y+1}); it != cellsMap.end() )
    {
      nearGroups.insert(it->second);
    }

    int currentGroupIndex = -1;
    if( nearGroups.empty() )
    {
      currentGroupIndex = groupCounter++;
    }
    else if( nearGroups.size() == 1 )
    {
      currentGroupIndex = *nearGroups.begin();
    }
    else if( nearGroups.size() > 1 )
    {
      currentGroupIndex = *nearGroups.begin();
      auto & currentGroup = groups[currentGroupIndex];
      for( auto it = std::next(nearGroups.begin(), 1); it != nearGroups.end(); ++it )
      {
        auto & groupToRemove = groups[*it];
        currentGroup.insert(currentGroup.end(), groupToRemove.begin(), groupToRemove.end());
        groups.erase(*it);

        for( auto & pair : cellsMap )
        {
          if( pair.second == *it)
            pair.second = currentGroupIndex;
        }
      }
    }

    cellsMap.insert({currentCell, currentGroupIndex });
    groups[currentGroupIndex].push_back(currentCell);
  }

  std::list<group> result;
  for( auto & pair : groups )
    result.insert(result.begin(), pair.second);
  return result;
}

Pero a cambio calcula los grupos correctamente y, lo mejor de todo... no calcula distancia entre celdas

Grupos: {5, 5} {5, 6} {5, 7} {6, 5} {6, 7} {7, 5} {7, 6} {7, 7} 
Grupos: {5, 0} {5, 1} {5, 2} {6, 0} {6, 1} {6, 2} {7, 0} {7, 1} {7, 2} 
Grupos: {1, 4} {2, 4} {3, 3} {3, 4} {4, 3} {4, 4} 
Grupos: {1, 1} {1, 2} {2, 1} 
Grupos: {0, 6} {0, 7} {1, 6} {1, 7} 
Comparaciones: 0

Adicionalmente, esta función parece comportarse ligeramente mejor que las otras alternativas (en cuanto a tiempo de ejecución).

No es perfecta y seguramente sea mejorable. Se aceptan sugerencias.

11
  • Las propuestas me gustan, pero es difícil saber si son más eficientes sin hacer mediciones. El problema es que se ha trasladado el peso de la computación de la función near al operador < o a la función IsInRange. La función eferionFunc lama 73 veces a near y 172 veces a IsInRange mientras que eferionFunc2 llama 828 veces al operador <. el 11 dic. 2019 a las 10:40
  • Está claro que la complejidad la vas a desplazar a unas funciones o a otras... pero el operador < es infinitamente más liviano que near. Tampoco es un código optimizado, por ejemplo si añades los elementos al inicio del std::list en vez de al final y quizás si se usa unordered_map en vez de map... todo dependerá del número de nodos a tratar. Pero en una pasada, como pretendes, va a estar complicado ya que vas a tener que ser capaz de fusionar grupos... y para ello tienes que saber antes si una celda une dos o más grupos... ¿cómo lo haces con una única comprobación?
    – eferion
    el 11 dic. 2019 a las 10:51
  • No veo que < sea más liviano que near, estoy haciendo pruebas y para 10 operaciones near es ~13 veces más lento que <, para 100 < es ~4 veces más lento que near y para 1000 < es ~11 veces más lento que near. Es decir, a más operaciones más rápido es near respecto <. Por otro lado ten en cuenta que < se llama dos veces en map y set por cada comprobación de equidad. el 11 dic. 2019 a las 12:55
  • Benchmarks. el 11 dic. 2019 a las 12:58
  • Estoy viendo que con O3 la diferencia de rendimiento entre < y near es casi nula. el 11 dic. 2019 a las 13:36

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.