JAVA Hole in Grid

Question

Мне нужно найти «дыры» в 2D-сетке в java - можете ли вы указать мне на лучший алгоритм для этого?

С вводом следующих пунктов:

5,3 
5,4 
8,4 
5,5 
6,3 
7,3 
7,4 
6,5 

Мне нужно, чтобы выяснить позиции «дыры» или в окружении пространства в этой сетке. Я немного потерял, как это сделать.

Участок точек:

Предполагая, что каждая точка 1x1

Answer 1

Это в основном алгоритм извлечения блоб + немного дополнительно. Сделайте это:

1) Найдите самую западную, самую восточную, самую северную и самую южную часть любого твердого тела. Помните о них как xmin xmax ymin ymax.

2) Выделите 2d массив целых чисел (с инициализацией на 0) с этими размерами и поместите в него все твердые точки как значение -1.

3) Сделать счетчик инициализированным 1. Сканировать 2-мерный массив. Каждый раз, когда вы находите точку, которая равна 0, установите ее на counter и заливку counter s на каждую смежную точку, которая не равна -1, пока вы не закончите точки, чтобы налить их. (Чтобы сделать заливку, один из способов состоит в том, чтобы сохранить набор всех точек, которые вы еще не залили всеми соседями, и перебрать их, добавив новые точки в набор до тех пор, пока набор не будет исчерпан -> ничего не осталось для заливки на .) Теперь увеличьте счетчик и продолжите.

4) Когда вы проверили всю сетку, просмотрите периметр. Каждый раз, когда вы видите не--1 по периметру, отмечайте, что blob не окружен (имея массив bools, если количество найденных blobs найдено).

5) Каждая пронумерованная капля, которую вы не отметили, окружена.

Читайте о добыче блоба здесь: http://en.wikipedia.org/wiki/Blob_extraction