|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
11.01.2010, 22:46 | #1 |
Пользователь
Регистрация: 09.01.2010
Сообщений: 17
|
Нужно найти связную область одного цвета начиная с произвольной точки.
Привет всем. Помогите подготовиться к экзамену. Еcть вот такой вопрос по алгоритму, не могу найти нужный алгоритм.
Есть большое изображение, допустим 10000x10000. Каждая точка такого изображения описывается по сути каким то числом(т. е. цветом). Нужно найти связную область одного цвета начиная с произвольной точки. Нужен наиболее оптимальный алгоритм такого поиска. Может у кого-нибудь есть какие нибудь мысли, можно конечно алгоритм типа перебора всех точек одна за одной и сравнивать текущую точку с ближайшими но он далеко не оптимален. |
11.01.2010, 23:08 | #2 |
Удален
Форумчанин
Регистрация: 02.12.2009
Сообщений: 309
|
а изображение как задается? перечислением чисел?
|
11.01.2010, 23:11 | #3 |
Новичок
Джуниор
Регистрация: 11.01.2010
Сообщений: 5
|
Если честно тут этого не указано, думаю что да.
Как я понимаю можно взять просто любое изображение и за место цветов,грубо говоря в каждой точке написать число соответствующее этому цвету. |
11.01.2010, 23:11 | #4 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Правильно я понял задание, надо найти максимальную по площади связную область одного (любого) цвета в пределах данной матрицы?
Где "узкое место" ограничений, нас поджимает время или память? Для 100 млн точек могу посоветовать банальный обход в ширину. С каждой неотмеченной точки запускать обход в ширину, считать, из скольких точек состоит связная область одного цвета, включающая эту точку, и отмечать все эти точки в процесе подсчета, чтоб не повторять одно и то же много раз (иначе, к примеру, область из 1000 точек будет считаться 1000 раз - при обходе из каждой из этих точек). Так мы можем найти число-ответ. Можно хранить так же координаты любой точки из области-ответа, тогда можно будет восстановить и саму область, а не только ее размер. Время выполнения - О(N), память - O(N) (N - число точек массива). Коэфициент по времени чуть великоват может быть (если картинка с очень малым количеством областей из 2 и больше точек, то условно в 5 раз хуже самого оптимального случая), остальное сойдет на базовом уровне алгоритмики. Или надо более красивое/оптиммальное решение? |
11.01.2010, 23:15 | #5 |
Новичок
Джуниор
Регистрация: 11.01.2010
Сообщений: 5
|
Kostyan142 щас занят, я его одногруппник, привет все пока буду за него.
На сколько мы понимаем нужно найти любую, первую которая попадется область, а поджимает нас время. Алгоритм должен быть оптимален по времени. |
11.01.2010, 23:25 | #6 |
Пользователь
Регистрация: 09.01.2010
Сообщений: 17
|
Нам самое главное чтобы алгоритм поиска был оптимален по времени, а область искать любую, не обязательно самую большую.
Ну то что любую это предположение. Последний раз редактировалось kostyan142; 11.01.2010 в 23:25. Причина: Поправка |
11.01.2010, 23:30 | #7 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Любую область (хотя бы одну)?
Тогда можно тоже обход в ширину. Быстрее линейного времени без строго определенной доп.информации не получится. Простой пример по поводу доп.информации - количество возможных цветов конечно? Оно большое? Кстати, если можно - хотел бы увидеть наработки на текущий момент - оценил бы, скажем, продуктивность на матрице 10000*10000 по среднему времени на 100 случайных тестах. Было бы с чем сравнивать. Конкретные числа по ограничениях можно? И еще, картинка на входе (поток, файл?) или уже в памяти (надо написать процедуру для готовой основной части программы). От этого тоже немного зависит, как оптимизировать. |
11.01.2010, 23:33 | #8 |
Пользователь
Регистрация: 09.01.2010
Сообщений: 17
|
Видимо моя вина то что я не сказал что этот вопрос на экзамен в разделе теории т. е. надо просто вкратце рассказать алгоритм и рассказать его оптимальность. Никаких исходных данных даваться не будет, и ничего делать не надо, только теория, в принципе я так полагаю того что вы мне ответили достаточно, так что в любом случае огромное спасибо!!!
|
12.01.2010, 00:06 | #9 |
Пользователь
Регистрация: 09.01.2010
Сообщений: 17
|
Есть еще вопросик, O(N) это расчет времени(оптимальности)?
|
12.01.2010, 00:12 | #10 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
На экзамене всегда можно сказать волшебные "алгоритм был проверен на практике и показал результаты, лучшие, чем такие вот (список алго) по памяти и/или времени".
О(N) - это асимптотическая оценка. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Имеются координаты точки. Как проверить какого цвета соседние точки на форме? | Rin | Мультимедиа в Delphi | 2 | 10.11.2009 22:47 |
Попадание точки в заштрихованную область C# | diman87 | Помощь студентам | 2 | 26.09.2009 14:01 |
входение точки в область, с++ | tipilat | Помощь студентам | 7 | 19.09.2009 00:42 |
Попадание точки в область С++ | Geg[C/c++] | Помощь студентам | 3 | 03.05.2009 12:58 |
Найти координаты хотя бы одной точки, попадающей в область, образованную тремя пересекающимися линиями. | Zibiv | Помощь студентам | 1 | 03.10.2008 17:55 |