Лекция 4 1

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

4.1. Метод Хоха 2

4.2. Итеративный подбор концевых точек. 3

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

4.4 Алгоритм Брезенхема. 5

4.4. Метод выбора средней точки 6

Лекция 4

Зайцев В.И.

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

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

Метод Хоха.

Имеется множество состоящее из n точек { (x_i ,y_i ), i=1,…,n }, составляющих прямую L.

Для каждой точки (x_i ,y_i )L, соединяя ее с началом координат, находим значения  и , удовлетворяющих равенству = x_icos + y_isin.

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

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

Для каждой из точек, изменяя значение параметра  от 0 до 360, получаем значение параметра  из формулы = x_icos + y_i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,…,a_{n ,} а полученная цепь имеет вид b=b₁,…,b_n .

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

C_ab=1/n_i=1a_ib_i , cos(a_i -b_i )

Если цепочки идеально совпадают, то C_ab = (1+…+1)/n =1. Вообще, C_ab  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 = D_i = 2(yi – xj)+2y – x <0 .

А
лгоритм:

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

Если D_i >0, то шаг по диагонали ( i=i+1, j=j+1, D_i+1 = D_i +2(y-x)), где D₀ =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;

}

}

7