Algoritmo para encontrar rectángulos

Question

tengo el siguiente código:

int width = 10; 
int height = 7; 
bool[,] array1 = new bool[width, height]; 


string values = 
    "1100000000" + 
    "1100000011" + 
    "0001100011" + 
    "0001100000" + 
    "0001110000" + 
    "0000000110" + 
    "0000000110"; 

for (int x = 0; x < width; x++) 
{ 
    for (int y = 0; y < height; y++) 
    { 
     array1[x, y] = (values[x + y * width] == '1'); 
    } 
} 

im busca de un algoritmo que permita, mediante rangos en los que tenemos 1.

por lo partir de estos datos que se pueden conseguir rectángulos (0 , 0,2,2), (8,1,2,2), (3,2,3,3), (7,5,2,2) ¡No importa el orden de los rectángulos!

Pero no tengo idea de cómo hacer esto, ¿alguien tiene algún punteros?

Después de leer la respuesta oxidado Weber me encontré con lo siguiente:

private static List<Rectangle> GetRectangles(bool[,] array) 
{ 
    List<Rectangle> rectangles = new List<Rectangle>(); 
    for (int x = 0; x < array.GetLength(0); x++) 
    { 
     for (int y = 0; y < array.GetLength(1); y++) 
     { 
      if (array[x, y]) 
      { 
       rectangles.Add(GetRectangle(array, new Point(x, y))); 
      } 
     } 
    } 
    return rectangles; 
} 



static Rectangle GetRectangle(bool[,] array, Point startLocation) 
{ 
    int maxX = int.MinValue; 
    int minX = int.MaxValue; 
    int maxY = int.MinValue; 
    int minY = int.MaxValue; 
    HashSet<Point> visitedLocations = new HashSet<Point>(); 
    Stack<Point> pointsToGo = new Stack<Point>(); 
    Point location; 
    pointsToGo.Push(startLocation); 
    while (pointsToGo.Count > 0) 
    { 
     location = pointsToGo.Pop(); 

     if (!location.X.IsBetween(0, array.GetLength(0) - 1)) 
      continue; 
     if (!location.Y.IsBetween(0, array.GetLength(1) - 1)) 
      continue; 
     if (!array[location.X, location.Y]) 
      continue; 
     if (visitedLocations.Contains(location)) 
      continue; 
     visitedLocations.Add(location); 

     pointsToGo.Push(new Point(location.X + 1, location.Y)); 
     pointsToGo.Push(new Point(location.X, location.Y + 1)); 
     pointsToGo.Push(new Point(location.X - 1, location.Y)); 
     pointsToGo.Push(new Point(location.X, location.Y - 1)); 
    } 

    foreach (Point location2 in visitedLocations) 
    { 
     array[location2.X, location2.Y] = false; 
     if (location2.X > maxX) 
      maxX = location2.X; 
     if (location2.X < minX) 
      minX = location2.X; 
     if (location2.Y > maxY) 
      maxY = location2.Y; 
     if (location2.Y < minY) 
      minY = location2.Y; 
    } 

    return new Rectangle(minX, minY, maxX - minX + 1, maxY - minY + 1); 
} 

public static bool IsBetween<T>(this T item, T start, T end) 
{ 
    return Comparer<T>.Default.Compare(item, start) >= 0 
     && Comparer<T>.Default.Compare(item, end) <= 0; 
} 

Answer 1

Añadir :: Podría ayudarme a responder a su pregunta si usted tiene coordenadas mejor definidas. (0,0,2,2) no es exactamente cartesiano y puede necesitar algunas explicaciones. ¿Es esta la esquina superior izquierda seguida de los anchos?

Ok. La forma más fácil de programar, en mi opinión al menos, para extraer todos los rectángulos posibles del gráfico es tener un método de definición recursiva que busque en una dirección específica para el patrón de rectángulo simétrico. Sin embargo, esto podría terminar siendo muy lento, así que espero que la velocidad no sea una restricción para ti. Mirando el estilo del código, diría que esta es una tarea escolar para recursividad o programación dinámica.

algo en la línea de la siguiente pseudocódigo

`

for i in width 
{ 
for j in height 
{ 
if(point[i,j] == 1) 
{ 
     potentials = searh_in_direction(i,j,graph,width,height,RIGHT,[[i,j]]) 
    listOfAllRects.append(potentials) 
} 
} 
} 
list_of_rectangle searh_in_direction(i,j,graph,width,height,direction, listofpoints) 
{ 
    nextdirection = direction.nextdirection; //Right -> down -> left-> up 


    //DEVELOP METHOD FOR RECURSION HERE THAT RETURNS ALL SETS OF 4 POINTS THAT 
    for every point in the direction of travel 
    if the point is the origional point and we have 4 points including the point we are looking at, we have a rectangle and we need to return 
    if point on direction of travel is a one travel on the next direction 
    posiblerects.append(searh_in_direction(i,j,graph,width,height,nextdirection , listofpoints.append(currentpoint))) 

//after all points in direction have bee searched 
return posiblerects. 
} 

`

sé que el código podría ser muy confuso, pero esa es la esencia de lo que necesita como recursiva elemento. También notaré que ya puedo ver varios errores en este código, pero me he quedado sin los 15 minutos que dije que iba a gastar en esta publicación, por lo que podría tener que elegirlos usted mismo.

Answer 2

No está claro si realmente desea rectángulos que cubran exactamente los 1, o si desea volúmenes delimitadores que pueden contener ceros, pero abarcará todos los 1 con un número razonablemente pequeño de rectángulos.

Suponiendo que desea rectángulos para cubrir los números 1, y no se necesita una solución perfecta:

1. realizar una copia temporal de la matriz.
2. iterar sobre el temporal en busca de de 1
3. Cuando te encuentras con un 1, comenzará un nuevo rectagle que se inicia tan 1x1, desplazamiento a la ubicación (por ejemplo, cubre sólo que 1)
4. ampliar esa derecha rectángulo siempre que haya es un 1 en la celda siguiente
5. Expande ese rectángulo hacia abajo, siempre que la fila siguiente tenga un 1 que coincida con el ancho del rectángulo actual.
6. UNA vez que ya no puede expandirse más, emite esa operación y borra todos los 1 cubiertos por ese rectángulo desde el
7. continúe escaneando por 1 a partir de la celda directamente después de la esquina superior derecha del rectángulo actual .

Esto producirá una cubierta decente, pero de ninguna manera ideal. Si necesita una cobertura perfecta, p. el número mínimo garantizado de rectángulos, entonces es más difícil.

Answer 3

Esto le da los mismos resultados que buscas:

static void Main(string[] args) 
{ 
    string values = 
     "1100000000" + 
     "1100000011" + 
     "0001100011" + 
     "0001100000" + 
     "0001110000" + 
     "0000000110" + 
     "0000000110"; 

    int width = 10; 
    int height = 7; 
    bool[,] array = new bool[width, height]; 

    for (int x = 0; x < width; x++) 
     for (int y = 0; y < height; y++) 
      array[x, y] = (values[x + y * width] == '1'); 

    List<Rectangle> rectangles = new List<Rectangle>(); 

    for (int x = 0; x < width; ++x) 
    { 
     for (int y = 0; y < height; ++y) 
     { 
      if (array[x, y] && !Used(rectangles, x, y)) 
      { 
       int rHeight = 1; 
       for (int rX = x + 1; rX < width && array[rX, y] && !Used(rectangles, rX, y); ++rX) 
        for (int rY = y + 1; rY < height && array[rX, rY] && !Used(rectangles, rX, rY); ++rY) 
         if (rY - y >= rHeight) 
          rHeight = rY - y + 1; 

       int rWidth = 1; 
       for (int rY = y + 1; rY < height && rY - y <= rHeight && array[x, rY] && !Used(rectangles, x, rY); ++rY) 
        for (int rX = x + 1; rX < width && array[rX, rY] && !Used(rectangles, rX, rY); ++rX) 
         if (rX - x >= rWidth) 
          rWidth = rX - x + 1; 

       rectangles.Add(new Rectangle(x, y, rWidth, rHeight)); 
      } 
     } 
    } 

    foreach (Rectangle rect in rectangles) 
     Console.WriteLine(rect); 
} 

private static bool Used(IEnumerable<Rectangle> rectangles, int x, int y) 
{ 
    return rectangles.Any(r => r.Contains(x, y)); 
} 

hice un rectángulo adhoc estructura ya que no me refiero System.Drawing, pero se puede pasar una System.Drawing.Point a el System.Drawing.Rectangle.Contains() y obtiene los mismos resultados.

Además, observe que el ancho de su matriz en realidad debería ser 10 y su cálculo de índice incorrecto. Deberías multiplicar y por el ancho, no la altura.