En los autómatas celulares , la vecindad de Moore se define en una celosía cuadrada bidimensional y se compone de una celda central y las ocho celdas que la rodean.
Nombre
El barrio lleva el nombre de Edward F. Moore , un pionero de la teoría de los autómatas celulares.
Importancia
Es uno de los dos tipos de vecindarios más utilizados, el otro es el vecindario de von Neumann . El conocido Juego de la vida de Conway , por ejemplo, usa el vecindario de Moore. Es similar a la noción de 8 píxeles conectados en los gráficos por computadora .
La vecindad de Moore de una celda es la celda misma y las celdas a una distancia de Chebyshev de 1.
El concepto se puede extender a dimensiones más altas, por ejemplo, formando un vecindario cúbico de 26 celdas para un autómata celular en tres dimensiones, como lo usa 3D Life . En la dimensión d, el tamaño del vecindario es 3 d - 1.
En dos dimensiones, el número de celdas en un vecindario extendido de Moore, dado su rango r es (2 r + 1) 2 .
Algoritmo
La idea detrás de la formulación de la vecindad de Moore es encontrar el contorno de un gráfico dado. Esta idea fue un gran desafío para la mayoría de los analistas del siglo XVIII y, como resultado, se derivó un algoritmo del gráfico de Moore que más tarde se denominó algoritmo del vecindario de Moore.
La siguiente es una descripción formal del algoritmo de rastreo Moore-Neighbor:
Entrada : una teselación cuadrada, T, que contiene un componente P conectado de celdas negras.Resultado : Una secuencia B (b1, b2, ..., bk) de píxeles de contorno, es decir, el contorno.Defina M (a) como la vecindad de Moore del píxel a.Sea p el píxel de límite actual.Sea c el píxel actual que se está considerando, es decir, c está en M (p).Sea b el retroceso de c (es decir, el píxel vecino de p que se probó previamente) Comience el Conjunto B para que esté vacío. De abajo hacia arriba y de izquierda a derecha, escanee las celdas de T hasta encontrar un píxel negro, s, de P. Inserte s en B. Establezca el punto límite actual p en s, es decir, p = s Sea b = el píxel desde el que se ingresó s durante el escaneo de la imagen. Configure c para que sea el siguiente píxel en el sentido de las agujas del reloj (desde b) en M (p). Mientras que c no es igual a s, si c es negro insertar c en B Sea b = p Sea p = c (retroceso: mueva el píxel actual c al píxel desde el que se ingresó p) Sea c = siguiente píxel en el sentido de las agujas del reloj (de b) en M (p). else (avanzar el píxel actual c al siguiente píxel en el sentido de las agujas del reloj en M (p) y actualizar el retroceso) Sea b = c Sea c = el siguiente píxel en el sentido de las agujas del reloj (de b) en M (p). end If end while end
Condición de terminación
La condición de terminación original era detenerse después de visitar el píxel de inicio por segunda vez. Esto limita el conjunto de contornos que el algoritmo recorrerá por completo. Una condición de detención mejorada propuesta por Jacob Eliosoff es detenerse después de ingresar el píxel de inicio por segunda vez en la misma dirección en la que lo ingresó originalmente.
Ver también
Referencias
- Weisstein, Eric W. "Vecindario de Moore" . MathWorld .
- Tyler, Tim, el barrio de Moore en cell-auto.com