¿Cuál es la mejor manera de combinar un conjunto de rectángulos en una imagen?

Question

Esto no es una pregunta para la tarea :)

Tengo un conjunto de rectángulos dispersos en una imagen. Quiero fusionar (crear una unión) de cada grupo de rectángulos intersecados. Si un rectángulo no se cruza con sus vecinos, permanece intacto.

El problema es que los rectángulos combinados pueden intersectar rectángulos que anteriormente no estaban en consideración; Los rectángulos fusionados también pueden intersectar rectángulos recién fusionados. Quiero atrapar esos casos.

Por lo tanto, en mi opinión, debe ser iterativo (pruebe cada rect contra cada otro rect en el conjunto) y recursivo (pruebe cada rect fusionada contra el conjunto de nuevo, incluidas las rectas fusionadas).

¿Cómo puedo hacer esto? Estoy trabajando en Java, pero esto es más una cuestión algorítmica que una orientada al lenguaje.

Gracias!

Editar: se agregó el código relevante para ilustrar mejor la mala forma en que lo estoy manejando ahora.

public static List<BinaryRegion> mergeRegions(List<BinaryRegion> regions) 
{ 
    List<BinaryRegion> merged = new ArrayList<BinaryRegion>(); 
    geoModel = new GeometryFactory(); 

    Polygon polys[] = new Polygon[regions.size()]; 
    for (int i = 0; i < regions.size(); i++) 
    { 
     Polygon p = convertRectangleToPolygon(regions.get(i) 
       .getBoundingBox()); 
     polys[i] = p; 
    } 

    System.out.println("Converted " + regions.size() + " polys"); 

    for (int i = 0; i < regions.size(); i++) 
    { 
     System.out.println("Sending in poly " + i); 
     ArrayList<Polygon> result = mergePoly(polys[i], polys); 
     System.out.println("After run, size=" + result.size()); 
    } 
    return merged; 

} 

private static ArrayList<Polygon> mergePoly(Polygon p, Polygon[] polys) 
{ 
    ArrayList<Polygon> merges = new ArrayList<Polygon>(); 

    for (int i = 0; i < polys.length; i++) 
    { 
     if (p.equals(polys[i])) 
      System.out.println("found the exact match at " + i); 
     else if (p.intersects(polys[i])) 
     { 
      System.out.println("Found intersection at " + i); 
      System.out.println("Other poly is area "+polys[i].getArea()); 
      Polygon u = (Polygon) p.union(polys[i]); 
      System.out.println("Merge size="+u.getArea()); 
      merges.add(u); 
     } 
     else 
      merges.add(polys[i]); 
    } 
    return merges; 
} 

Answer 1

No sabe con certeza si este enfoque iterativo anidada es realmente el camino a seguir (sobre todo porque yo no veo cómo es exactamente lo que está manejando las regiones fusionadas después de su llamada a mergePoly). En lugar de trabajar con un polígono a la vez en comparación con todos los demás polígonos, ¿por qué no mantiene los pasos intermedios y vuelve a ejecutar la fusión hasta que no haya más intersecciones? Algo a lo largo de las líneas de:

private static ArrayList<Polygon> mergePoly(Polygon[] polys) 
{ 
    List<Polygon> polygons = new ArrayList<Polygon>(Arrays.asList(polys)); 
    boolean foundIntersection = false; 
    do 
    { 
     foundIntersection = false; 
     for (int i = 0; i < polygons.size(); i++) 
     { 
      Polygon current = polygons.get(i); 
      for (int j = i + 1; j < polygons.size(); j++) 
      { 
       if (current.intersects(polygons.get(j))) 
       { 
        foundIntersection = true; 
        current = (Polygon)current.union(polygons.remove(j--)); 
        System.out.println("Merge size="+u.getArea()); 
       } 
      } 
      polygons.set(i, current); 
     } 
    } while(foundIntersection); 
    return polygons; 
} 

Ha sido un tiempo desde que he trabajado con Java, pero la lógica es bastante auto-explicativo. Realiza dos iteraciones de los polígonos. La iteración externa es tu polígono "actual", con el que fusionarás todos los polígonos (eliminándolos de la colección a medida que avanzas). Después de cada iteración externa, simplemente establecerá el elemento en ese índice con el polígono (posiblemente) fusionado y pasará al siguiente polígono de la serie. Continuarás haciendo esto hasta que ya no obtengas más fusiones. Solo tenga en cuenta que esta es una implementación terriblemente ingenua, y que sería mejor dividirla en "mitades" y fusionar estos subconjuntos más pequeños (piense en mergesort).

Answer 2

Usted puede utilizar el algoritmo línea de barrido para encontrar las intersecciones de rectángulos (example1, example2) yu nion-find algorithm para combinar con eficacia conjuntos de rectángulos.