Лекция 4 2




Скачать 42.05 Kb.
НазваниеЛекция 4 2
Дата публикации09.06.2014
Размер42.05 Kb.
ТипЛекция
litcey.ru > Право > Лекция


Лекция 4 2

Зайцев В.И. 2

Устюгова Е.Н. 2

Методы преобразования точек в кривые 2



Лекция 4

Зайцев В.И.

Устюгова Е.Н.




Методы преобразования точек в кривые



Метод Хоха.



Имеется множество состоящее из n точек { (xi ,yi ), i=1,…,n }, составляющих прямую L.
Для каждой точки (xi ,yi )L, соединяя ее с началом координат, находим значения  и , удовлетворяющих равенству = xicos + yisin.

Рассматриваем несколько отрезков принадлежащих исходной прямой, а остальные точки отбрасываем.

Проводим квантование параметров  и  строим соответствующую матрицу (например, 50x50)

Для каждой из точек, изменяя значение параметра  от 0 до 360, получаем значение параметра  из формулы = xicos + yisin. Затем к элементу матрицы, стоящему на пересечении столбца, отвечающего , и строки со значением , прибавляем 1. В результате будет выделена линия.
Если попытаться применить этот метод для выделения окружности, то потребуется три параметра (x,y,r) и следовательно будет необходима 3D матрица.
Итеративный подбор концевых точек.

Имеем кривую АСDB

1. Находим самые удаленные по горизонтали точки (т.е. максимальное и минимальное значение x -- А, B)

2.Cоединяем точки А и В. Вычисляем расстояния от всех точек до прямой АВ, и если все полученные значения меньше заданного порога, то процесс завершается. Иначе ищем самую удаленную точку – С и строим отрезки AC и DC.

3. Затем ищем самые удаленные точки от прямых BC и АС, для прямой AC точка D находиться достаточно близко, а для прямой BC она является удаленной. Следовательно, строим отрезки CD и BD.

Теперь все точки лежат достаточно близко от всех прямых, следовательно, процесс завершен.

^

Цепное кодирование.



Рассматриваем сетку, из каждой точки такой сетки можно двинуться в восьми направлениях.

Из этих восьми точек выбираем наиболее близкую к кривой и переходим к ней, затем производим перекодировку (т.е. для этой новой точки нумеруем соседей 0,1,2…7 – против часовой стрелки). Таким образом, записывая номера в сетке точек, к которым переходим, строим ход.

Целью является последовательность точек a=a,…,an , а полученная цепь имеет вид b=b1,…,bn .

Рассмотрим корреляционную функцию

Cab=1/ni=1aibi , cos(ai -bi )

Если цепочки идеально совпадают, то Cab = (1+…+1)/n =1. Вообще, Cab  1. Вокруг цепочки можно построить габаритный прямоугольник.

Изменение направления обхода означает перенумерацию, т.е. увеличивается либо уменьшается или только x, или у, или x и y вместе (например, полученный код будет иметь вид 001120).

При цепном кодировании возможны следующие операции:

  • Измерение длины цепи

  • Описание прямоугольника

  • Изменение направления обхода

  • Площадь замкнутого контура

  • Моменты инерции

  • Кратчайшая цепь

  • Расстояния между двумя точками

  • Зеркальная цепь


Представление контура цепным кодом состоит из абсолютного адреса начальной точки и последовательности ключевых слов («0» – «7»), указывающих направления отрезков прямой, соединяющей соседние пикселы.

Существует дифференциальный код, при котором соседи кодируются 0, 1, 2, 3, 4, причем в целях экономии эти коды записывают как последовательности 0 и1:

‘0’ – 0;

‘+1’ – 01;

‘-1’ – 011;

‘+2’ – 0111;

‘-2’ – 01111; и т.д.

Возможны и другие варианты кодирования. «Соседи» номеруются также, но коды в 0 и 1 выглядят иначе:

‘0’ – 0;

‘+1’ – 100;

‘-1’ – 101;

‘+2’ – 1100;

‘-2’ – 1101;

‘+3’ – 1110;

‘-3’ – 1111, и т.д.
При векторном построении прямую изображают штрихами из-за того, что перо может двигаться в восьми направлениях. При плохом (низком) расширении эти штрихи видны невооруженным взглядом.

Вопрос выбора следующей точки можно решать с помощью алгоритма Брезенхема:

Алгоритм Брезенхема.
Предположим, что точка (i,j) – начальная. Тогда рассмотрим только точки первого октанта, т.е точки с координатами (x,y) такими, что xy0. В этом октанте возможны только два направления дальнейшего движения: по горизонтали на право или же на право под углом 45. Шаг по горизонтали направо делается в случае, если r < q, т.е. r-q<0:

r = y/x(i+1) – j;

q = j+1– y/x(i+1);

(y/x(i+1)–j)–(j+1–y/x(i+1))=2y/x(i+1) –2j–1<0
Считаем, что x>0, иначе если x = 0, то останется та же точка, т.к. тогда y = 0.

2(y(i+1) – xj) – x = Di = 2(yi – xj)+2y – x <0 .

А
лгоритм:


Если Di <0, то осуществляем шаг по оси ( i=i+1, j=j, Di+1= Di+2y)

Если Di >0, то шаг по диагонали ( i=i+1, j=j+1, Di+1 = Di +2(y-x)), где D0 =2y –x при i=j=0.

Если мы рассматриваем прямые, лежащие во втором октанте, то осевой шаг – шаг по j (j=j+1, i=i), а диагональный шаг не изменяется. Для третьего октанта осевой шаг – шаг по j, шаг по диагонали i=i-1, j=j+1 и т.д..

Количество совершенных осевых шагов равно (x-y), и каждый шаг по y становиться диагональным, следовательно, всего необходимо совершить x шагов.
Если кривая равноудалена от двух соседних точек, то можно взять любую из них и построить две равноценные ломанные, которые после прохождения этих точек совпадают.
Однако при таком приближении кривой диагональные и горизонтальные составляющие будут иметь различную яркость (горизонтальная линия будет в 2 раз ярче).

Алгоритм выбора средней точки (Midpoint algorythm).
Для алгоритма выбора среднней точки линия представляется в виде F(x,y) = 0. Выбор между N и NE осуществляется слеующим образом.

О
пределим:

Е
сли выбрали E:

Е
сли выбрали NE:

П

роцесс повторяется при прохождении по х. На каждом шаге делается выбор между E/NE.

Инициализация.

Для того, чтобы получить алгоритм, в котором используется арифметика только над целыми числами.
И
так, определим:

Приведенная ниже программа предполагает, что х1 меньше х2.
drawline(x1, y1, x2, y2, colour)

int x1, y1, x2, y2, colour;

{

int dx, dy, d, incE, incNE, x, y;

dx = x2 - x1;

dy = y2 - y1;

d = 2*dy - dx;

incE = 2*dy;

incNE = 2*(dy - dx);

y = y1;

for (x=x1; x<=x2; x++)

{

setpixel(x, y, colour);

if (d>0) { d = d + incNE; y = y + 1; }

else d = d + incE;

}

}




Похожие:

Лекция 4 2 iconЛекция «Сущность и проблемы вэд, состояние вэд в России» 1 час. 2...
Лекция «Внешнеэкономические операции и сделки: виды, классификация, организация» 1 час
Лекция 4 2 iconЛекция №1
Лекция № Общие принципы эффективной организации учебного процесса. Физиологиче­ская цена учебных нагрузок
Лекция 4 2 iconЛекция №1
Лекция № Общие принципы эффективной организации учебного процесса. Физиологиче­ская цена учебных нагрузок
Лекция 4 2 iconЛекция №1
Лекция № Общие принципы эффективной организации учебного процесса. Физиологиче­ская цена учебных нагрузок
Лекция 4 2 iconЛекция №1
Лекция № Общие принципы эффективной организации учебного процесса. Физиологиче­ская цена учебных нагрузок
Лекция 4 2 iconНеделя с 05. 12. 2011 по 11. 12. 2011 Дни Пара Время 2511-зво 2512-зво...
Организация таможенного контроля товаров и транспортных средств. (Лекция) проф. Кулешов А. В. ауд. 108
Лекция 4 2 iconЛекция 11. Элементарные механизмы образования дисперсных систем
Эта лекция посвящена анализу элементарных механизмов формирова-ния текстуры катализаторов и носителей, которые непосредственно следуют...
Лекция 4 2 iconЛекция № Предмет и история биомеханики Лекция № Кинематика движений человека
Для правильной подготовки спортсменов высокой квалификации тренер должен владеть глубокими знаниями по основным естественным дисциплинам....
Лекция 4 2 iconЧисленность и воспроизводство населения мира. Демографическая политика
По типу данный урок является уроком общего разбора темы и методики ее изучения. По своей дидактической цели это урок сообщения нового...
Лекция 4 2 iconЛекция представителей ООО «Хевел»
Лекция представителей ООО «Хевел» с учащимися классов и-9-1, и-9-2, и-10-1, и-10-2
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
litcey.ru
Главная страница