Veïnat de Moore

En la teoria d'autómates celulars, el Veïnat de Moore es definix com el conjunt de les huit celes que rodegen una cela central en un enreixat quadrat bidimensional. Este criteri de veïnat deu el seu nom a Edward F. Moore, un pioner de la teoria d'autómates celulars. És un dels criteris més utilisats; l'atre és el de la veïnat de von Neumann, formada per les 4 celes que compartixen un costat en la cela central. Per eixemple, en el ben conegut "joc de la vida" de Conway, s'utilisa el veïnat de Moore. És similar a l'idea dels 8 píxels conectats en els gràfics d'ordenador.

Veïnat de Moore

El veïnat de Moore comprén les huit celes que rodegen a la cela central C.

El concepte pot ser estés a dimensions més altes, per eixemple formant un veïnat cúbic de 26-celes per a un autómata celular en tres dimensions, com els utilisats en els "jocs de la vida en 3D".

El veïnat de Moore d'un punt és el conjunt dels punts a una distància de Chebyshov de valor 1 des del punt donat.

El número de celes del veïnat de Moore d'un punt donat considerant r unitats de distància, és:

(2r + 1)² - 1

Aixina, para distancia r=1, val 8; para distancia r=2, val 24; i per a r=3 val 48.

Algoritme

L'idea darrere de la formulació del veïnat de Moore és trobar el contorn d'un grafo donat. Esta idea era un repte important per a molts analistes de el XVIII. Del seu treball va resultar una rutina derivada del grafo de Moore, més vesprada denominada com "algoritme de veïnat de Moore".

A continuació figura una descripció formal de l'algoritme que localisa el veïnat de Moore:

Entrada: Una teselació quadrada, T, contenint un conjunt conexo P de celes negres.
Eixida: Una seqüència B (b1, b2, ..., bk) de píxels de frontera, és dir, el contorn.
Definir M(a) per a ser el veïnat de Moore del píxel a.
p denota el píxel de frontera actual.
c denota el píxel actualment considerat, és dir, c pertany a M(p).
b denota el píxel anterior al c (és dir, el píxel veí al p anteriorment provat)

Escomença
  Buidar B
  Recórrer d'avall a dalt i d'esquerra a dreta, les celes de T fins a trobar un píxel negre s, de
  P Insertar s en
  B Posar el punt de frontera actual p com a s (és dir, p=s)
  Fer b = el píxel des del que s es va introduir durant el recorregut de l'image
  Seleccionar c per a ser el pròxim píxel en el sentit de les agulles del rellonge (des de b) en M(p)
  Mentres c no siga igual a s, fer:
    Si c és negre:
      Insertar c en
      B Fer b = p
      Fer p = c
      (retrocedir: moure el píxel actual c al píxel des del que p va ser introduït)
      Fer c = següent píxel en el sentit de les agulles del rellonge (des de b) en M(p)
    Si no ho és:
      (alvançar el píxel actual c al pròxim píxel en el sentit de les agulles del rellonge en M(p) i actualisar l'orde retrocedir)
      Fer b = c
      Fer c = següent píxel en el sentit de les agulles del rellonge (des de b) en M(p)
    Fi del Si
  Fi del Mentres
Fi

Condició de terminació

La condició de terminació original era parar despuix de visitar el píxel d'inici per segona volta. Açò llimita el conjunt de contorns que l'algoritme recorrerà completament. Una condició de parada millorada proposta per Jacob Eliosoff consistix en parar despuix d'introduir el píxel d'inici per segona volta en la mateixa direcció en la que es va introduir originalment.

Vore també

• Veïnat (teoria de grafos)
• Distància de Chebyshov

Referències

• Moore Neighborhood en MathWorld.
• Tyler, Tim, The Moore neighborhood at cell-auto.com