Подскажите алгоритм или возможно название алгоритма

← →
DVM © (2009-11-10 20:40) [0]

Итак, есть клетчатое поле n x m клеток. Некоторые клетки этого поля - особые (ну, например, черные, а поле само белое, неважно). Особые клетки разбросаны хаотично по полю.

Требуется разбить все такие особые клетки на группы. Клетки входят в одну группу, если касаются друг друга углами или сторонами. Т.е., например, если клетка A касается углом клетки B, которая в свою очередь касается клетки С, то все они принадлежат одной группе.

Результат работы алгоритма - один или несколько прямоугольников (групп), описывающих все клетки каждой группы.

Желательно группировать клетки за один проход, от первой клетки к последней.

Не сталкивался ли кто с таким алгоритмом? Может у методики группировки есть и название?

← →
@!!ex © (2009-11-10 20:57) [1]

за один проход не выйдет.

алгоритм простой:
находим первую клетку. пускаем волну от нее. все клетки, которые захватывает волна помечаем как принадлежащим группе.
Как только волне идти некуда продолжаем поиск.

← →
@!!ex © (2009-11-10 20:59) [2]

за один проход не вйдет - имеется ввиду, что как ни крути просто поэлементной проверкой не обойтись. Все равно будут элементы которые будут проверятся несколько раз.

← →
Pavia © (2009-11-10 21:13) [3]

Алгоритм называется выделение связанных областей.

Делается обычно за два прохода можно за один.

Берем точку тьфу клетку,если черная.
Если ни слева, ни сверху ни слева сверху нет черной то присваиваем клетке счетчик групп. Счетчик увеличиваем на один.

То смотрим если слева или сверху или слева сверху черная то присваиваем номер той клетки. Если к примеру имеем сверху один номер, а слева другой то выбираем любой.

Второй проход нужен что бы объединить вот эти не стыковки.

← →
DVM © (2009-11-10 21:27) [4]

> @!!ex © (10.11.09 20:57) [1]

> пускаем волну от нее. все клетки, которые захватывает волна
> помечаем как принадлежащим группе.

О волновом алгоритме я немного слышал. Но мне кажется он слишком ресурсоемкий выходит. Мне как раз важна скорость. Но все равно, спасибо.

> Pavia © (10.11.09 21:13) [3]

В общих чертах понятно. Спасибо.

← →
Sapersky (2009-11-10 21:27) [5]

http://homepages.inf.ed.ac.uk/rbf/HIPR2/label.htm
Т.е. если мы обнаружили, что закрасили одну фигуру разными цветами, предлагается просто запомнить где-нибудь, что эти цвета эквивалентны, и на втором проходе объединить.

Нашел. http://cgm.computergraphics.ru/content/view/53

Как раз моя задача.

Подскажите алгоритм или возможно название алгоритма Найти похожие ветки