АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Алгоритм с упорядоченным списком активных ребер (САР)

Читайте также:
  1. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  2. АКТИВНЫХ ОПЕРАЦИЙ КОММЕРЧЕСКОГО БАНКА
  3. Алгоритм
  4. Алгоритм MD4
  5. Алгоритм RC6
  6. Алгоритм RSA
  7. Алгоритм Брезенхема для окружности
  8. Алгоритм Брезенхема.
  9. Алгоритм взятия мазка из носа и зева.
  10. Алгоритм вибіркового методу
  11. Алгоритм вставки элемента в список после элемента с указанным ключом
  12. Алгоритм выполнения прически

Достоинства:

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

Алгоритм:

1. Предполагаем что начальная точка любого ребра многоугольника это точка с большей Y координатой. Для каждого ребра создадим структуру данных: y x dy dx

y - Начальная точка ребра по Y координате

x0 – x координата точки пересечения ребра со сканирующей строкой(крайняя левая точка)

dy – число пересекаемых ребром строк

dx – смещение по X

2.Вычисляем пересечение i+1 сканирующей строки с ребром:

xi+1=xi +1\k , где k=dy\dx тангенс угла наклона ребра

3. Сортируем ребра по возрастанию Y-координаты.

рис3

 

6 12 5 1

3 3 2 -9

11 3 8 2

11 5 3 -5

4. Определяем кол-во вершин встречаемых текущей сканирующей строкой. Если такая вершина имеется , то в список активных ребер вносятся связанные с ней ребра.

5. Отсортировываются Х – координаты точек пересечения ребер с текущей сканирующей строкой.

6. определяются интервалы.

7. Закрашиваются интервалы.

8. Увеличиваем dy на 1.

9. Проверяем САР.

10. Если ребра не пересекается с данной сканир строкой – исключаем его из списка.

Растровая развертка многоуголников.

Достоинства:

1.Медленная операция отрисовки вып всего один раз

Недостатки:

1.Требует доп памяти и усложняет алгоритм

Растровая развертка многоугольников инверсией

Алгоритм использует св-ва операции XOR:

рис4

1.Обозначим через i(x,y) состояние пикселя с коорд x,y.

Если I= 1, если пиксель «включен», иначе «не включен»

2. Последовательно выполняем операцию

i(x+1,y)=1(x+1,y) XOR 1(x,y)

Нюансы – растеризация многоугольников.

Могут быть достигнуты неудовлетворительные результаты если многоугольники будут делить граничные пиксели а оставлять границу между ними недопустимо.

Аппроксимация кривых на плоскости и в пространстве.

Аппроксимация – метод, состоящий в замене одних обьектов другими, в том или ином смысле близкими к исходным, но более простыми.

Аппрокс. ф-ии f(x) это нахождение F(x) которая была бы близка к заданной.

Аппроксимация

Точечная.

В машинной графике на дискретном наборе значений расчетных или экспериментальных данных Тогда по имеющимся данным приближенно вычисляют значение Y в рамках некоторого интервала.



рис5

рис6

частный вид аппроксимации – интерполяция ( налагается строгое условие совпадения в заданных точках xi f(x) От F(x))

Аппроксимация:

-интерполяция

-экстраполяция

Интерполяция :

-глобальная – проходит через все точки заданного интервала

-локальная- интерполируется несколькими ф-иями

-алгебраическая( методы ближайшего соседа)

-полиноминальная

-сплайн-интерполяция


1 | 2 | 3 | 4 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)