В клеточных автоматах окрестность Мура определяется на двумерной квадратной решетке и состоит из центральной ячейки и восьми ячеек, которые ее окружают.
Район назван в честь Эдварда Ф. Мура , пионера теории клеточных автоматов.
Это один из двух наиболее часто используемых типов соседства, другой — соседство фон Неймана , которое исключает угловые ячейки. Например, известная игра «Жизнь» Конвея использует соседство Мура. Оно похоже на понятие 8-связанных пикселей в компьютерной графике .
Окрестность Мура ячейки — это сама ячейка и ячейки, находящиеся на расстоянии Чебышева, равном 1.
Эту концепцию можно распространить на более высокие измерения, например, формируя 26-клеточную кубическую окрестность для клеточного автомата в трех измерениях, как это используется в 3D Life . В измерении d, где , размер окрестности равен 3 d − 1.
В двух измерениях число ячеек в расширенной окрестности Мура диапазона r равно (2 r + 1) 2 .
Идея, лежащая в основе формулировки окрестностей Мура, заключается в нахождении контура заданного графа. Эта идея была большим вызовом для большинства аналитиков 18-го века, и в результате из графа Мура был выведен алгоритм , который позже был назван алгоритмом окрестностей Мура.
Псевдокод для алгоритма трассировки Мура-Окрестностей :
Вход : квадратная мозаика T, содержащая связный компонент P черных ячеек. Выход : последовательность B (b1, b2, ..., bk) граничных пикселей, т.е. контур.Определим M(a) как окрестность Мура пикселя a.Пусть p обозначает текущий граничный пиксель.Пусть c обозначает текущий рассматриваемый пиксель, т.е. c находится в M(p).Пусть b обозначает возврат c (т.е. соседний пиксель p, который был ранее протестирован) Начните с пустого множества B. Сканируйте ячейки T снизу вверх и слева направо , пока не найдете черный пиксель s ячейки P. Вставьте s в B. Установите текущую граничную точку p на s, т.е. p=s Пусть b = пиксель, из которого s был введен во время сканирования изображения. Установите c на следующий пиксель по часовой стрелке (от b) в M(p). Пока c не равно s , выполните Если c черный вставьте c в B Пусть b = p Пусть p = c (возврат: перемещение текущего пикселя c в пиксель, из которого был выполнен вход в p) Пусть c = следующий пиксель по часовой стрелке (от b) в M(p). иначе (перемещение текущего пикселя c в следующий пиксель по часовой стрелке в M(p) и обновление возврата) Пусть b = c Пусть c = следующий пиксель по часовой стрелке (от b) в M(p). конец Если конец Пока Конец
Первоначальное условие остановки состояло в остановке после повторного посещения начального пикселя. Это ограничивает набор контуров, которые алгоритм будет полностью проходить. Улучшенное условие остановки, предложенное Якобом Элиософфом, состоит в остановке после повторного входа в начальный пиксель в том же направлении, в котором вы изначально в него вошли.
