Práctica 5 de AED2: Montículos binomiales

Implementar un montículo binomial en la clase monticulo_binomial. Dicha clase se ultilizará para analizar una imagen binaria y etiquetar los objetos contenidos en ella.

Los ficheros de imágenes responderán al siguiente formato: una línea de caracteres por cada línea en la imagen con cada caracter correspondiente a un pixel. El valor de los caracteres puede ser:

El programa debe generar una imagen de salida similar a la de entrada, pero sustituyendo los asteriscos por letras mayúsculas. Cada letra será el identificador de un objeto distinto. Todo conjunto de pixels ocupados 8 conexo se considera un único objeto.

El programa tendrá como argumento el nombre del fichero de entrada/salida sin extensión. Los ficheros de entrada tendrán la extensión in y los de salida la extensión out.

A continuación se proporciona el esqueleto de la clase imagen:

public class imagen
  {
    // Variables globales
  private static final int XMAX = 500;
  private static final int YMAX = 500;
  int maxx, maxy;
  char[][] imagen;
  int[] idx_monti;
  private static final int MAX_MONTICULOS = 20;
  monticulo_binomial[] vmonti;
    // Constructor
  public imagen()
    {
    vmonti = new monticulo_binomial[MAX_MONTICULOS];
    }
    // Carga la imagen de fichero
  public void carga(String nomf)
    {
    imagen = new char[XMAX][YMAX];
    idx_monti = new int[XMAX*YMAX];
    try
      {
      int val;
      InputStream f = new FileInputStream(nomf);
      maxx = 0;
      maxy = 0;
      for (int y=0; y<YMAX && f.available()>0; y++)
        {
        for (int x=0; x<XMAX; x++)
          {
          val = f.read();
          if ( val<=' ' )
            break;
          if ( x>maxx )
            maxx = x;
          if ( y>maxy )
            maxy = y;
          imagen[x][y] = ((char)val);
          }
        }
      }
    catch (java.io.IOException e)
      {
      System.out.println("Error en la entrada.");
      }
    }
    // Comprueba si el pixel esta ocupado
  boolean ocupado(int x1, int y1)
    {
    if ( imagen[x1][y1]!='.' )
      return(true);
    return(false);
    }
    // Etiqueta los objetos de la imagen
  public void etiqueta()
    {
      // Genera vector de monticulos a partir de la imagen y
      // Etiqueta en base al vector de monticulos


    }
    // Vuelca la imagen etiquetada
  public void vuelca(String nomf)
    {
    try
      {
      OutputStream f = new FileOutputStream(nomf);
      for (int y=0; y<=maxy; y++)
        {
        for (int x=0; x<=maxx; x++)
          {
          System.out.print(imagen[x][y]);
          f.write(imagen[x][y]);
          }
        f.write('\n');
        System.out.println("");
        }
      }
    catch (java.io.IOException e)
      {
      System.out.println("Error en la salida.");
      }
    }
    // programa principal
  public static void main(String[] args)
    {
    String nfr = args[0] + ".in";
    String nfw = args[0] + ".out";
    imagen im = new imagen();
    im.carga(nfr);
    im.etiqueta();
    im.vuelca(nfw);
    }
  }
  
Falta implementar el método etiqueta(). Para ello se recomienda almacenar en los montículos la posición de los pixels codificada como: y*maxx + x.

PISTAS:

  1. Crear un montículo nuevo para cada pixel procesado que pertenezca a un objeto e insertarlo en un elemento no usado del array vmonti.
  2. Fusionar dicho montículo con sus cuatro vecinos ya procesados si hiciera falta.
  3. Para evitar fusionar un montículo consigo mismo usar los valores del mínimo de los montículos.
  4. Cada vez que se fusionen dos montículos guardar en las posiciones de los mínimos de ambos montículos del array idx_monti (antes de la fusión) el valor del mínimo del montículo resultante. Esto permite determinar el montículo de vmonti que contiene una posición dada.
  5. Los valores de posición a almacenar en los montículos deben ser de algún tipo que implemente el interfaz Comparable; por ejemplo, el tipo Integer.

Disponéis de un ejemplo de entrada en imagen1.in, junto con el fichero resultado del procesamiento en imagen1.out.

NOTA: Esta práctica dura dos sesiones y deben entregarse a través de web el fichero imagen.java con el procesamiento de la imagen y el fichero monticulo_binomial.java con la implementación del montículo binomial.