ГЛАВА 3

Геометрия декартовой плоскости

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

Мы знаем, что уравнение прямой есть

Y-M*X+C,

где М - тангенс угла между прямой и положительным направлением оси X, С - точка пересечения прямой с осью Y; что означает, что Y-C когда ХЧ). Эта формула широко известна, но она не всегда пригодна. Что произойдет, если прямая вертикальна? М обратится в бесконечность! Более общей формулой является:

A*Y-B*X+C

С помощью этой формулы можно задавать любые прямые; если прямая вертикальна А-0; (В/А) равно тангенсу угла между прямой и положительным направлением оси X; если А-0, то прямая пересекает ось Y в точке (С/А), а если В-0, то ось X в точке (-С/В). Прямая параллельна оси Y, если А-0 и параллельна оси X, если В-0.

Мы будем часто пользоваться этой формулой в дальнейшем, однако введем еще один, быть может более практичный способ определения прямой.

Определим сначала умножение вектора на скаляр и операцию сложения векторов. Пусть даны два вектора Р(1) - (X(1),Y(1)) и Р(2) - (X(2),Y(2)), тогда произведение вектора на скаляр К*Р(1) - (^X^X^Y^)) - равно вектору, составленному из компонента вектора, умноженных на скаляр К. Сумма векторов определяется так:

Р (1)+Р (2)-(Х (1)+X(2),Y(1)+Y(2)) Складываем Х-компоненты друг с другом и Y-компоненты друг с другом, абсолютные значения P(1)=X(l)+Y(1) -это расстояние от начала координат до точки Р (оно также называется длиной вектора, нормой вектора). Для того, чтобы задать прямую, выберем сначала на ней две точки P(1)=(X(1),Y(1)) и P(2)=(X(2),Y(2)). Произвольная точка прямой P(MU)=(X,Y), задается как комбинация умножения на скаляр и сложения векторов:

(1-MU)*P(1)+MU*P(2), где MU-действительное число, что дает вектор

((1-MU)*Х(1)+MU*Х(2),(1-MU)*Y(1)+MU*Y(2)) Мы поместили MU в скобках после Р, чтобы показать, что Р зависит от MU. После того, как мы разберемся в этой зависимости получше, мы будем опускать символ (MU). Если 0<=MU<=1, тогда P(MU) лежит между Р(1)и Р(2). Для любой точки P(MU) значение MU задается с помощью отношения:

расстояние от P(MU) до P(1)

расстояние от P(2) до P(1) где расстояние считается положительным, если P(MU) расположена по ту же сторону от Р(1), что и Р(2), и отрицательным - в противоположном случае. Абсолютное значение расстояния между точками задается формулой (Пифагора):

Рис. 16А.

Пример 3.А

Воспользовавшись таким способом параметрического представления прямой, начертим орнамент, показанный на рис. 16А. На первый взгляд орнамент кажется сложным, но, если присмотреться повнимательнее, видно, что он состоит из последовательности вложенных друг в друга квадратов. Стороны квадратов монотонно убывают, и каждый из квадратов повернут относительно своего предшественника на фиксированный угол. Для того, чтобы нарисовать этот орнамент, нам нужно научиться вписывать в квадрат другой квадрат, повернутый на фиксированный угол. Предположим, что четыре вершины квадрата - это отрезок, соединяющий точку (X(I), Y(D) (11,2,3,4); 1-ая сторона квадрата - это отрезок, соединяющий точку (X (I), Y(I) с точкой (X(I+1), Y(I+1), где сложение производится по модулю 4. Координаты (X''(I), Y''(I) произвольной точки, лежащей на этой стороне, есть

((1-MU)*X(I)+MU*X(I+1),(1-MU)*Y(I)+MU*Y(I+1)),

где 0<=MU<=1

Эта точка делит сторону в отношении MU:(1-MU). Если MU фиксировано и четыре точки (X''(I), Y''(I)

(I=1,......4) вычисляются по приведенной формуле, то стороны нового квадрата образуют угол ALFA=ARCTG(MU/(1-

MU)) со сторонами старого квадрата. Таким образом, если MU остается одним и тем же для всех квадратов, то мы получим необходимую последовательность. Программа, приведенная на листинге 3.1, рисует орнамент, состоящий из 21 -го квадрата с М^=0.1. LISTING 3.1

100 REM SQUARE OUTSIDE SQUARE ETC.

110 LET START=9700: LET SETORIGIN=9600: LET MOVETO=9500: LET LINETO=9400 120 LET HORIZ=3: LET VERT=2.1 130 GO SUB START

140 LET XMOVE=HORIZ*0.5: LET YMOVE=VERT*0.5 150 GO SUB SETORIGIN

160 DIM X(4):DIM Y(4): DIM V(4):DIM W(4) 170 DATA 1,1,1,-1,-1,-1,-1,1

179 REM INITIALISE FIRST SQUARE.

180 FOR I=1 TO 4: READ X(I),Y(I): NEXT I

189 REM SET MU VALUE AND DRAW 20 SQUARES.

190 LET MU=0.1: LET UM=1-MU 200 FOR I=1 TO 21

208 REM JOIN FOIR VERTICES OF SQUARE (X(J),Y(J)).

209 REM CALCULATE NEXT FOIR VERTICES(V(J),W(J)).

210 LET XPT=X(4): LET YPT=Y(4): GO SUB MOVETO 220 FOR J=1 TO 4

230 LET XPT=X(J): LET YPT=Y(J): GO SUB LINETO

240 LET NJ=J+1: IF NJ=5THEN LET NJ=1

250 LET V(J)=UM*X(J)+MU*X(NJ)

260 LET W(J)=UM*Y(J)+MU*Y(NJ)

270 NEXT J

279 REM COPY ARRAYS V AND W INTO X AND Y.

280 FOR J=1 TO 4

290 LET X(J)=V(J): LET Y(J)=W(J) 300 NEXT J 310 NEXT I 320 STOP

Иногда оказывается полезной следующая параметрическая форма прямой:

P(1)+MU*(P(2)-P(1))

Здесь Р(1) называется базовым вектором, а (Р(2)-Р(1)) - направляющим вектором. Любая точка прямой может выступать в роли базового вектора; она просто выделяет из семейства прямых, параллельных направляющему вектору, прямую, проходящую через эту точку. Следует дополнительно обсудить возможность использования вектора для указания направления. Мы знаем, что вектор (X,Y) может использоваться для обозначения точек на плоскости. Тогда прямая, проходящая через начало координат и эту точку, определяет направление - по определению, любая прямая, параллельная этой прямой, имеет тот же направляющий вектор. Отметим, что положительным направлением на прямой считается направление от начала координат к точке (X,Y). Двойственное представление вектора как точки

и как направления находит применение в следующем примере. Пример 3.Б

Нарисуйте линию, состоящую из 13 штрихов и проходящую через точки P(1)=(X(1),Y(1)) и P(2)=(X(2),Y(2)). Эта задача решается при помощи 26 точек, равноудаленных друг от друга; точка этого семейства задается выражением Р(1)+(!/25)*(Р(2)-Р(1)), где I принимает значения от 0 (точка Р(1)) до 25 (точка Р(2)). Используя подпрограмму "PLOT" (листинг 2.8), мы попеременно то движемся по прямой, то вычерчиваем участок этой прямой. Хранить значения координат необязательно; Р(1) нам задано, и, прибавляя каждый раз по 1/25*(Р(2)-Р(1)), мы побываем во всех необходимых точках (см. листинг 3.2).

LISTING 3.2

100 REM DASHED LINES 110 LET START=9700: LET PLOT=9800 120 LET HORIZ=30: LET VERT=20 130 GO SUB START

140 LET XPT=HORIZ*0.5: LET YPT=VERT*0.5: LET MOVE=3

150 GO SUB PLOT

160 INPUT " X1=";X1;" Y1=";Y1

170 INPUT " X2=";X2;" Y2=";Y2

179 REM MOVE TO FIRST POINT.

180 LET XPT=X1:LET YPT=Y1: LET MOVE=3: GO SUB PLOT 190 LET XD=(X2-X1)/25: LET YD=(Y2-Y1)/25

199 REM Alternately draw and move to next 25 points on the line.

200 FOR I=1 TO 25

210 LET XPT=XPT+XD: LET YPT=YPT+YD: LET MOVE=5-MOVE: GO SUB PLOT 220 NEXT I 230 STOP Упражнение 3.1

Поэкспериментируйте с различными видами пунктирных линий:

A. Длина штриха в два ряда превосходит длину промежутка между кривыми. Б. Длина штриха фиксирована, а количество штрихов неизвестно.

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

Данная параметрическая форма прямой удобна для вычисления точки пересечения двух прямых - задачи, часто встречающейся в двумерной графике. Предположим, что заданы две прямые

P+MU*Q и R+LMD*S где P=(X(l),Y(l)), Q=(X(2),Y(2)), R=(X(3),Y(3)), S=(X(4),Y(4)),

Минус Бесконечность < MU, S < Плюс Бесконечность Мы должны найти такие значения MU и LMD, что

P + MU*Q-R + LMD*S то есть точку, лежащую на обеих прямых. Это векторное уравнение распадается на два скалярных:

Х(1)+MU*X(2)=Х(3)+LMD*Х(4) (3.1) Y(1)+MU*Y(2)=Y(3)+LMD*Y(4) (3.2)

Перепишем эти уравнения так:

MU*X(2)-LMD*Х(4)=Х(3)-Х(1) (3.3) MU*Y(2)-LMD*Y(4)=Y(3)-Y(1) (3.4)

Умножим (3.3) на Y(4), а (3.4) на Х(4) и, вычитая, получим:

MU*(X(2)*Y(4)-Y(2)*X(4)) = (X(3)-X(1))*Y(4)-(Y(3)-Y(1))*X(4) Если (X(2)*Y(4)-Y(2)*X(4))=0, тогда эти прямые параллельны, и точки пересечения не существует (MU не существует), в противном случае

_MU = (X (3) - X (1)) * Y (4) - (Y (3) - Y (1)) * X (4) X (2)* Y (4) - Y (2)* X (4)

и аналогично

_LMD = (X (3) - X (1)) * Y (3) - (Y (3) - Y (1)) * X (3) X (2)* Y (4) - Y (2)* X (4) Это решение упрощается, если одна из прямых параллельна координатной оси. Предположим, что X=D, тогда R=(D,0) и S=(0,l),

MU=(D-X(1))/X(2)

Аналогично для прямой Y=D, получим:

MU=(D-Y(1))/Y(2)

Если прямые параллельны, то детерминант уравнения обращается в бесконечность, так как параллельные прямые не пересекаются.

Пример 3.В

Найдите точку пересечения двух прямых:

A. Соединяет (1,-1) и (-1.-3);

B. Соединяет (1,2) и (2,2).

Эти прямые задаются выражениями

(1-MU)*(1,-1) + MU*(-1,3) -Бесконечность<Ми<+Бесконечность (3.7) (1-(LMD))*(1,2) + LMD*(2,-2) -Бесконечность<ЬМБ<+Бесконечность (3.8)

или, переходя к форме базовая точка - направление:

(1,-1)+MU*(-2,-2) (3.9) (1,2)+LMD*(2,-4) (3.10)

Подставляя эти значения в уравнение (3.5), получим:

_MU _ (1 -1)(4) - (2 +1)2 1 (-2(-4) - (-2)2) 2 откуда значения координат точки пересечения (1,-1) - 1/2* (-2,2) = (2,0).

Упражнение 3.2

Поэкспериментируйте с такой формой представления двумерной геометрии. Вы можете составить свои собственные задачи. Легко проверить правильность решения этих задач. Рассмотрим пример 3.Б. Мы знаем, что точка (2,0) лежит на первой прямой, так как мы использовали MU=-1/2; наше решение верно, если она также лежит и на второй прямой; нетрудно убедиться, что это так - значение LMD=1/2;

Упражнение 3.3

Напишите программу, которая считывает информацию о двух прямых; они могут быть заданы в форме уравнений или в форме базовая точка-направление и вычисляет точку их пересечения (если таковая имеется).

Кадрирование

Нам известно, что для точек (X,Y), расположенных вне экрана, команды PLOT и DRAW недействительны, так что мы ограничены значениями координат 0<=Х<=255 и 0<=Y<=175. Двумерные и трехмерные построения удобно проводить на больших областях, чем область экрана, но тогда нам необходимо найти алгоритм, удаляющий всю лишнюю информацию без потери полезной информации.

1Х=-1	|Х=%| r=J"	А*	1Х=+1 IY=+1
J Н --	с о G "1—--*	Е1	IY=0
	F	в! lv=-1

Рис. 17.

Предположим, что центр экрана задается точкой (не пикселем!) с действительными координатами (255/2, 175/2) = (127.5, 87.5) и, следовательно, угловые точки экрана имеют координаты (127.5±127.5, 87.5±87.5). Наша задача сводится к нахождению отрезка прямой, соединяющего пиксели (XA,YA) и (XB,YB) и лежащего в поле экрана. Для простоты предположим, что начало координат совпадает с центром экрана, что достигается вычитанием вектора (127.5,87.5) из векторов, соответствующих точкам в старой системе координат. Теперь координаты угловых точек экрана равны (±127.5,±87.5). Мы продолжаем стороны прямоугольника, разбивая таким образом плоскость на девять участков; см. рис. 17, на котором видны графическое поле и его граница. Для иллюстрации работы алгоритма на рисунке изображены несколько сегментов. Каждая точка пространства может быть теперь охарактеризована двумя параметрами, IX и IY, где

(1) IX=-1,0,+1 в зависимости от того, будет ли значение Х-координаты точки лежать справа, в, или левее графической области;

(2) IY=-1,0,+1 в зависимости от того, будет ли значение Y-координаты точки лежать ниже графической области, в графической области или выше её.

Эти значения при необходимости вычисляются внутри программы.

Пусть концам сегмента с координатами (XA,YA), (XB,YB) соответствуют значения параметров IXA и IYA и IXB и IYB соответственно, тогда имеются следующие возможности:

(I) если IXA=IXB не=0 и IYA=IYB не=0, тогда весь сегмент лежит вне экрана и его можно не рассматривать; см. сегмент АВ на рис. 17.

(II) если IXA=IYA=IXB=IYB=0, тогда весь сегмент лежит в графическом поле и его следует изобразить целиком; см. сегмент CD.

(III) оставшиеся случаи следует рассмотреть подробнее. Если IXA не=0 и (или) IYA не=0, тогда точка (XA,YA) лежит вне прямоугольника и поэтому следует вычислить новые значения ХА и YA - чтобы избежать недоразумений, мы обозначим их XA',YA'. (XA',YA') - ближняя к (XA,YA) точка пересечения прямой с границей графической области. Формула для вычисления координат точки пересечения рассматривалась выше: это формула для нахождения точки пересечения прямой с другой прямой, параллельной координатной оси. Если прямая не пересекает прямоугольник, то принимаем за точку (XA',YA') точку пересечения прямой с одной из продолженных вертикальных прямых. Если IXA=IYA=0, то (XA',YA')=(XA,YA). Точка (XB',YB') вычисляется аналогично; см. алгоритм подпрограммы CLIP на листинге 3.3. Требуемый отрезок - это отрезок, соединяющий точки (XA',YA') с точкой (XB',YB'). Если прямая не пересекает прямоугольник, то (XA',YA')=(XB',YB'), и новый отрезок вырождается в точку.

Например, EF обрезается до E'F'. GH обрезается до GH' (G=G'), и IJ сводится к точке I'=J'.

Программа "CLIP" переводит координаты концов отрезка (XA,YA) и (XB,YB) в координаты центрированной системы координат. Затем проверяется, какая из трех ситуаций имеет место, и в случае (I) программа тут же прекращает работу, в случае (II) соединяет две точки, а в случае (III) - вычисляет "штрихованные" координаты.

Листинг 3.3 содержит новую версию подпрограммы "LINETO", вызывающей "CLIP" вместо PLOT и DRAW, так что теперь мы можем соединять любые точки. Начиная с этого момента, используйте эту версию "LINETO". Она окажется неоценимым подспорьем, особенно при исследовании трехмерных объектов.

Упражнение 3.4

Используйте эту модифицированную программу в программах главы 2. Выбирайте значения HORIZ и VERT таким образом, чтобы некоторые участки кривых выходили за пределы графического поля.

LISTING 3.3

8400 REM CLIP

8401 REM IN - XA,YA,XB,YB

8409 REM CHANGE COORDINATE SYSTEM.

8410 LET XA=XA-127.5: LET YA=YA-87.5: LET XB=XB-127.5:

8419 REM Fire the sector values of two points (XA,YA)

IF ABS XA>127.5 THEN LET IXA=SGN XA IF ABS YA>87.5 THEN LET IYA=SGN YA IF ABS XB>127.5 THEN LET IXB=SGN XB IF ABS YB>87.5 THEN LET IYB=SGN YB

8459 REM POINTS IN SAME OFF-SCREEN SECTOR THEN RETURN.

8460 IF IXA*IXB=1 OR IYA*IYB=1 THEN RETURN 8470 IF IXA=0 THEN GO TO 8500

8479 REM MOVE 1"ST POINT TO NEARER X-EDGE.

8480 LET XX=127.5*IXA: LET YA=YA+(YB-YA)*(XX-XA)/(XB-XA): LET XA=XX 8490 LET IYA=0: IF ABS YA> 87.5 THEN LET IYA=SGN YA

8500 IF IYA=0 THEN GO TO 8520

8509 REM MOVE 1"ST POINT TO NEARER Y-EDGE.

8510 LET YY=87.5*IYA: LET XA=XA+(XB-XA)*(YY-YA)/(YB-YA): LET YA=YY 8520 IF IXB=0 THEN GO TO 8550

8529 REM MOVE 2"ND POINT TO NEARER X-EDGE.

8530 LET XX=127.5*IXB: LET YB=YB+(YB-YA)*(XX-XB)/(XB-XA): LET XB=XX 8540 LET IYB=0: IF ABS YB>87.5 THEN LET IYB=SGN YB

8550 IF IYB=0 THEN GO TO 8570

8559 REM MOVE 2"ND POINT TO NEARER Y-EDGE.

8560 LET YY=87.5*IYB: LET XB=XB+(XB-XA)*(YY-YB)/(YB-YA): LET YB=YY 8570 IF ABS (XA-XB)<0.000001 AND ABS (YA-YB)<0.000001 THEN RETURN

8579 REM PLOT NOT-COINCIDENT POINTS.

8580 LET XA=INT (XA+128): LET YA=INT (YA+88): LET XB=INT (XB+128): (YB+88)

8590 PLOT XA,YA: DRAW XB-XA,YB-YA: RETURN

9400 REM LINETO/CLIPPING

9401 REM IN - XPT,YPT,XPEN,YPEN

9402 REM OUT - XPEN,YPEN 9410 LET CLIP=8400

9420 LET XA=XPEN: LET YA=YPEN

9430 LET XPEN=FN X(XPT): LET YPEN=FN Y(YPT)

9440 LET XB=XPEN: LET YB=YPEN

9450 GO SUB CLIP

9460 RETURN

Y

|Q|xSin(<aO

|Q|xCos(oC)

Рис. 18.

Возвращаясь к использованию направляющего вектора Q=(X,Y) не= (0,0) для определения направления, заметим, что вектор KQ, где К>0, определяет то же направление и ориентацию, что и Q (если К отрицательно, то ориентация направления противоположная). Если мы возьмем К=1/ABS(Q), то получим вектор (X/SQRT(X**2+Y**2), Y/SQRT(X**2+Y**2)) единичной длины.

Расстояние точки прямой P+MU*Q до базового вектора Р есть ABS(MU*Q), и если ABS(Q)=1, то это расстояние равно ABS(MU).

Предположим, что ALFA - угол между прямой, соединяющей 0 (начало координат) с точкой Q=(X,Y) и положительной полуосью X. Тогда X=ABS(Q)*COS(ALFA), Y-ABS(Q)*SIN(ALFA), см. рис. 18; для других квадрантов картина аналогичная.

Если Q - вектор единичной длины, то Q=(COS(ALFA).SIN(ALFA)). Заметим, что SIN(ALFA)=COS(PI/2-ALFA) для всех значений ALFA. Поэтому мы можем записать Q=(COS(ALFA),COS(PI/2-ALFA)), но PI/2 - ALFA это угол между векторами и положительной полуосью Y, что дает основание называть координаты единичного вектора направляющими косинусами.

Перед тем, как продолжить, мы рассмотрим имеющиеся в бейсике тригонометрические функции: SIN и COS и обратную тригонометрическую функцию ATAN. SIN и COS - однопараметрические (угол, выраженный в радианах) и однозначные функции с областью значений между -1 до +1.

Функция ATAN имеет областью определения всю числовую ось, и вычисляет угол в радианах (так называемую главную ветвь с диапазоном значений от -PI/2 до PI/2), тангенс которого совпадает со значением аргумента.

Программа "ANGLE" вычисляет угол, который образует направление Q=(X,Y) с положительной полуосью X. Эта подпрограмма приведена на листинге 3.4 и окажет нам большую помощь в последующих главах, посвященных трехмерной геометрии.

LISTING 3.4

8800 REM ANGLE

8801 REM IN - AX.AY

8802 REM OUT- THETA

8809 REM THETA IS THE ANGLE MADE BY LINE TO (AX,AY) WITH+VE X-AXIS.

8810 IF ABS AX>0.00001 THEN GO TO 8860

8819 REM LINE IS VERTICAL.

8820 LET THETA=PI /2

8830 IF AY<0 THEN LET THETA=THETA+PI

8840 IF ABS AY<0.00001 THEN LET THETA=0

8850 RETURN

8859 REM LINE NOT VERTICAL SO IT HAS FINITE TANGENT.

8860 LET THETA=ATN (AY/AX)

8870 IF AX<0 THEN LET THETA=THETA+PI

8880 RETURN

Рис. 19

Предположим, что нам заданы два вектора (А,В) и (C,D); ограничимся для простоты случаем векторов единичной длины (см. рис. 19). Мы хотим вычислить острый угол ALFA между этими векторами. Из рисунка видно, что

OA=SQRT(A**2+B**2)=1, OB=SQRT(C**2+D**2)=1.

По теореме косинусов имеем:

AB**2=OA**2+OB**2-2*OA*OB*COS(ALFA)=2*(1-COS(ALFA))

Но по теореме Пифагора:

AB**2=(A-C)**2+(B-D)**2=(A**2+B**2)+(C**2+D**2)-2(A*C+B*D)=2-2(A*C+B*D).

Таким образом

COS(ALFA)=A*C+B*D.

Если A*C+B*D отрицательно, то ARCCOS(A*C+B*D) - тупой угол, и требуемый острый угол равен PI-ALFA. Так как COS(PI-ALFA)=-COS(ALFA), то мы приходим к выводу, что острый угол вычисляется по формуле

ARCCOS(ABS(A*C+B*D)) Рассмотрим, например, две прямые с направляющими косинусами

(SQRT(3)/2,1/2) и (-1/2,-SQRT(3/2); мы видим, что A*C+B*D=-3/2 и, следовательно,

ALFA=ARCCOS(SQRT(3)/2)=PI/6. Этот простой пример приводится для того, чтобы ввести понятие скалярного произведения двух векторов (A,B)*(C,D)=A*C+B*D. Понятие скалярного произведения распространяется на случай пространств больших измерений, так что и в этих случаях оно помогает ввести понятие угла между прямыми.

Задание кривых с помощью функциональной зависимости Кривая в двумерном пространстве задает зависимость между значениями X координаты и Y координаты, которая называется функциональной зависимостью. С другой стороны, значения координат точек вдоль кривой можно задавать с помощью параметра.

Мы знаем, что прямую (которая является окружностью бесконечно большого радиуса) можно задавать с помощью AY=BX+C. Если перенести правую часть в левую, то мы придем к уравнению (A*Y-B*X-C=0), правая часть которого:

F(X,Y)=A*X-B*Y-C

называется функциональной формулой прямой. Точка принадлежит прямой тогда и только тогда, когда F(X,Y)=0. Таким образом, вся плоскость оказывается разделенной на три области:

• область, в которой F(X,Y)>0 (область положительных значений),

• область, в которой F(X,Y)<0,

• собственно прямая F(X,Y)=0.

Если кривая делит плоскость на две связанные компоненты (область называется связанной, если любые две точки, принадлежащие области, можно соединить кривой, не пересекающей кривую F(X,Y)=0), тогда каждую из этих компонент можно отождествить с областью положительных значений.

Следует помнить, что некоторые, даже вполне элементарные, кривые делят область не на две, а на бесконечное число компонент (например, F(X,Y)=COS(Y)-SIN(X)), что не исключает возможности обеим несвязанным компонентам принадлежать к типу областей положительных значений.

Обратите внимание, что функциональное представление не единственно. Ту же прямую задает функция

F(X,Y)=B*X+C-A*Y.

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

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

F(X,Y)=A*Y-B*X-C,

где точка (X1,Y1) лежит по ту же сторону от прямой, если и только если знаки F(X1,Y1) и F(X2,Y2) совпадают.

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

Направляющий вектор прямой равен (А,В). Направляющий вектор (-В,А). Почему? Произведение тангенсов взаимно перпендикулярных прямых равно -1 . Мы видим, что ближайшая к точке Р точка Q задается:

Q=(X(1),Y(1))+MU*(-B,A), что означает, что прямая, проходящая через Р и Q, перпендикулярна исходной прямой. Так как Q лежит на исходной прямой, то

F(Q)-F(X(1),Y(1)H/IU*(-B,A)-0

и следовательно

A*(Y(1)+MU*A)-B*(X(1)-MU*B)-C=F(X(1),Y(1))+MU*(A**2+B**2)=0

откуда

MU=F(X(1),Y(1))/(A**2+B**2).

Точка Q лежит на расстоянии MU*ABS(-B,A) от точки (X(1),Y(1)); это означает, что расстояние от (X(1),Y(1)) до прямой есть

MU*SQRT(A**2+B**2)=-F(X(1),Y(1))/SQRT(A**2+B**2)

Знак указывает, по какую сторону от прямой лежит точка. Если А**2+В**2=1, то ABS(F(X1,Y1)) задает расстояние от точки (X1,Y1) до прямой.

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

Рассмотрим выпуклый N-угольник; предположим что нам задано множество его вершин в том порядке, в каком они встречаются при обходе многоугольника по (против) часовой стрелки. В дальнейшем мы будем называть такой набор вершин упорядоченным. Задачу выяснения того, является ли набор упорядоченным по часовой стрелке или против, мы отложим до главы 7. N сторон многоугольника являются отрезками прямых

F(I)(X,Y) = (X(I+1)-X(I))*(Y-Y(I))-(Y(I+1)-Y(I))*(X-X(I)), где I=l,...,N, и сложение производится по модулю N (что означает N+J=J для I<=J<=N). Попробуйте объяснить, почему эти формулы описывают отрезки. Последовательное рассмотрение этих отрезков позволит нам определить внутренность этой выпуклой области. Каждый из этих сегментов, например, соединяющий точки Р® и Р(!+1) для некоторого I, обладает тем свойством, что точки внутри области должны лежать с той же стороны от прямой, на которой лежит отрезок и остальные вершины многоугольника, например, вершина Р(!+2). Таким образом, не трудно вывести формулы для точки, лежащей вне области, на границе области и внутри области.

А теперь перейдем к примеру.

1 2

Рис. 20

Пример 3.Г

Предположим, что задан выпуклый многоугольник с вершинами (1,0), (5,2), (4,4) и (-2,1) (см. рис. 20). Очевидно, что точки обходились против часовой стрелки. Находятся ли точки (3,2), (1,4), (3,1) внутри многоугольника, вне многоугольника или лежат на границе? Каково расстояние от точки (4,4) до первой прямой? F(1)(X,Y) = (5-1)*(Y-0)-(2-0)*(X-1) = 4*Y-2*X+2

F (2) (X, Y) = (4-5) * (Y-2) - (4-2) * (X-5) = -Y-2*X+12

F(3) (X,Y) = (-2-4) *(Y-4)-(l-4)*(X-4) = -6*Y+3*X+12

F(4) (X,Y) = (1+2)*(Y-1)-(0-l)* (X+2) = 3*Y+X-1

Мы видим, что точка (3,2) лежит внутри многоугольника, так как F(l)(3,2)=4 и F(l)(4,4)=10; F(2)(3,2)=4 и F(2)(2,1)=15; F(3)(3,2)=9 и F(3)(1,0)=15; F(4)(3,2)=8 и F(4)(5,2)=10 - все точки имеют одинаковый положительный знак. Точка (1,4) лежит вне области, так как F(3)(1,4)=-9 и F(3)(1,0)=15 - знаки противоположны. Точка (3,1) лежит на границе, так как F(1)(3,1)=0, F(2)(3,l)=5, F(3)(3,l)=15, F(4)(3,4)=5.

На самом деле нет необходимости вычислять F(I)(X(I+2,Y(I+2)) для каждого значения I, они все имеют тот же знак, так что вычислив F(1)(X(3),Y(3)), мы можем использовать это значение в наших вычислениях. (4,4) находится на расстоянии

F(1)(4,4)/SQRT(4**2+2**2)=10/SQRT(20)=SQRT(5)

Упражнение 3.5

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

Теперь рассмотрим параметрическое представление кривой. Еще раз отметим, что в случае параметрического задания кривой координаты точки, принадлежащие прямой, определяются с помощью параметра с учетом области допустимых значений этого параметра. Мы уже знаем параметрический вид прямой: это просто задание прямой с помощью базовой точки и направляющего вектора:

B+MU*Q=(X(1),Y(1)+MU*(X(2),Y(2))=(X(1)+MU*X(2),Y(1)+MU*Y(2)), где -Бесконечность<MU<+Бесконечность.

MU - параметр, X(1)+MU*X(2) и Y(1)+MU*Y(2) - соответственно Х- и Y-координаты, которые зависят только от значений MU.

Мы приведем также функциональный и параметрический виды простейших кривых. Например, кривая синуса задается в функциональной форме

F(X,Y)=Y-SIN(X)

и в параметрической

(X,SIN(X))

где -бесконечность<Х<+бесконечность.

Общий вид конического сечения (эллипс, парабола, гипербола) задается функцией

F(X,Y)=A*X**2+B*Y**2+H*X*Y+F*X+G*Y+C. где коэффициенты А, В, Н, F, G, С однозначно определяют кривую. Окружность радиуса R с центром в начале координат имеет значение параметров А=В=1, F=G=H=0 и С=Я**2, F(X,Y)>0. В параметрической форме координаты окружности имеют вид:

(R*COS(ALFA),R*SIN(ALFA)),

где 0<=ALFA<=2*PI (мы уже встречались с параметрической формой эллипса, окружности и спирали в главе 2).

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

Пример 3.Д

Предположим, что мы хотим нарисовать шар (радиуса R), исчезающий в эллипсной дыре (большая ось-А, малая ось-В). Некоторые участки окружности и эллипса скрыты от наблюдателя.

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

F(X,Y)=X**2/A**2+Y**2/B**2-1

и параметрический вид:

(A*COS(ALFA),B*SIN(ALFA)),

где 0<=ALPHA<=2*PI.

Для окружности:

F(X,Y)=X**2+(Y-D)**2-R**2

и параметрическая форма:

(R*COS(LMDA)*D+R*SIN(LMDA)),

где 0<=LMDA<=2*PI.

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

(X,Y)=(A*COS(ALFA),B*SIN(ALFA)), удовлетворяющие F(C)(X,Y)=0, что означает:

A**2(COS(ALFA))**2+(B*SIN(ALFA)-D)**2-R**2=0 A**2*COS(ALPHA)**2+B**2*SIN(ALPHA)**2-2*B*D*SIN(ALPHA)+D**2-R**2=0; и так как (COS(ALFA))**2=1-(SIN(ALFA))**2, то:

(B**2-A**2)*(SIN(ALFA))**2-2*B*D*SIN(ALFA)+A**2+D**2-R**2=0 Это простое квадратное уравнение легко разрешить относительно SIN(ALFA) (квадратное уравнение А*Х**2+В*Х+С=0 имеет корни (-B+-SQRT(B-4*A*C)/2*A)). Для каждого значения SIN(ALFA) мы можем вычислить точки значения ALFA, 0<=ALFA<=2*PI (если таковые существуют) и затем вычислить точки пересечения (A*COS(ALFA),B*SIN(ALFA)).

Не существует жестких правил о том, каким представлением лучше пользоваться в том или ином случае; это надо чувствовать, и это достигается только практикой.

Список программ

1. LIB1 и листинг 3.1.: входные данные отсутствуют.

2. Листинги 2.1, 2.8 и 3.2: входные данные - две координатные пары (X(1),Y(1)) и (X(2),Y(2)) Замечание: с этого момента листинг 3.3 ("CLIP) и новая версия "LINETO" заменят листинг 2.5 в "LIB1A".

1. Предисловие - данная книга является введением в предмет компьютерной графики, может рассматриваться как дешевый пакет программ.
2. Введение - Эту книгу можно можно рассматривать как книгу рецептов графических программ, позволяющих рисовать сложные картинки с помощью SPECTRUMa.
3. Графические команды ZX SPECTRUM - Команды PAPER и INK; Дисплейный файл; Команда BORDER; Символьные блоки; Команды PLOT и DRAW; Команды PRINT и LIST; Команды INVERSE и OVER; Команды FLASH и BRIGHT; Атрибуты; Простейшее движущееся изображение; Команды CIRCLE и DRAW; Цвета в символьном блоке; Простая игра.
4. От реальных координат к пикселям - Примитивы, обеспечивающие карту пространства на графическом экране; Список программ;
5. Геометрия декартовой плоскости - Кадрирование; Задание кривых с помощью функциональной зависимости; Список программ.
6. Матричное представление преобразований двумерного пространства - Композиция преобразований; Перенос; Растяжение; Вращение относительно начала координат; Обратное преобразование; Размещение объекта; Рассматривание объекта; Вычерчивание объекта; Сложные изображения - метод построения изображения "по кирпичикам"; Эффективное использование матриц; Хранение информации об изображении; Список программ.
7. Символьная графика ZX SPECTRUM - Стандартный набор символов; Графический режим работы; Блочная графика; Графика, определяемая пользователем; Альтернативные множества символов; Список программ.
8. Диаграммы и графики - Курсоры; Атрибуты; Точки и линии; Запись и загрузка; Надписи; Данные для графиков; Специальные символы; Определенные пользователем символы для использования в гистограммах; Гистограммы; Круговые диаграммы; Штриховка секторов; Графики; Список программ.
9. Трёхмерная декартова геометрия - Определение прямой; Угол между двумя направляющими векторами; Определение плоскости70 Точка пересечения прямой и плоскости; Расстояние от точки до прямой; Точка пересечения двух прямых; Плоскость, проходящая через три неколлинеарные точки; Точка пересечения трёх плоскостей; Линия пересечения двух плоскостей; Функциональное представление поверхности; Лежит ли точка по ту же сторону от плоскости, что и начало координат?; Каково направление обхода двумерного многоугольника, заданного последовательностью своих вершин?
10. Матричное представление преобразования трехмерного пространства - Параллельный перенос; Растяжение; Вращение относительно координатной оси; Вращение на угол ТЕТА относительно оси X; Обратное преобразование; Поворот на угол NU относительно произвольной оси.
11. Ортогональные проекции - Исходное положение; Фактическое положение; Наблюдаемое положение; Ортогональная проекция; Вычисление матрицы Q, переводящей объект из фактического положения в наблюдаемое; Как задавать объект; Конструирующие подпрограммы и метод построения блоков; Тела вращения.
12. Простые алгоритмы удаления невидимых линий и поверхностей - Ориентация треугольника в трехмерном пространстве; Алгоритм удаления скрытых поверхностей для случая тела, ограниченного замкнутой и выпуклой поверхностью; Тела вращения; Вычерчивание поверхности специального вида, лежащей в трехмерном пространстве.
13. Перспективная проекция - Что такое перспективное видение? Построение перспективной проекции точки; Свойства перспективной проекции; Выбор визуальной плоскости; Кадрирование изображения; Список программ.
14. Общий алгоритм удаления невидимых линий - алгоритм для перспективного отображения трехмерного обьекта, хранящегося в памяти.
15. Белее сложные элементы программирования - Управление выполнением программ; Структура дисплейного файла; Быстрое преобразование содержимого экрана; Мультипликация; Свертка; Структура программ на бейсике (перенумерация и уничтожение); Структура программы на бейсике (эффективные программы); Синхронное изображение.
16. Действующий пример видеоигры - Описание игры; Передний план; Фон; Каскадная мультипликация; Другие методы мультипликации.
17. Проекты - ПРИЛОЖЕНИЕ А.

  Оставте Ваш отзыв:

  НИК/ИМЯ

  ПОЧТА (шифруется)

  КОД