algorithm - graphs - Búsqueda de áreas contiguas de bits en 2D Bit Array

prim''s algorithm example (2)

De hecho, una vez recibí una pregunta como esta en una entrevista.

Se puede pretender que la matriz es un gráfico y los nodos conectados son los adyacentes. Mi algo implicaría ir 1 a la derecha hasta que encuentre un nodo marcado. Cuando encuentre uno, haga una primera búsqueda que se ejecute en O (n) y evite la recursión. Cuando el BFS vuelva, siga buscando desde donde lo dejó y si el nodo ya ha sido marcado por uno de los BFS anteriores, obviamente no necesita buscar. No estaba seguro de si realmente quería devolver el número de objetos encontrados, pero es fácil hacer un seguimiento simplemente incrementando un contador cuando golpea el primer cuadrado marcado.

Generalmente, cuando se realiza un algoritmo de tipo de relleno de inundación, se coloca en un lugar y se le pide que complete. Dado que se trata de encontrar todas las regiones rellenas de una forma que desee optimizar, es evitar volver a verificar los nodos ya marcados de los BFS anteriores, desafortunadamente en este momento no puedo pensar en una forma de hacerlo.

Una forma pirata de reducir el consumo de memoria sería almacenar un short[][] lugar de un booleano. Luego usa este esquema para evitar hacer una segunda matriz 2D completa

sin marcar = 0, marcado = 1, marcado y sin marcar = 3, marcado y marcado = 3

De esta manera, puede verificar el estado de una entrada por su valor y evitar hacer una segunda matriz.

El problema

Tengo una matriz de bits que representa un "mapa" bidimensional de "mosaicos". Esta imagen proporciona un ejemplo gráfico de los bits en la matriz de bits:

Necesito determinar cuántas "áreas" contiguas de bits existen en la matriz. En el ejemplo anterior, hay dos "áreas" contiguas, como se ilustra aquí:

Los mosaicos deben ubicarse directamente en N, S, E o W de un mosaico para que se consideren "contiguos". Los azulejos que tocan diagonalmente no cuentan.

Lo que tengo hasta ahora

Debido a que estas matrices de bits pueden llegar a ser relativamente grandes (varios MB de tamaño), he evitado intencionalmente el uso de cualquier tipo de recursión en mi algoritmo.

El pseudocódigo es el siguiente:

LET S BE SOURCE DATA ARRAY LET C BE ARRAY OF IDENTICAL LENGTH TO SOURCE DATA USED TO TRACK "CHECKED" BITS FOREACH INDEX I IN S IF C[I] THEN CONTINUE ELSE SET C[I] IF S[I] THEN EXTRACT_AREA(S, C, I) EXTRACT_AREA(S, C, I): LET T BE TARGET DATA ARRAY FOR STORING BITS OF THE AREA WE''RE EXTRACTING LET F BE STACK OF TILES TO SEARCH NEXT PUSH I UNTO F SET T[I] WHILE F IS NOT EMPTY LET X = POP FROM F IF C[X] THEN CONTINUE ELSE SET C[X] IF S[X] THEN PUSH TILE NORTH OF X TO F PUSH TILE SOUTH OF X TO F PUSH TILE WEST OF X TO F PUSH TILE EAST OF X TO F SET T[X] RETURN T

Lo que no me gusta de mi solución

Solo para ejecutarse, se requiere dos veces la memoria de la matriz de mapa de bits que se está procesando.
Al extraer un "área", utiliza tres veces la memoria de la matriz de mapa de bits.
Los duplicados existen en la pila de "fichas para verificar", lo que parece feo, pero no vale la pena evitar la forma en que tengo las cosas ahora.

Que me gustaria ver

Mejor perfil de memoria
Manejo más rápido de grandes áreas.

Solución / Seguimiento

Reescribí la solución para explorar solo los bordes (según la sugerencia de @hatchet).

Esto fue muy sencillo de implementar y eliminó la necesidad de realizar un seguimiento de los "mosaicos visitados" por completo.

Basado en tres reglas simples, puedo atravesar los bordes, realizar un seguimiento de los valores mínimo / máximo de x e y, y completar cuando llegue al principio de nuevo.

Aquí está la demostración con las tres reglas que utilicé:

Un enfoque sería una caminata perimetral. Dado un punto de partida en cualquier lugar a lo largo del borde de la forma, recuerda ese punto.

Comience el cuadro delimitador como sólo ese punto.

Recorra el perímetro usando un conjunto de reglas en el sentido de las agujas del reloj: si el punto utilizado para llegar al punto actual estaba arriba, primero mire a la derecha, luego hacia abajo, luego a la izquierda para encontrar el siguiente punto en el perímetro de la forma. Esto es algo así como la estrategia simple de resolver un laberinto en el que seguimos continuamente una pared y siempre giramos hacia la derecha.

Cada vez que visite un nuevo punto del perímetro, expanda el cuadro delimitador si el nuevo punto está fuera de él (es decir, realice un seguimiento de los valores mínimo y máximo de x e y).

Continuar hasta alcanzar el punto de partida.

Contras: si la forma tiene muchos filamentos de un solo píxel, los volverá a visitar a medida que la caminata regresa.

Ventajas: si la forma tiene grandes extensiones de espacio interno ocupado, nunca tienes que visitarlas o registrarlas como si estuvieras grabando píxeles visitados en un relleno de inundación.

Por lo tanto, conserva el espacio, pero en algunos casos a expensas del tiempo.

Editar

Como suele ser el caso, este problema se conoce, se denomina y tiene múltiples soluciones algorítmicas. El problema que describiste se llama Rectángulo de delimitación mínimo. Una forma de resolver esto es mediante el rastreo de contornos . El método que describí anteriormente está en esa clase y se llama Rastreo de Vecinos de Moore o Barrido Radial . Los enlaces que he incluido para ellos los discuten en detalle y señalan un problema que no había detectado. A veces, volverá a visitar el punto de inicio antes de atravesar todo el perímetro. Si su punto de inicio es, por ejemplo, en algún lugar a lo largo de un ''filamento'' de un solo píxel, lo volverá a visitar antes de terminar y, a menos que considere esta posibilidad, se detendrá prematuramente. El sitio web al que vinculé habla sobre formas de abordar este problema de detención. Otras páginas en ese sitio web también hablan de otros dos algoritmos: Trazado cuadrado y Algoritmo de Theo Pavlidis. Una cosa a tener en cuenta es que estos consideran las diagonales como contiguas, mientras que usted no lo hace, pero eso debería ser algo que se pueda manejar con modificaciones menores a los algoritmos básicos.

Un enfoque alternativo a su problema es el etiquetado de componentes conectados . Sin embargo, para sus necesidades, esta puede ser una solución más costosa de lo que necesita.

Recurso adicional:

Algoritmo de trazado de contorno del vecino de Moore en C ++