Форум: "Прочее";
Поиск по всему сайту: 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.015 c
15-1257856074     oxffff                2009-11-10 15:27  2010.01.10  
Уважаемый модератор. Почисти и мой последний пост в теме


10-1162211576     Max Ivanych           2006-10-30 15:32  2010.01.10  
Защита диапазона ячеек в Excel


15-1256930126     Суслик_               2009-10-30 22:15  2010.01.10  
Разработка приложения для в рамках в Win Terminal Service


2-1258649675      Виктор                2009-11-19 19:54  2010.01.10  
Использование данных таблицы Paradox в формировании шаблона


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