Нужно найти связную область одного цвета начиная с произвольной точки.

[kostyan142]

Привет всем. Помогите подготовиться к экзамену. Еcть вот такой вопрос по алгоритму, не могу найти нужный алгоритм.

Есть большое изображение, допустим 10000x10000. Каждая точка такого изображения описывается по сути каким то числом(т. е. цветом). Нужно найти связную область одного цвета начиная с произвольной точки. Нужен наиболее оптимальный алгоритм такого поиска.

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

[Alex_FF]

а изображение как задается? перечислением чисел?

[Студент007]

Если честно тут этого не указано, думаю что да.
Как я понимаю можно взять просто любое изображение и за место цветов,грубо говоря в каждой точке написать число соответствующее этому цвету.

[LeBron]

Правильно я понял задание, надо найти максимальную по площади связную область одного (любого) цвета в пределах данной матрицы?
Где "узкое место" ограничений, нас поджимает время или память?
Для 100 млн точек могу посоветовать банальный обход в ширину. С каждой неотмеченной точки запускать обход в ширину, считать, из скольких точек состоит связная область одного цвета, включающая эту точку, и отмечать все эти точки в процесе подсчета, чтоб не повторять одно и то же много раз (иначе, к примеру, область из 1000 точек будет считаться 1000 раз - при обходе из каждой из этих точек). Так мы можем найти число-ответ. Можно хранить так же координаты любой точки из области-ответа, тогда можно будет восстановить и саму область, а не только ее размер.
Время выполнения - О(N), память - O(N) (N - число точек массива). Коэфициент по времени чуть великоват может быть (если картинка с очень малым количеством областей из 2 и больше точек, то условно в 5 раз хуже самого оптимального случая), остальное сойдет на базовом уровне алгоритмики.
Или надо более красивое/оптиммальное решение?

[Студент007]

Kostyan142 щас занят, я его одногруппник, привет все пока буду за него.
На сколько мы понимаем нужно найти любую, первую которая попадется область, а поджимает нас время. Алгоритм должен быть оптимален по времени.

[kostyan142]

Нам самое главное чтобы алгоритм поиска был оптимален по времени, а область искать любую, не обязательно самую большую.
Ну то что любую это предположение.

[LeBron]

Любую область (хотя бы одну)?
Тогда можно тоже обход в ширину.
Быстрее линейного времени без строго определенной доп.информации не получится.
Простой пример по поводу доп.информации - количество возможных цветов конечно? Оно большое?
Кстати, если можно - хотел бы увидеть наработки на текущий момент - оценил бы, скажем, продуктивность на матрице 10000*10000 по среднему времени на 100 случайных тестах. Было бы с чем сравнивать. Конкретные числа по ограничениях можно?
И еще, картинка на входе (поток, файл?) или уже в памяти (надо написать процедуру для готовой основной части программы). От этого тоже немного зависит, как оптимизировать.

[kostyan142]

Видимо моя вина то что я не сказал что этот вопрос на экзамен в разделе теории т. е. надо просто вкратце рассказать алгоритм и рассказать его оптимальность. Никаких исходных данных даваться не будет, и ничего делать не надо, только теория, в принципе я так полагаю того что вы мне ответили достаточно, так что в любом случае огромное спасибо!!!

[kostyan142]

Есть еще вопросик, O(N) это расчет времени(оптимальности)?

[LeBron]

На экзамене всегда можно сказать волшебные "алгоритм был проверен на практике и показал результаты, лучшие, чем такие вот (список алго) по памяти и/или времени".
О(N) - это асимптотическая оценка.