ALL

АЛГОРИТМЫ ПОСТРОЕНИЯ ЭЛЛИПСОВ

•Эллипс можно описать как модифицированную окружность, радиус которой меняется от максимального значения в одном направлении до минимального значения в перпендикулярном направлении. Прямолинейные отрезки, проведенные внутри эллипса по этим двум перпендикулярным направлениям, называются больший и малой осями эллипса.

•СВОЙСТВА ЭЛЛИПСОВ

•Точное определение эллипса можно дать, воспользовавшись расстояниями от любой точки эллипса до двух фиксированных точек, которые называются его фокусами. Сумма этих двух расстояний одинакова для всех точек эллипса (рис.). Если расстояния от двух фокусов до любой точки P = (x, y) эллипса обозначить d1 и d2, тогда общее уравнение эллипса можно записать как

• d1 + d2 = const.

(34)

•Если выразить расстояния d1 и d2 через координаты фокусов

•F1 = (x1,y1) и F2= (x2,y2), то получится

•	(x x )2	( y y )2		(x x	)2 ( y y		)2 const	(35)
	1	-1		2		2

•Возведя это уравнение в квадрат, собрав члены с одинаковыми

•степенями, и снова возведя в квадрат, можно переписать общее

•уравнение эллипса в виде

• Ax2 + By2 + Cxy + Dx + Ey + F = 0

(36)

Рис. Эллипс с фокусами F1 и F2

•где коэффициенты А, В, C, D, Е и F выражаются через координаты фокусов и длины большой и малом осей эллипса.

•Эллипс можно описать интерактивно через его относительную ориентацию – два фокуса и точку на границе эллипса. Зная координаты этих точек, можно найти константу уравнения (35). После этого вычисляются коэффициенты уравнения (36) и используются для изображения пикселей расположенных на эллиптической траектории.

АЛГОРИТМЫ ПОСТРОЕНИЯ ЭЛЛИПСОВ

1.Уравнения эллипса упрощаются, если эллипс в "стандартном положении", большая и малая оси направлены параллельно осям x

и y. Параметр rx – половина большой оси (большая полуось), а параметр ry — малая полуось. Уравнение эллипса, (рис.а), через координаты центра эллипса и параметры rx и ry:

• ((x – x )/ r )2	+ ((y – y )/ r )2	= 1.	(37)
c x	c y

2. В полярных координатах r и θ эллипс в стандартном положении.

•x = xc + rx cos θ,

• y = yc + ry sin θ.

(38)

•Угол θ, угол эксцентриситета эллипса, измеряется по периметру

ограничивающей окружности. Если rx > ry, радиус ограничивающей окружности r = rx (рис, б). В противном случае радиус равен r = ry.

3.Как и в алгоритме для окружности, можно учесть условия симметрии. Эллипс в стандартом положении симметричен в квадрантах, но не симметричен в двух октантах одного квадранта. Таким образом, нужно найти координаты пикселей на дуге эллипса в одном квадранте, а затем воспользоваться условиями симметрии и найти кривую в остальных трех квадрантах (рис. в).

Рис. в. Симметрия эллипса. Найдя координаты точки (x, у) в одном квадранте, можно узнать координаты точек в трех остальных

Рис. а. Эллипс с центром в точке (xс,yс), большая полуось которого равна rx, а малая – ry

Рис. б. Ограничивающая окружность и угол эксцентриситета θ эллипса, у которого rx > ry

АЛГОРИТМ СРЕДНЕЙ ТОЧКИ ДЛЯ ЭЛЛИПСА

•В этом случае подход аналогичен тону, который использовался при растровом изображении окружности.

•Если известны параметры rx, ry и (xc, yc), можно определить координаты точек (x, y) эллипса

встандартном положении с центром в начале координат, после этого сместить все точки так, чтобы получился эллипс с центром в точке (xc, yc).

•Если потребуется изобразить эллипс в нестандартном положении, можно развернуть его вокруг центральной точки, чтобы переориентировать большую и малую оси в нужном направлении.

•рассмотрим изображения эллипсов в стандартном положении.

•Метод средней точки для эллипса применяется в обеих частях первого квадранта. На рис. показано, как первый квадрант делится на части согласно тангенсу угла наклона эллипса для которого rx < ry.

•При обработке этого квадранта в той части, где тангенс угла наклона кривой меньше 1, выполняются единичные шаги в направлении х,

•а затем в той части, где величина тангенса угла наклона больше 1, выполняются единичные шаги в направлении у.

Рис. Области обработки эллипса. В области 1 тангенс угла наклона эллипса меньше 1, в области 2 тангенс угла наклона больше 1.

АЛГОРИТМ СРЕДНЕЙ ТОЧКИ ДЛЯ ЭЛЛИПСА

•Области I и 2 (рис.) можно обрабатывать различными способами.

•Можно начать с точки (0, ry) и двигаться по часовой стрелке по эллиптической траектории в первом квадранте, а затем перейти от единичного шага по x к единичному шагу по y, когда тангенс угла наклона станет меньше -1.

•Или же можно начать с точки (rx, 0) и выбирать точки в направлении против часовой стрелки, перейдя от единичного шага по y к единичному шагу по x, когда танине угла наклона станет больше –1.

•При наличии параллельные процессоров можно рассчитывать координаты пикселей в двух областях одновременно.

•Для иллюстрации последовательной реализации алгоритма средней точки возьмем

начальное положение в точке (0, ry) и будем перемешаться по эллиптической траектории в первом квадранте но часовой стрелке.

•Определим функцию эллипса из уравнения (37) при (xс, yс) = (0, 0) как

• f	(x, y) = r2	x2 + r2	y2	– r2	x	r2	y	.	(39)
эллипса	y	x

•Эта функция обладает следующими свойствами:

•	< 0, если (x, у) находится с внутренней стороны границы эллипса,
•	f(x, у) = 0, если (х, у) находится на границе эллипса,
•	> 0, если (х, у) находится за границей эллипса.

•Таким образом, функция эллипса fэллипс (x, у) является параметром принятия решения в алгоритме средней точки. В каждой точке выборки определяется следующий пиксель на эллиптической траектории в соответствии со знаком функции эллипса, которая вычисляется в средней точке между двумя возможными положениями пикселей.

АЛГОРИТМ СРЕДНЕЙ ТОЧКИ ДЛЯ ЭЛЛИПСА

•Начиная с точки (0, ry), выполняются единичные шаги по x до тех пор, пока не будет достигнута граница между областью 1 и 2 (рис.). Затем единичные шаги по у на оставшейся части кривой в первом квадранте. На каждом шаге проверить значение тангенса угла наклона кривой (39):

	•	dy/ dx = - 2r		2x/2r 2y	(41)
			y	x		Рис. 3.26. Средняя точка между
	•	На границе между 1 и 2			dy/dx ,
						возможными пикселями в точке
	•	т.е., выход за пределы области 1, когда				выборки хk + 1 на эллиптической
	•	2r	2x 2r 2y	(42)		траектории в 1 области
		y	x

•Предположив, было выбрано положение (xk, yk), найдем следующее положение на эллиптической траектории, вычислив параметр принятия решения в этой средней точке:

• p1

k

= f

(х

k

+1, y

–1/2) = r

2(x

k

+ 1)

2 + r

2(x

y

– 1/2)

2 – r

2 r 2

(43)

эллипс

k

y

x

x

y

•Если p1k < 0, средняя точка находится внутри эллипса, тогда пиксель в строке развертки yk будет ближе к границе эллипса.

•В противном случае средняя точка лежит за пределами эллипса или на его границе, и выбирается пиксель в строке развертки yk – 1.

•В следующей точке выборки (xk+1+1 = xk +2) параметр принятия решения для области 1 ищется как

•или

где yk+1 равно yk либо yk – 1 в зависимости от знака p1k.

АЛГОРИТМ СРЕДНЕЙ ТОЧКИ ДЛЯ ЭЛЛИПСА

•Параметры принятия решения увеличиваются на следующие величины:

•Приращение =

•Приращение для параметров принятия решения вычисляются с использованием только операций сложения и вычитания, как и в алгоритме для окружности, поскольку значения

членов 2ry2x и 2rx2y находятся путем сложения приращений. В начальном положении (0, rу) эти два члена равны

•	2r	2x = 0			(3.45)
	y
•	2r	2y = 2r	2 r	у	(3.46)
	x		x

•С увеличением x и у их новые значения находятся путем прибавления 2ry2 к текущему значению увеличивающегося члена, представленного в уравнении (45), и вычитания 2rx2 из текущего значения члена, представленного в уравнении (46). На каждом шаге сравниваются новые значения приращений, и при выполнении условия (42) мы переходим из области 1 в область 2.

•В области 1 начальное значение параметра принятия решения находится через функцию эллипса в начальной точке (x0, y0) = (0, rу):

•

или

• (47)

АЛГОРИТМ СРЕДНЕЙ ТОЧКИ ДЛЯ ЭЛЛИПСА

•В области 2 выполняется выборка с единичным интервалом в отрицательном направлении координаты у, а средняя точка на каждом шаге теперь берется между горизонтальными пикселями (рис.). Для этой области параметр принятия решения находится следующим образом:

•

•

(48)

•Если p2k > 0, средняя точка находится за пределами эллипса, и выбирается пиксель с координатой хk. Если p2k 0, средняя точка расположена либо внутри эллипса, либо на его границе, и выбирается пиксель с координатой хk+1.

•Чтобы найти взаимосвязь между последовательными параметрами принятия решения в области 2, найдем функцию эллипса для следующего шага дискретизации y k+1 – 1 = y k – 2:

•

(49)

•или

•при хk+1 равном хk или хk + 1 в зависимости от знака p2k.

•

Рис. Средняя точка между возможными пикселями в точке выборки уk — 1 на эллиптической траектории

АЛГОРИТМ СРЕДНЕЙ ТОЧКИ ДЛЯ ЭЛЛИПСА

•Чтобы упростить вычисление р20, положения пикселей можно выбирать в направлении против часовой стрелки, начиная с точки (rx, 0). Тогда единичные шаги выполняются в положительном направлении оси у до тех пор, пока не будет выбрано последнее положение в области 1.

•Описанный алгоритм средней точки можно применять и для создания эллипсов с нестандартным положением, воспользовавшись функцией эллипса (36) и вычисляя координаты пикселей на всей эллиптической траектории.

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

•Предположим, что rx, ry и координаты центра эллипса известны и представлены в целочисленных экранных координатах.

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

•Приращения rx2, ry2, 2rx2 и 2 ry2 находятся один раз в начале процедуры.

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

АЛГОРИТМ СРЕДНЕЙ ТОЧКИ ДЛЯ ЭЛЛИПСА

•1. Ввести rx, rу и координаты центра эллипса (хс, ус), а затем найти первую точку эллипса с центром в начале координат: (x0, y0) = (0, rу)

•2. Вычислить начальное значение параметра принятия решения в области 1: p10 = ry2 - rx2 rу + ¼( rx2)

•Для каждого значения хk в области 1, начиная с k = 0, провести следующую проверку. Если р1k < 0,

следующей точкой эллипса с центром (0, 0) будет (х	, у ) и р1	k+1	= р1	k	+ 2r	2	х	+ r 2
k + 1	k					y	k+1	y

•В противном случае следующей точкой эллипса будет (хk + 1, уk— 1) и р1k+1 = р1k + 2ry2 хk+1 – 2rx2 yk+1 + ry2

•при

•

2r

y

2 х = 2r

2 x + 2r

2,

2r

2 y

k+1

= 2r

2 y

k

– 2r

2

k+1

y k

y

x

x

x

•Данный процесс продолжается, пока не станет 2ry2 х 2rx2у.

•4. Найти начальное значение параметра принятия решения в области 2:

•р20= ry2(x0+1/2)2 + rx2 (y0 – 1)2 - rx2 ry2, где (x0, y0) — координаты последней точки из области 1.

•5. В каждой точке уk в области 2, начиная с k: = 0, выполнить следующую проверку. Если р2k > 0, следующей точкой эллипса с центром в точке (0, 0) будет (хk, уk-1) и р2k+1 = р2k – 2ry2 yk+1 + rx2

•В противном случае следующая точка эллипса будет иметь координаты (хk + 1, уk-1) и

•р2k+1 = р2k + 2ry2 хk+1 – 2rx2 yk+1 + ry2

•Здесь используются те же самые расчеты для приращений по х и у, что и для области 1. Процесс продолжается до тех пор, пока не будет у = 0.

•1. Для обеих областей найти симметричные точки в остальных трех квадрантах.

•2. Переместить каждую найденную точку (x, у) на эллиптическую траекторию с центром в точке (хс, ус) и изобразить точки с такими координатами:

• x = х + хс, у = у + ус

Изображение эллипса методом средней точки

•Известны входные параметры эллипса rx = 8 и ry = 6. Проиллюстрируем шаги алгоритма средней точки для эллипса, определив растровые положения на эллиптической траектории в первом квадранте. Начальные значения и приращения параметра принятия решения вычисляются следующим образом:

•	2r	2x = 0		( с приращением 2r 2	= 72)
	y			y
•	2r	2y = 2r	2 r	(с приращением 2r 2		= –128).
	x	x	у		x

•Для области 1 начальной точкой эллипса с центром в начале координат будет (x0, у0) = (0, 6), а значение начального параметра принятия решения

•p10 = ry2 - rx2 rу + ¼( rx2) = –332.

•Последующие значения параметра принятия решения для метода средней точки и координаты пикселей, образующих эллипс, приведены в таблице.

k	p1		(x	, y	)	2r	2	x	2r	2	y
		k	k+1	k+1			y	k+1		x	k+1
6	-332		(1, 6)				72			768
1	-224		(2, 6)				144			768
2	-44		(3,6)				216			768
3	208		(4, 5)				288			640
4	-108		(5,5)				360			640
5	288		(6, 4)				432			512
6	244		(7, 3)				504			384