Форум: "Прочее";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2010.01.10;
Скачать: [xml.tar.bz2];




Вниз

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


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
Т.е. если мы обнаружили, что закрасили одну фигуру разными цветами, предлагается просто запомнить где-нибудь, что эти цвета эквивалентны, и на втором проходе объединить.



DVM ©   (2009-11-10 21:54) [6]

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

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




Форум: "Прочее";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2010.01.10;
Скачать: [xml.tar.bz2];




Наверх





Память: 0.73 MB
Время: 0.033 c
2-1258375107      defen                 2009-11-16 15:38  2010.01.10  
разрешения для изменения ключей реестра


6-1210789618      EgorovAlex            2008-05-14 22:26  2010.01.10  
При сканировании определённого сегмента сети я нахожу адреса,


15-1258021222     kyn66                 2009-11-12 13:20  2010.01.10  
Что за сайт?


15-1257757397     @!!ex                 2009-11-09 12:03  2010.01.10  
Подскажите софт для просмотра Онлайн ТВ(wpl)


15-1257523019     Nikols                2009-11-06 18:56  2010.01.10  
Программа для удаленного управления.