- •«Разработка автоматизированной системы проектирования прокладки кабелей в офисных помещениях»
- •Реферат
- •Введение
- •1 Анализ современного состояния теории и практики автоматизированного проектирования лвс в жилых и офисных помещениях
- •1.1 Обзор программных комплексов
- •1.2 Анализ преимуществ и недостатков конкурентных программ автоматизированного проектирования лвс
- •2 Развитее методики автоматизированного проектирования лвс в жилых и офисных помещениях
- •2.1 Разработка общей концепции системы
- •2.2 Разработка математической модели
- •2.3 Разработка объектно – ориентированной модели программы
- •2.3.1 Контекстная диаграмма
- •2.3.2 Диаграмма состояний
- •2.3.3 Диаграмма потоков данных
- •2.4 Алгоритмы устранения геометрических искажений
- •2.4.1 Алгоритмы отсечения
- •2.4.2 Алгоритмы заполнения и заливки
- •2.4.3 Алгоритмы заполнения
- •2.4.4 Алгоритм построчного заполнения
- •2.4.5 Алгоритмы заливки
- •3 Реализация программного комплекса автоматизированного проектирования лвс в жилых и офисных помещениях
- •3.1 Разработка автоматизированной системы проектирования лвс на основе оригинальной математической модели
- •3.2 Разработка интерфейса программы
- •3.3 Руководство по разработке автоматизированной системы
- •3.4 Методические рекомендации по использованию автоматизированной системы проектирования лвс в жилых и офисных помещениях
- •Заключение
- •Список литературы
2.4.5 Алгоритмы заливки
В алгоритмах заливки задается заливаемая (перекрашиваемая) область, код пиксела, которым будет выполняться заливка и начальная точка в области, начиная с которой начнется заливка.
Виды заливок:
- простой алгоритм заливки с затравкой;
- построчный алгоритм заливки с затравкой.
По способу задания области заливки делятся на два типа:
1) Гранично-определенные, задаваемые своей (замкнутой) границей такой, что коды пикселев границы отличны от кодов внутренней, перекрашиваемой части области. На коды пикселев внутренней части области налагаются два условия - они должны быть отличны от кода пикселев границы и кода пикселя перекраски. Если внутри гранично-определенной области имеется еще одна граница, нарисованная пикселями с тем же кодом, что и внешняя граница, то соответствующая часть области не должна перекрашиваться;
2) Внутренне-определенные, нарисованные одним определенным кодом пикселя. При заливке этот код заменяется на новый код закраски.
По способам доступа к соседним пикселям области делятся на 4-х и 8-ми связные.
В 4-х связных областях доступ к соседним пикселям осуществляется по четырем направлениям - горизонтально влево и вправо и в вертикально вверх и вниз.
В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность мы может, двигаясь от точки затравки, достичь и закрасить все пиксели области [20].
4-х связную область мы можем заполнить как 4-х, так и 8-ми связным алгоритмом. Обратное же неверно. Так, область на рис.2.16.(а) мы можем заполнить любым алгоритмом, а область на рис.2.16. (б), состоящую из двух примыкающих 4-х связных областей можно заполнить только 8-ми связным алгоритмом.
С использованием связности областей и стека можно построить простые алгоритмы закраски как внутренне, так и гранично-определенной области.
Рисунок.2.16.– Связность областей и их границ
Простой алгоритм заливки может быть выполнен двумя способами:
- в рекурсивной реализации;
- в итеративной реализации.
Алгоритм заливки в рекурсивной реализации гранично-определенной 4-х связной области выполняется в следующем порядке:
- определяется, является ли пиксель граничным или уже закрашенным;
- если нет, то пиксель перекрашивается, затем проверяются и если надо перекрашиваются 4 соседних пикселя.
Несмотря на простоту, рекурсивная реализация проигрывает итеративной в том, что требуется много памяти для сохранения вложенных вызовов.
Логика работы итеративного алгоритма заливки 4-х связной гранично-определенной области следующая:
1. Поместить координаты затравки в стек;
2. Если стек не пуст, извлечь из него координаты пикселя;
3. Перекрасить пиксель;
4. Для всех четырех соседних пикселев проверить, является ли он граничным или уже перекрашен;
5. Если нет, то занести его координаты в стек.
На рис.2.17 (а) показан выбранный порядок перебора соседних пикселев, а на рис.2.17 (б) соответствующий ему порядок закраски простой гранично-определенной области.
Рисунок 2.17. – Заливка 4-х связной области итеративным алгоритмом
Как уже отмечалось, очевидный недостаток алгоритмов непосредственно использующих связность закрашиваемой области - большие затраты памяти на стек, так как на каждый закрашенный пиксель в стеке по максимуму будет занесена информация о еще трех соседних. Кроме того, информация о некоторых пикселях может записываться в стек многократно. Это приведет не только к перерасходу памяти, но и потере быстродействия за счет многократной раскраски одного и того же пикселя. Значительно более экономен далее рассмотренный построчный алгоритм заливки.
Построчный алгоритм заливки.
Использует пространственную когерентность, при которой:
- пиксели в строке меняются только на границах;
- при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксель.
Таким образом, на каждый закрашиваемый фрагмент строки в стеке хранятся координаты только одного начального пикселя, что приводит к существенному уменьшению размера стека.
Последовательность работы алгоритма для гранично-определенной области следующая:
1. Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4.
2. Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксель. Пусть это Хлев и Хправ, соответственно.
3. Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек.
4. То же самое проделывается для строки выше закрашиваемой [16].
В результате проведенного анализа алгоритмов поиска кратчайшего пути основой для разработки автоматизированной системы прокладки интернет кабелей был выбран алгоритм Дейкстры, потому как он наиболее точнее и быстрее справляется с поставленной задачей. Также был проведен структурный анализ данных, в ходе которого были построены следующие диаграммы: диаграмма потоков данных, диаграмма состояний и контекстная диаграмма на основе созданной математической модели [18].
