Курсоваяработ а «Раскрашивание карты» по дисциплине «Структуры данных»
жүктеу/скачать 1,28 Mb.
|
Отчет Курсовая
- Бұл бет үшін навигация:
- Алгоритм раскраски
- Алгоритм поиска смежных областей
Теоретическая частьДля разработки данного алгоритма были изучены следующие темы: алгоритм раскраски области, определение границ области, раскраска графа, то есть определение в какой цвет, какую область нужно раскрасить. Алгоритм раскраскиБыстрый алгоритм раскраски рекурсивный. Хоть используется рекурсия и активно заполняется стек, скорость раскраски максимальна. Суть алгоритма: Находится белый пиксель, значит область не раскрашена. От исходного пикселя нужно найти самый левый на данной линии (то есть тот, который имеет слева пиксель черного цвета, либо границу). Далее слева направо вся линия раскрашивается в нужный цвет. Возвращаемся к самому левому пикселю на данной линии. Далее проверяется пиксель сверху, потом снизу. Если он белый, то выполняется пункт 2. Если он другого цвета, то проверяется следующий пиксель в этой линии и выполняется пункт 4. Алгоритм поиска смежных областейДля начала реализуется проход по внутренней границе каждой области. От каждого пикселя в сторону ближайшей границы определяется цвет пикселя. Например, для Рисунок 1 – Пример, иллюстрирующий алгоритм поиска смежный областей алгоритм двигается вправо. Для первого пикселя граница черная, для второго тоже и так далее. Было выяснено, что смежные области те, размеры границы до которой меньше ее ширины, проверяя это пикселями справа и слева по пути до области. То есть, начиная со второго пикселя, нужно рассматривать пиксели сверху и снизу, для третьего пиксели через один и так далее. Если один из этих пикселей не равен цвету границы, то поиск останавливается. Если по ширине все пиксели черные, а пиксель, который была получен прямолинейным поиском другой области, имеет цвет другой области, значит это области являются смежными. Рисунок 1 – Пример, иллюстрирующий алгоритм поиска смежный областей жүктеу/скачать 1,28 Mb. Достарыңызбен бөлісу:
|