sort fastest complexity best array algorithms c arrays algorithm math

fastest - Encontrando rectángulos completos que encierran 0



sorting algorithms java (5)

El siguiente algoritmo O (n) funcionará en cualquier matriz 2D de valores 0/1 (es decir, se permiten rectángulos que se intersecan / superponen, al igual que las formas abiertas / cerradas arbitrarias no rectangulares). La definición de un rectángulo que estoy usando aquí es "el interior está formado completamente por 0-celdas" (por ejemplo, si un rectángulo contiene por completo otro, solo se encontrará el rectángulo interior; si también se debe considerar el hecho de contener rectángulos, cada rectángulo encontrado se puede eliminar y reiniciar el algoritmo). Se basa en la observación de que cada celda 0 puede estar en el interior de un rectángulo como máximo .

Yo uso la convención de que x = 0 es la posición más a la izquierda y y = 0 es la posición más alta.

  1. Encuentra la esquina superior izquierda. Comenzando en la celda superior izquierda y continuando de izquierda a derecha y de arriba a abajo, encuentre la siguiente celda no visitada que podría ser la esquina superior izquierda de un rectángulo sólido-0: específicamente debe ser una celda 0 que tiene vecinos de 1 celda en las posiciones SW, W, NW, N y NE, y celdas 0 en las 3 posiciones vecinas restantes.
  2. Encuentra la esquina superior derecha. Escanee a través de los vecinos a su derecha, mientras que estas celdas son 0 y tienen un vecino N de 1 celda.
  3. ¿Podría ser esta la fila superior de un rectángulo 0 sólido? Si la última celda encontrada por el bucle anterior antes de que finalice es una celda que podría ser la celda superior derecha en un rectángulo sólido-0 (específicamente una celda 0 que tiene vecinos de 1 celda en el NW, N, NE, E y celdas SE, y celdas 0 en las 3 posiciones restantes), entonces hemos establecido tanto la coordenada y superior como el ancho exacto del único rectángulo 0 sólido sólido posible que usa cualquiera de estas celdas. Si la última celda no cumple con estas condiciones en la esquina superior derecha, ninguna de estas celdas puede formar parte de un rectángulo 0 sólido: márquelas como visitadas y goto 1.
  4. Llame a las coordenadas de inicio y final x de la tira de 0 celdas x1 y x2; llamar a la posición vertical y1.
  5. Escanear hacia abajo, una fila a la vez. Establezca y2 = y1, y mientras que la línea entre x1 y x2 en la posición vertical y2 podría formar parte del rectángulo 0 sólido, incremente y2. Específicamente, la prueba en cada posición vertical y2 es: las celdas en (x1 - 1, y2) y (x2 + 1, y2) deben ser 1, y todas las celdas intermedias deben ser 0.
  6. ¿Podría ser esta la fila inferior de un rectángulo 0 sólido? Si la última fila encontrada por el bucle anterior antes de que finalice es una fila que podría ser la fila inferior de un rectángulo 0 sólido (específicamente hay 1 celdas desde (x1 - 1, y2 + 1) hasta (x2 + 1, y2 + 1)), entonces hemos encontrado un rectángulo 0 sólido completo rodeado de 1 celda: si su tamaño es mayor que el más grande descubierto hasta ahora, regístrelo como el nuevo rectángulo más grande. De lo contrario (si no hay una fila sólida de 1 celda en la siguiente línea hacia abajo), ninguna de las 0 celdas examinadas puede ser parte de ningún rectángulo 0 sólido: márquelas todas como visitadas y goto 1.

Hay diversos rectángulos en dados de 1000 x 1000. en la <Figure 1> , el "1" en serie que se muestra como una celda amarilla es el patrón del rectángulo. El tamaño mínimo del rectángulo en <Figure 1> es 3 x 3 mostrado como celda verde.

Debería haber al menos uno de ''0'' dentro del rectángulo.

Pero, en esta matriz, existe una forma no cerrada o un patrón de línea recta también.

(El valor inicial de la matriz es ''0'', y los patrones se representan como una serie de ''1''. No se superponen ni se incluyen entre sí.)

¿Cuál podría ser un algoritmo eficiente para encontrar los regtangles completos en la matriz, excepto la forma no cerrada o la línea recta? Por ejemplo, en la figura de arriba, el número de rectángulos completos es 3

Esto es bastante simple. Si tiene n cuadrados, puede contar los rectángulos en O(n) .

Suposiciones

  • Los bordes de cada rectángulo válido no comparten ninguna celda con una ruta no válida.
  • Si un rectángulo está dentro de otro, te encantaría encontrarlos.

Necesitaría memoria extra tan grande como la entrada. Llamemos a esto visited e inicialicemos con 0.

Primero construyamos una función auxiliar:

is_rectangle(square s) from s, go right while you see 1s and visited is 0 mark them as 1 in visited if less than 3 steps return 0 then, go down while you see 1s and visited is 0 mark them as 1 in visited if less than 3 steps return 0 then, go left while you see 1s and visited is 0 mark them as 1 in visited if less than 3 steps return 0 then, go up while you see 1s and visited is 0 mark them as 1 in visited if then one above is not s return 0 return 1

Esta función básicamente rastrea los 1s en las direcciones de derecha-abajo-izquierda-arriba y verifica si se cumplen las condiciones (longitud al menos 3 y que llega a la posición inicial). También marca las plazas visitadas.

Lo importante a tener en cuenta acerca de esta función, es que funciona correctamente solo si el cuadrado inicial es la esquina superior izquierda.

Ahora, la solución al problema es fácil:

num_rectangles = 0 initialize visited to 0 (rows x columns) for r in rows for c in columns if visitied[r][c] or image[r][c] == 0 continue num_rectangles += is_rectangle(<r,c>) return num_rectangles

Así es como se ejecuta el algoritmo:


1. Parte fallida (y marcada) de un rectángulo defectuoso


2. Encontró (y marcó) un rectángulo.


3. Falló en un solo cuadrado (de una línea vertical)


4. Falló en un solo cuadrado (de una línea vertical)


5. Falló en un solo cuadrado (de una línea vertical)


6. Después de muchos pasos similares, encontré el siguiente rectángulo.


7. Y el siguiente rectángulo.


8. Fin del algoritmo

Esto es lo que pienso, podría ser bastante ineficiente en recursos. No sé sobre eso.

  1. Recorra a lo largo de una fila a menos que encuentre al menos 3 1 s.
  2. Desplácese hacia abajo y boolean y boolean con las filas a continuación -> deben tener el formato de 100..001 si es un rectángulo válido. (Asumiendo que puedes hacer todas las operaciones boolean )
  3. Ha encontrado un rectángulo cuando ha encontrado al menos una fila en el paso 2, y finalmente todos los 1 s.
  4. Repita con el siguiente elemento de la fila!

Pensé en ello un rato. Se me ocurrió este método:

1) elimine todos los ceros alrededor de los bordes - cambie su valor a 2

2) llenar la matriz alrededor de los 2

esto te deja solo con la isla de los ceros, que ahora se puede probar para la convexidad. Así que para cada isla:

3) busque la extensión del valor 0 en X e Y - le da un potencial rect interno

4) si el rect interior contiene un 1 O el rect externo contiene un 0, rellene esta isla con 2s ya que no es convexo (por lo tanto, no es un rectángulo)

Suponiendo que pueda encontrar un buen algoritmo de relleno de inundación (no como el mío), esto debería ser eficiente para cortar el espacio de búsqueda rápidamente.

Y ahora para el código (lo siento es C sharp):

using System; using System.Collections.Generic; namespace Test { class MainClass { static private int [,] matrix = new int[,] { {0,0,0,0,0,0,0,0,1,1,1,1,0,0,0}, {0,1,1,1,1,1,1,0,1,0,0,1,0,1,0}, {0,1,0,0,0,0,1,0,1,0,0,1,0,1,0}, {0,1,0,0,0,0,1,0,1,0,0,1,0,1,0}, {0,1,0,0,0,0,1,0,1,0,0,0,0,1,0}, {0,1,0,0,0,0,1,0,1,0,0,0,0,1,0}, {0,1,1,1,1,1,1,0,1,0,0,1,0,1,0}, {0,0,0,0,0,0,0,0,1,1,1,1,0,0,0}, {0,0,1,1,1,1,0,0,0,0,0,0,0,0,0}, {0,0,1,0,0,1,0,0,1,1,1,0,1,1,0}, {0,0,1,1,1,1,0,0,1,0,1,0,0,0,0}, {0,0,0,0,0,0,0,0,1,1,1,0,0,0,0} }; static private int width = matrix.GetLength(0); static private int height = matrix.GetLength(1); private const int DEAD = 2; private const int RECT = 3; public static void Main (string[] args) { //width = matrix.GetLength(0); //height = matrix.GetLength(1); PrintMatrix (); EliminateFromEdges (DEAD); PrintMatrix (); FloodFill (DEAD); // very inefficient - find a better floodfill algorithm PrintMatrix (); // test each island of zeros for convexness for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { if (matrix[i,j] == 0) { if (TestIsland(i,j) == false) { // eliminate this island as it is not convex matrix[i,j] = DEAD; FloodFill(DEAD); PrintMatrix (); } else { // flag this rectangle as such matrix[i,j] = RECT; FloodFill(RECT); PrintMatrix (); } } } } // We''re done, anything flagged as RECT can be expanded to yield the rectangles PrintMatrix (); } // flag any zero at edge of matrix as ''dead'' static private void EliminateFromEdges(int value) { for (int i = 0; i < width; i++) { if (matrix [i, 0] == 0) { matrix [i, 0] = value; } if (matrix [i, height - 1] == 0) { matrix [i, height - 1] = value; } } for (int j = 1; j < height - 1; j++) { if (matrix [0, j] == 0) { matrix [0, j] = value; } if (matrix [width - 1, j] == 0) { matrix [width - 1, j] = value; } } } // propagte a value to neighbouring cells static private void FloodFill (int value) { bool change_made = true; // set to true to start things off while (change_made) { change_made = false; for (int i = 1; i < width - 1; i++) { for (int j = 1; j < height - 1; j++) { if ((matrix [i, j] == 0) && ((matrix [i - 1, j] == value) || (matrix [i + 1, j] == value) || (matrix [i, j - 1] == value) || (matrix [i, j + 1] == value))) { matrix [i, j] = value; change_made = true; } } } } } static private bool TestIsland (int x, int y) { // find convex extend of island int x2 = x; int y2 = y; while (matrix[++x2, y] == 0); x2--; while (matrix[x,++y2] == 0); y2--; // check inner cells (want all zeroes) for (int i = x; i <= x2; i++) { for (int j = y; j <= y2; j++) { if (matrix[i,y] != 0) { return false; } } } // check surrounding cells (want all ones) x--; y--; x2++; y2++; for (int i = x; i <= x2; i++) { if ((matrix[i,y] != 1) || (matrix[i,y2] != 1)) { return false; } } for (int j = y + 1; j <= y2 - 1; j++) { if ((matrix[x,j] != 1) || (matrix[x2,j] != 1)) { return false; } } return true; } // for debug purposes static private void PrintMatrix () { for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { switch(matrix[i,j]) { case DEAD: Console.Write("-"); break; case RECT: Console.Write("+"); break; default: Console.Write(matrix[i,j]); break; } } Console.WriteLine(); } Console.WriteLine(); } } }

La salida de este código.

000000001111000 011111101001010 010000101001010 010000101001010 010000101000010 010000101000010 011111101001010 000000001111000 001111000000000 001001001110110 001111001010000 000000001110000 --------1111--- -1111110100101- -1000010100101- -1000010100101- -1000010100001- -1000010100001- -1111110100101- -0000000111100- -0111100000000- -0100100111011- -0111100101000- --------111---- --------1111--- -111111-1--1-1- -100001-1--1-1- -100001-1--1-1- -100001-1----1- -100001-1----1- -111111-1--1-1- --------1111--- --1111--------- --1001--111-11- --1111--101---- --------111---- --------1111--- -111111-1--1-1- -1++++1-1--1-1- -1++++1-1--1-1- -1++++1-1----1- -1++++1-1----1- -111111-1--1-1- --------1111--- --1111--------- --1001--111-11- --1111--101---- --------111---- --------1111--- -111111-1--1-1- -1++++1-1--1-1- -1++++1-1--1-1- -1++++1-1----1- -1++++1-1----1- -111111-1--1-1- --------1111--- --1111--------- --1++1--111-11- --1111--101---- --------111---- --------1111--- -111111-1--1-1- -1++++1-1--1-1- -1++++1-1--1-1- -1++++1-1----1- -1++++1-1----1- -111111-1--1-1- --------1111--- --1111--------- --1++1--111-11- --1111--1+1---- --------111---- --------1111--- -111111-1--1-1- -1++++1-1--1-1- -1++++1-1--1-1- -1++++1-1----1- -1++++1-1----1- -111111-1--1-1- --------1111--- --1111--------- --1++1--111-11- --1111--1+1---- --------111----

Si solo puede tener formas rectangulares en su matriz, es equivalente a un problema clásico de cálculo en imágenes binarias: simplemente aplique un algoritmo estándar para los componentes conectados. Etiqueta solo los componentes conectados de 0 y los cuenta.

Ver http://en.wikipedia.org/wiki/Connected-component_labeling por ejemplo. Este tipo de algoritmo es bastante simple en imágenes, pero requiere cierta cantidad de memoria (el mismo tamaño que la matriz de entrada, de tipo corto o int). Tenga cuidado con la conectividad: si elige la conectividad 4, contará rectángulos cerrados incluso si faltan algunas esquinas. Pero el algoritmo es más simple que con conectividad 8.

Si puede tener formas encerradas más complejas, simplemente agregue un procesamiento posterior: para cada componente conectado, cuente la cantidad de píxeles dentro del cuadro delimitador del componente (si los dos números son iguales, tiene un rectángulo)