ГЛАВА 7
Трёхмерная декартова геометрия
Перед тем, как изучать методы трехмерной графики, нам необходимо ознакомиться с методами декартовой трехмерной геометрии. Так же, как и в двумерном варианте, мы начинаем с того, что выбираем в пространстве точку, которую считаем началом координат, и проводим через неё три взаимно перпендикулярные прямые, которые мы называем осью X, осью Y и осью Z. На этих осях следует указать положительное и отрицательное направления, так что расстояние от точки, расположенной по положительную сторону от начала координат, положительно, а отрицательную - отрицательно.
Для осей X и Y положительное направление можно указать так же, как и в двумерном случае - предположим, что плоскость, в которой лежат эти оси, совпадает с плоскостью страницы, ось X горизонтальна, ось Y - вертикальна, тогда положительное направление на оси X - вправо от начала координат, а положительное направление по оси Y -вверх от начала координат. Для оси Z остается только две возможности: она должна идти перпендикулярно плоскости листа (это равносильно перпендикулярности обеим координатным осям), и может быть направлена положительной полуосью в страницу, или положительной полуосью из страницы.
Первый случай соответствует так называемой правосторонней координатной системе, а второй -левосторонней. Всюду в этой книге мы будем пользоваться только левосторонней системой координат. Все, что относится к левосторонним координатам, относится и к правосторонним системам, так что неважно, какие из них использовать, важно только придерживаться какой-то одной системы.
С помощью координатной системы мы отождествляем точки P пространства с тройками действительных чисел (X,Y,Z), где эти числа называются координатными точками и являются расстояниями от проекции точки на координатную ось до начала координат. Проекцией точки на координатную ось называется точка, которая однозначно определяется тем, что прямая, соединяющая проекцию точки и точку перпендикулярна этой оси.
Над трёхмерными векторами можно производить две операции:
• Умножить на число - К*(Х^) = (К*Х,К*^Е^);
• Складывать - сумма векторов P1 = (X1,Y1,Z1) и Р2 = (X2,Y2,Z2) есть вектор (Х1+Х2Д^2^^2), то есть
при сложении векторов соответствующие координаты складываются.
Определение прямой
Теперь мы определим прямую, проходящую через две заданные точки (X1,Y1,Z1), (X2,Y2,Z2), что можно сделать, задав уравнение этой прямой:
(X-X1)*(Y2-Y1)=(Y-Y1)*(X2-X1) (Y-Y1)*(Z2-Z1)=(Z-Z1)*(Y2-Y1) (Z-Z1)*(X2-X1)=(X-X1)*(Z2-Z1)
Хотя здесь приведены три уравнения, их решение определяет прямую, а не единственную точку, что связано с тем, что эти уравнения линейно зависимы так, что, задавая одну из координат, можно однозначно получить значение двух других (см. пример 7.А).
Также, как и в случае двух измерений, это не единственный способ задавать прямую. Существует ещё параметрический способ задания прямой, проходящей через точки Р1 и Р2:
P(MU) = (1-MU)*P1+MU*P2, или P(MU) = (1-MU)*X1+MU*X2,(1-MU)*Y1+MU*Y2,(1-MU)*Z1+MU*Z2, где MU - действительный параметр.
Параметрический вид прямой в точности совпадает с двумерным случаем. Символ MU в скобках указывает на то, что точка на прямой параметрически зависит от MU. Начиная с этого момента, будем опускать MU. Обратите внимание, что MU=1 дает точку Р2, а MU=0 - точку Р1.
Мы можем записать параметрическое уравнение прямой в таком виде:
P(MU)=P1+MU*(P2-P1)
Так же, как и в двумерном варианте, вектор P1 называется базовым вектором, а вектор (Р2-Р1) -направляющим вектором. Мы, опять-таки, имеем двойственность в представлении векторов: с одной стороны, вектор можно отождествлять с точкой, проекции которой на координатные оси равны координатам вектора, а с другой стороны - вектор задает направление, совпадающее с направлением прямой, проведенной из начала координат в эту точку. При этом направление на прямой от начала координат к точке считается положительным, а обратное направление - отрицательным. Таким образом, вектора (X,Y,Z) и (-X,-Y,-Z) определяют одну и ту же прямую в пространстве, но с разной ориентацией.
Определим норму вектора (которую также называют модулем вектора, его длиной), обозначаемую ABS(D), как расстояние от точки, определяемой вектором, до начала координат
ABS(D)=SQRT(X**2+Y**2+Z**2)
Точку P+MU*D на прямой можно определить следующим образом: найти точку P и сдвинуть по прямой на расстояние MU*ABS(D) в положительном направлении, если MU положительно, и в отрицательном направлении -если MU отрицательно; при этом мы попадаем в точку P+MU*D. Заметьте, что любая точка прямой может служить базовым вектором, и что направляющий вектор можно умножить на любое, отличное от нуля, число.
Если вектор D=(X,Y,Z) составляет с осью X,Y,Z, углы TETX, TETY и TETZ, то
X:Y:Z=COS(TETX):COS(TETY):COS(TETZ),
это означает, что
D=(LMD*COS(TETX),LMD*COS(TETY),LMD*COS(TETZ))
Из свойств трёхмерного пространства следует:
(COS(TETX))**2+(COS(TETY))**2+(COS(TETZ))**2=1
Отсюда следует, что LMD=ABS(D), и что если направляющий вектор единичной длины, то его компоненты: (COS OX, COS OY, COS OZ) и LMD=-1. Координаты единичного вектора называются направляющими косинусами. В общем случае, направляющие косинусы прямой с направляющим вектором D=(X,Y,Z) есть
( X Y Z ^
v ABS(D), ABS(D), ABS(D) ,
Пример 7.А
Используя три приведенных метода, описать прямую, соединяющую точки (1,2,3) и (-1,0,2). Произвольная точка (X,Y,Z), лежащая на прямой, удовлетворяет уравнению
(Х-1)х(0-2)=^-2)х(-1-1), (Y-2)x(2-3)=(Z-3)x(0-2), (Z-3)x(-1-1)=(X-1)x(2-3),
что эквивалентно:
-2*X+2*Y =2 -Y+2*Z =4 -2*Z+X =-5
Мы можем ограничиться рассмотрением только последних двух уравнений, так как первое уравнение получается из суммы второго и третьего уравнений, умноженных на -2
Y= 2*Z-4 и X= 2*Z-5,
так что прямая задается одним параметром, в нашем случае Z, что дает точки прямой в параметрическом виде (2*Z-5, 2*Z-4,Z). Этот результат легко проверить: значение Z=3 соответствует точке (1,2,3), а значение Z=2 соответствует точке (-1,0,2), а эти точки и определяют прямую.
В векторной форме точка прямой задается:
P(MU)=(1-MU)(1,2,3)+MU(-1,0,2)=(1-2*MU,2-2*MU,3-MU) Координаты точки и в этом случае зависят от одного параметра. Значению MU=0 отвечает точка (1,2,3), значению MU=1 - точка (-1,0,2).
Если задавать прямую с помощью базового и направляющего вектора, то
P'(MU)=(-1,0,2)+MU(-2,-2,1) Мы можем заменить координаты направляющего вектора направляющими косинусами (-2/3,-2/3,-1/2), что дает другую форму представления прямой с помощью базового и направляющего векторов:
P''(MU)=(1,2,3)+MU(-2/3,-2/3,-1/3) Естественно, что одно и тоже значение задает различные точки прямой; например, Р(3)=(-5,4,0), Р'(3)=(-7,-6,-1) и Р''(3)=(-1,0,2). Эта прямая составляет:
131.81°(ARCCOS(-2/3)), 131.81°(ARCCOS(-2/3)), 109.47°(ARCCOS(-1/3))
с осями X, Y и Z соответственно.
Угол между двумя направляющими векторами Для вычисления угла между двумя векторами введем понятие скалярного произведения двух векторов:
P*Q=(X1,Y1,Z1)(X2,Y2,Z2)=X1*X2+Y1*Y2+Z1*Z2 Если P и Q - оба вектора единичной длины (что означает, что они записаны как направляющие косинусы), а ТЕТА - угол между прямыми, то COS(ТЕТА)=P*Q (см. главу 3, где приведён двумерный аналог этой формулы). В общем случае угол между прямыми с направляющими векторами P и Q (мы предполагаем, что обе прямые проходят через начало координат):
ARCCOS((P/ABS(P))*(Q/ABS(Q)))
Очевидно, что P и Q перпендикулярны, только если P*Q=0.
Определение плоскости Перейдем к определению плоскости. Точки плоскости задаются уравнением
N*X=K,
где К - скаляр, а N - вектор, перпендикулярный плоскости (см. пример 7.Б). Если A - принадлежит плоскости, то N*A=K заменяя К в предыдущем уравнении, получим
N*X=N*A N*(X-A)=0
Последнее уравнение станет очевидным, если вспомнить, что скалярное произведение двух перпендикулярных векторов равно нулю. Для любой точки X плоскости, не совпадающей с A, Х-А можно рассматривать, как направляющий вектор прямой, лежащей в плоскости, а так как вектор N перпендикулярен плоскости, то он перпендикулярен и каждой прямой, лежащей в плоскости, а следовательно, N*(Х-А)=COS(PI/2)=0. Расписывая это уравнение по координатам, мы получим обычное уравнение плоскости:
(N1,N2,N3)*(X,Y,Z)=N1*X+N2*Y+N3*Z=K Обратите внимание, что две плоскости параллельны тогда и только тогда, когда вектора, нормальные к этим плоскостям, параллельны.
Точка пересечения прямой и плоскости Предположим, что прямая задана как A+MU*D, а плоскость N*X=K Тогда для нахождения точки пересечения прямой и плоскости нам необходимо найти такое значение MU, чтобы
N*(A+MU*D)=K, откуда MU=(K-N*A)/(N*D)
где (N*D) не =0.
Если N*D=0, то прямая параллельна плоскости, и точек пересечения нет.
Расстояние от точки до прямой Расстоянием от точки P до плоскости N*X-K называется наименьшее из расстояний от точки P до точек, лежащих на этой плоскости, откуда следует, что прямая, соединяющая точку P с точкой P2, лежащей на плоскости N, такой, что расстояние от точки P до P2 равно расстоянию от точки Р до плоскости, перпендикулярна этой плоскости. Эта прямая может быть записана в виде P+MU*N; MU определяется точкой P2:
MU=(K-N*P)/(N*N)
откуда расстояние от точки до плоскости:
MU*ABS(N)=ABS(K-N*P)/ABS(N)
В частности, если P - начало координат, то расстояние от плоскости до начала координат есть ABS(K)/ABS(N). Более того, если N - единичный вектор, то К - расстояние от плоскости до начала координат.
Пример 7. Б
Найдем точку пересечения прямой, соединяющей точки (1,2,3) с (-1,0,2), и плоскости (0,-2,1)*Х=5, а также расстояние от плоскости до начала координат
B =(1,2,3) N =(0,-2,1)
D =(-1,0,2)-(1,2,3)=(-2.-2,-1) N*B =(0* 1,-2*2,1*3)=-1 N*D =(0*-2,-2*-2,1*-1)=3
откуда значение MU, соответствующее точке пересечения, есть (5-(-1))/3=2, а точка пересечения (1,2,3)+2(-2,-2,-1)=(-3,-2,1); расстояние от плоскости до начала координат есть
5/(N)=5/SQRT(5)=SQRT(5) Программа на листинге 7.1 позволяет вычислить точку пересечения (массив P) плоскости и прямой. Базовый вектор прямой - B, направляющий вектор прямой - D, нормаль к плоскости - N, константа плоскости К. Обратите внимание на тот факт, что из-за использования десятичной арифметики мы не можем проверить, равно ли нулю скалярное произведение, так как следует учитывать ошибки округления. Всё, что мы можем определить - это является ли скалярное произведение пренебрежимо малым; величина того, что считать бесконечно малым, определяется программистом (на SPECTRUMe это примерно шесть знаков после запятой). LISTING 7.1
100 REM INTERSECTION OF LINE AND PLANE
110 DIM B(3): DIM D(3): DIM N(3):DIM P(3): DIM A$(8)
120 INPUT "BASE VECTOR OF LINE","(";B(1);",";B(2);",";B(3);")"
130 PRINT AT 1,0;"BASE VECTOR OF LINE ","(";B(1);",";B(2);",";B(3);")"
140 INPUT "DIRECTION VECTOR OF LINE ","(";D(1);",";D(2);",";D(3);")"
150 PRINT AT 4,0;"DIRECTION VECTOR OF LINE ","(";D(1);",";D(2);",";D(3);")"
160 INPUT "NORMAL TO PLANE ",,"(";N(1);",";N(2);",";N(3);")"
170 PRINT AT 7,0;"NORMAL TO PLAN ",,"(";N(1);",";N(2);",";N(3);")"
180 INPUT "PLAN CONSTANT ";K
190 PRINT AT 10,0;"PLAN CONSTANT ";K
199 REM CALCULATE POINT OF INTERSECTION (P(1), P(2),P(3)) OF LINE AND PLANE, INPUT ABOVE.
200 LET DOT=N(1)*D(1)+N(2)*D(2)+N(3)*D(3)
209 REM ZERO DOT PRODUCT SO NO INTERSECTION.
210 IF ABS DOT<0.000001 THEN PRINT AT 15,0,-"NO POINT OF INTERSECTION": STOP 220 LET MU=(K-N(1)*B(1)-N(2)*B(2)-N(3)*B(3))/DOT
230 FOR I=1 TO 3: LET P(I)=B(I)+MU*D(I): IF ABS P(I)<0.000001 THEN LET P(I)=0 240 NEXT I: PRINT AT 15,0;"POINT OF INTERSECTION","("
249 REM TIDY UP OUTPUT.
250 FOR I=1 TO 3: LET A$=STR$ P(I): FOR J=1 TO 8 260 IF A$<>" " THEN PRINT A$(J);
270 NEXT J: IF I<>3 THEN PRINT","; 280 NEXT I: PRINT ")" 290 STOP
Точка пересечения двух прямых Предположим, что точка пересечения двух прямых задаваемых, как B1+MU*D1, и B2+LMD*D2, существует (если прямые не компланарны или они параллельны, то точки пересечения не существует). Точка пересечения определяется таким значением MU и LMD, что
B1+MU*D1=B2+LMD*D2 (7.1)
Это уравнение векторное и состоит их трёх скалярных уравнений.
Для разрешимости этого уравнения необходимо, чтобы только два из них были независимыми, а оставшееся являлось бы их следствием. Две прямые параллельны, если вектора D1 и D2 пропорциональны. Возьмём два независимых уравнения, решим их относительно MU и LMD (у нас два уравнения и два неизвестных) и подставим эти значения в третье уравнение для проверки совместимости этих уравнений.
Пример 7.В иллюстрирует этот метод, а на листинге 7.2 содержится программа, находящая этим методом точку пересечения прямых. Базовый и направляющий вектор первой прямой хранится в массивах B и D, а вектора второй прямой - в массивах C и E; найденная точка пересечения записывается в массив P. Обратите внимание, что если два независимых уравнения есть:
A(1,1)*MU+A(1.2)*LMD=B1 (7.2)
A(2,1)*MU+A(2,2)*LMD=B2 (7.3)
то их детерминант DELTA=A(1,1)*А(2,2)-А(1,2)*А(2,1) отличен от нуля (так как уравнения независимы), и решения можно записать в виде:
MU=(A(2,2)*B1-A(1,2)*B2)/DELTA; LMD=(A(1,1)*B2-A(2,1)*B1)/DELTA.
LISTING 7.2
100 REM INTERSECTION OF TWO LINES
110 DIM B(3): DIM D(3): DIM C(3): DIM E(3): DIM P(3): DIM A$(8)
120 INPUT "BASE VECTOR OF FIRST LINE ","("; B(1);",";B(2);",";B(3);"),"
130 PRINT AT 1,0;"BASE VECTOR OF FIRST LINE ","(";B(1);",";B(2);",";B(3);")"
140 INPUT "DIRECTION VECTOR OF FIRST LINE ","(";D(1);",";D(2);",";D(3);")"
150 PRINT AT 4,0;"DIRECTION VECTOR OF FIRST LINE ","(";D(1);",";D(2);",";D(3);
160 INPUT "BASE VECTOR OF SECOND LINE ","(";C(1);",";C(2);",";C(3);")" 170 PRINT AT 7,0;"BASE VECTOR OF SECOND LINE ","(";C(1);",";C(2);",";C(3);")" 180 INPUT "DIRECTION VECTOR OF SECOND LINE ","(";E(1);",";E(2);",";E(3);")" 190 PRINT AT 10,0;"DIRECTION VECTOR OF SECOND LINE ","(";E(1);",";E(2);","; E(3);")"
199 REM CALCULATE POINT OF INTERSECTION (P(1),P(2),P(3)) OF TWO LINES, DATA INPUT ABOVE. FIND ANY TWO INDEPENDENT LINE EQUATIONS FROM THE THREE (X/Y/Z).
200 FOR I=1 TO 3
210 LET J=I+1: IF J=4 THEN LET J=1 220 LET DELTA=E(I)*D(J)-E(J)*D(I) 230 IF ABS DELTA>0.000001 THEN GO TO 260 240 NEXT I
249 REM CANNOT FIND TWO INDEPENDENT EQUATIONS-LINES DO NOT INTERSECT.
250 PRINT AT 15,0;"LINES DO NOT INTERSECT": STOP
259 REM CALCULATE MU AND LAMBDA VALUES OF POINT OF INTERSECTION.
260 LET MU=(E(I)*(C(J)-B(J))-E(J)*(C(I)-B(I)))/DELTA 270 LET LAMBDA=(D(I)*(C(J)-B(J)-D(J))*(C(I)-B(I)))/DELTA
279 REM NO SOLUTION IF MU AND LAMBDA DO NOT MATISFY THIRD EQUATION.
280 LET K=J+1: IF K=4 THEN LET K=1
290 IF ABS(B(K)+MU*D(K)-C(K)-LAMBDA*E(K))>0.000001 THEN GO TO 250
299 REM CALCULATE (P(1),P(2),P(3)) USING MU VALUE.
300 FOR I=1 TO 3: LET P(I)=B(I)+MU*D(I): IF ABS P(I)<0.000001 THEN LET P(I)=0 310 NEXT I: PRINT AT 15,0,-"POINT OF INTERSECTION ","(";
319 REM TIDY UP OUTPUT.
320 FOR I=1 TO 3: LET A$=STR$ P(I): FOR J=1 TO 8 330 IF A$(J)<>" " THEN PRINT A$(J);
340 NEXT J: IF I<>3 THEN PRINT","; 350 NEXT I: PRINT ")" 360 STOP Пример 7.В.
Найдите точки пересечения (если они имеются) (A) (1,1,1)+MU(2,1,3) с уравнением (0,0,1)+LMD(-1,1,1) (Б) (2,3,4)+MU (1,1,1) с уравнением (-2,-3,-4)+LMD(1,2,3) В (А) эти три уравнения есть:
1 +2 *MU=0-LMD (7.4)
1+MU=0+LMD (7.5)
1 +3 *MU= 1+LMD (7.6)
Из уравнений 7.4 и 7.5 мы получаем MU=-2/3 и LMD=1/3, подставляя в уравнение 7.6, получаем 1+3x(-2/3)=-1 в левой части уравнения и 1+1x(1/3)=4/3 - в правой части, так, что прямые не пересекаются.
Из (Б) следуют уравнения:
2+MU=-2+LMD (7.7)
3+MU=-3+2LMD (7.8)
4+MU =-4+3LMD (7.9)
Из 7.7 и 7.8 получаем MU=-2 и LMD=2, и эти значения удовлетворяют 7.9 (правая и левая части равны 2). Так что точка пересечения:
(2,3,4)-2(1,1,1)=(-2,3,4)+2(1,2,3)=(0,1,2) Плоскость, проходящая через три неколлинеарные точки Для решения задачи мы вводим понятие векторного произведения двух векторов, результатом которого является вектор
P*Q=(P1,P2,P3)*(Q1,Q2,Q3)=(P2*Q3-P3*Q2,P3*Q1-P1*Q3,P2*Q3-P3*Q2)
Если P и Q не параллельны, то вектор P*Q перпендикулярен как P, так и Q. Следует отметить, что векторное произведение не коммутативно, то есть P*Q^Q*P. При изменении порядка сомножителей векторного произведения вектор результата меняет направление на противоположное. Например, (1,0,0)*(0,1,0)=(0,0,1), но (0,1,0)*(1,0,0)=(0,0,-1); вектора (0,0,1) и (0,0,-1) оба параллельны оси Z. На листинге 7.3 приведена программа, вызывающая подпрограмму "VECPROD" (для векторов L и M вычисляется их векторное произведение N, и "DOTPROD", (вычисляющее значение DOT скалярного произведения L и M); обе эти программы приведены на листинге 7.4. LISTING 7.3
100 REM DOT PRODUCT AND VECTOR PRODUCT 110 LET VECPROD=300: LET DOTPROD=400 120 DIM L(3): DIM M(3): DIM N(3)
130 INPUT "VECTOR L ","(";L(1);",";L(2);",";L(3);")"
140 PRINT AT 1,O;"VECTOR L ","(";L(1);",";L(2);",";L(3);")"
150 INPUT "VECTOR M ","(";M(1);",";M(2);",";M(3);")"
160 PRINT AT 4,0;"VECTOR M ","(";M(1);",";M(2);",";M(3);")"
170 GO SUB VECPROD
180 PRINT AT 8,0;"VECTOR PRODUCT ","(";N(1);",";N(2);",";N(3);")" 190 GO SUB DOTPROD
200 PRINT AT 11,0;"DOT PRODUCT "-DOT 210 STOP LISTING 7.4
300 REM VECPROD
301 REM IN - L(3),M(3)
302 REM OUT- N(3)
309 REM N IS THE VECTOR PRODUCT OF L AND M.
310 LET NI=2: LET NNI=3 320 FOR I=1 TO 3
330 LET N(I)=L(NI)*M(NNI)-L(NNI)*M(NI)
340 LET NI=NNI: LET NNI=NI+1: IF NNI=4 THEN LET NNI=1 350 NEXT I 360 RETURN
400 REM DOTPROD
401 REM IN - L(3),M(3)
402 REM OUT - DOT
409 REM DOT IS THE DOT PRODUCT OF L AND M.
410 LET DOT=0
420 FOR I=1 TO 3: LET DOT=DOT+L(I)*M(I): NEXT I 430 RETURN
Предположим, что даны три неколлинеарные точки - P1, P2 и P3, тогда векторы P2-P1 и P3-P1 представляют два направления, пересекающиеся в P1 и лежащие в плоскости, содержащей эти три точки. Мы знаем, что нормаль к плоскости перпендикулярна каждой линии, лежащей в плоскости, в частности и двум упомянутым выше. Так как эти точки неколлинеарны, то P2-P1=P3-P1 и нормаль к плоскости есть (P2-P1)*(P3-P1), а уравнение прямой есть ((P2-P1)*(P3-P1)*(X-P1))=0 Пример 7.Г
Найдите уравнение плоскости, проходящей через точки (0,1,1), (1,2,3) и (-2,3,-1). Точка такой плоскости удовлетворяет
(((1,2,3)-(0,1,1)*((-2,3,-1)-(0,1,1)))*((X,Y,Z)-(0,1,1))=0,
что даёт
((1,1,2)*(-2,2,-2)*(X,Y-1,Z-1)=0 или (-6,-2,4)*(X,Y-1,Z-1)=0 Это равносильно -6Х -2Y + 4Z -2 - 0, а это равносильно ЗХ + Y - 2Z - -1.
Точка пересечения трёх плоскостей Предположим, что плоскости заданы уравнениями 7.10-7.12, приведенными ниже:
N1*X=K1 (7.10)
N2*X=K2 (7.11)
N3 *X=K3 (7.12)
где N1=(N(1,1),N(1,2),N(1,3)), N2=(N(2,1),N(2,2),N(2,3)), N3=(N(3,1),N(3,2),N(3,3)). Мы можем переписать эти уравнения в матричном виде:
N(1,1) N(1,2) N(1,3) X K1
N(2,1) N(2,2) N(2,3) * Y = K2 N(3,1) N(3,2) N(3,3) Z K3
Решение задается в виде столбца
X N(1,1) N(1,2) N(1,3) K1
Y = N(2,1) N(2,2) N(2,3) * K2 Z N(3,1) N(3,2) N(3,3) K3
Мы видим, что вычисление точки пересечения трёх плоскостей требует нахождения обратной матрицы размера (3*3). На листинге 7.5 приводится программа, вычисляющая обратную матрицу присоединённым методом. Обращаемая матрица - N, обратная - M. LISTING 7.5
500 REM INVERSE OF 3*3 MATRIX
501 REM IN - N(3,3)
502 REM OUT- M (3,3), SINGULAR 510 LET SINGULAR=1
520 LET DET=0: LET NI=2:LET NNI=3 530 FOR I=1 TO 3
540 LET DET=DET+N(1,I)*(N(2,NI)*N(3,NNI)-N(2,NNI)*N(3,NI)) 550 LET NI=NNI: LET NNI=NI+1: IF NNI=4 THEN LET NNI=1 560 NEXT I
569 REM DETERMINANT OF SINGULAR MATRIX IS ZERO, THERE IS NO INVERSE.
570 IF ABS DET<0.000001 THEN RETURN
579 REM CALCULATE M, THE INVERSE OF N, BY THE ADJOINT METHOD.
580 LET NI=2: LET NNI=3 590 FOR I=1 TO 3
600 LET NJ=2: LET NNJ=3 610 FOR J=1 TO 3
620 LET M(J,I)=(N(NI,NJ)*N(NNI,NNJ)-N(NI,NNJ)*N(NNI,NJ))/DET 630 LET NJ=NNJ: LET NNJ=NJ+1: IF NNJ=4 THEN LET NNJ=1 640 NEXT J
650 LET NI=NNI: LET NNI=NI+1: IF NNI=4 THEN LET NNI=1
660 NEXT I
670 LET SINGULAR=0
680 RETURN
В программе на листинге 7.6 векторы представляются одномерными массивами; массив B(3) содержит решение уравнений, а K(3) - константы плоскостей. Нормали N1, N2 и N3 задаются в матрице N размерности (3*3). Если две из этих плоскостей параллельны или если эти плоскости пересекаются по прямой, то точка пересечения не единственна; в этом случае переменная DET, равная детерминанту N, равна нулю, и переменная SINGULAR=1. LISTING 7.6
100 REM INTERSECTION OF THREE PLANES
110 DIM N(3,3): DIM M(3,3): DIM K(3) :DIM B(3)
120 LET INV=500
129 REM INPUT DATA OF THREE PLANES.
130 PRINT AT 2,4;"COEFFICIENTS CONSTANT" 140 FOR I=1 TO 3
150 PRINT AT 2+2*I,0;"PLANE(";I;")-( , , )" 160 FOR J=1 TO 3
170 LET I$="INPUT N("+STR$ I+","+STR$ J+") "
180 INPUT (I$);N(I,J): PRINT AT 2+2*I,7+4*J;N(I,J)
190 NEXT J
200 LET I$="INPUT K("+STR$ I+") "
210 INPUT (I$);K(I): PRINT AT 2+2*I,28;K(I)
220 NEXT I
229 REM IF MATRIX OF NORMAL IS SINGULAR THEN NO INTERSECTION.
230 GO SUB INV
240 PRINT AT 12,4;"POINT OF INTERSECTION" 250 IF SINGULAR THEN PRINT AT 12,0;"NO": STOP
259 REM POINT OF INTERSECTION IS (B(1),B(2),B(3)).
260 FOR i=1 TO 3 270 LET B(I)=0 280 FOR J=1 TO 3
290 LET B(I)=B(I)+M(I,J)*K(J) 300 NEXT J
310 IF ABS B(I)<0.000001 THEN LET B(I)=0 320 PRINT AT 12+2*1,7;"B(";I;") = ";B(I) 330 NEXT I 340 STOP
Пример 7.Д
Найдите точку пересечения трёх плоскостей (0,1,1)*Х=2, (1,2,3)*Х=4 и (1,1,1)*Х=0 В матричной форме
есть
-1 0 2 -1
-1 1 -1
|
X |
|
-1 0 1 |
|
2 |
|
-2 |
|
Y |
= |
2 -1 1 |
* |
4 |
= |
0 |
|
Z |
|
-1 1 -1 |
|
0 |
|
2 |
Это решение легко проверить:
(0,1,1)*(-2,0,2) =2, (1,2,3)*(-2,0,2) =4, (1,1,1)*(-2,0,2) =0,
что означает: точка (-2,0,2) принадлежит всем трём плоскостям и, следовательно, является их точкой пересечения.
Линия пересечения двух плоскостей Пусть две плоскости задаются уравнениями
P*X=(P1,P2,P3)*X=K1 Q*X=(Q1,Q2,Q3)*X=K2
Мы полагаем, что плоскости не параллельны и, следовательно, P не- LMD*Q для любого LMD. Прямая, лежащая в обеих плоскостях должна быть перпендикулярна обеим нормалям к этим плоскостям. Это означает, что направление прямой D=P*Q и прямая может быть записана в виде B+MU*Q, где B - любая точка прямой. Для задания прямой мы должны найти этот вектор B. Мы находим точку пересечения этих двух плоскостей третьей, которая не параллельна ни одной из них и не пересекает их по общей прямой. Плоскость с нормалью P*Q удовлетворяет этим условиям (помните, что мы уже вычислили это произведение). Нам остается задать K3. Выберем K3=0, так, что третья плоскость проходит через начало координат. Тогда вектор B задается выражением
f P1 P1 P1 Y1 f K1 ^
P1 Q2
x
vP2* Q2 - P3* Q3 P3* Q1 - P1* Q3 P1* Q2 - Q1* P2J ^ 0 J
Пример 7.Е
Найдите прямую пересечения плоскостей (0,1,1)*X=2 и (1,2,3)*X=2. Так как P=(0,1,1) и Q=(l,2,3), то P*A=(1*3-1*2,1*1-0*3,0*2-1*1)=(1,1,-1). Обратная матрица
f- 5 2 1 ^
= 1
= 3х
V
следовательно, точка пересечения трех плоскостей есть
f-5 2 1 ^ f2
1
4 -1 1 -1 1 -1
2
J
и прямая есть (-2,2,0)+MU*(1,1,-1).
Ответ легко проверить, так как все точки прямой должны удовлетворять уравнению обеих плоскостей (0,1,1)*((-2,2,0)+MU(1,1,-1))=(0,1,1)*(-2,2,0) MU(0,1,1)*(1,1,-1)=2
для всех MU и
(1,2,3)*((-2,2,0)+MU(1,1,-1))=(0,1,1)*(-2,2,0)
MU(1,2,3)*(1,1,-1)=2
для любых MU.
Программа для решения этой задачи приводится на листинге 7.7. Обратите внимание, что она очень похожа на предыдущую программу. Обратите внимание, что для P и Q не выделяются специальные массивы, они хранятся в первых двух строках матрицы N. В массиве B хранится значение базового вектора прямой, значение направляющего вектора прямой D хранится в третьей строке матрицы N.
LISTING 7.7
100 REM LINE OF INTERSECTION OF TWO PLANES
110 DIM N(3,3): DIM M(3,3): DIM K(3): DIM B(3): DIM A$(2)
120 LET INV=500: LET A$="PQ"
129 REM INPUT DATA OF TWO PLANES.
130 PRINT AT 2,4;"COEFFICIENTS CONSTANT" 140 FOR I=1 TO 2
150 PRINT AT 2+2*I,0;"PLANE(";I;")=( , , )" 160 FOR J=1 TO 3
170 LET I$="INPUT "+A$(I)+"("+STR$ J+") "
180 INPUT (I$);N(I,J): PRINT AT 2+2*I,7+4*J;N(I,J)
190 NEXT J
200 LET I$="INPUT K("+STR$ I+")"
210 INPUT (I$);K(I): PRINT AT 2+2*I,28;K(I)
220 NEXT I
229 REM FOR THIRD PLANE.
230 LET N(3,1)=N(1,2)*N(2,3)-N(1,3)*N(2,2) 240 LET N(3,2)=N(1,3)*N(2,1)-N(1,1)*N(2,3) 250 LET N(3,3)=N(1,1)*N(2,2)-N(1,2)*N(2,1) 260 LET K(3)=0
269 REM IF MATRIX OF NORMAL IS SINGULAR THEN NO INTERSECTION.
270 GO SUB INV
280 PRINT AT 10,4;"LINE OF INTERSECTION"
290 IF SINGULAR THEN PRINT AT 10,0;"NO": STOP
300 PRINT AT 12,0;"BASE VECTOR";" DIRECTION"
309 REM LINE OF INTERSECTION - BASE (B(1),B(2),B(3))) AND DIRECTION (N(3,1),N(3,2),N(3,3)).
310 FOR I=1 TO 3 320 LET B(I)=0 330 FOR J=1 TO 3
340 LET B(I)=B(I)+M(I,J)*K(J) 350 NEXT J
360 IF ABS B(I)<0.000001 THEN LET B(I)=0 370 PRINT AT 12+2*I,0;"B(";I;") - ";B(I) 380 PRINT AT 12+2*I,20;"D(";I;") - ";N(3,I) 390 NEXT I 400 STOP
Функциональное представление поверхности Мы видели, что в двумерном случае кривые можно задавать с помощью функциональных зависимостей. Этот метод можно распространить на случай трёх измерений для исследования поверхностей в пространстве. Простейшей формой поверхности является плоскость с нормалью N=(N1,N2,N3), которая, как мы знаем, задается уравнением:
N*X-K=N1*X1+N2*Y+N3*Z-K=0, которое можно переписать в функциональной форме
F(X)=F(X,Y,Z)=N1*X+N1*Y+N*Z-K=N*X-K, где X=(X,Y,Z) .
Это простое выражение позволяет нам разбить пространство на три множества, множество точек X, таких, что F(X)<0 - отрицательная область, множество точек X, лежащих на плоскости таких, что F(X)=0 и множество точек X, таких, что F(X)>0 - положительная область.
Если поверхность разбивает пространство на две связные области (область называется связной, если любые две точки области можно соединить кривой, целиком лежащей в этой области), то эти области можно отождествлять с областью положительных и отрицательных значений. Следует иметь в виду, что многие поверхности делят пространство на большое число компонент; примером такой поверхности является поверхность, задаваемая уравнением F(X,Y,Z)=COS(Y)-SIN(X**2+Z**2). Однако, имеется ряд поверхностей, удовлетворяющих требуемому условию. Примером такой поверхности является сфера
F(X)=R**2-ABS(X)**2
или по компонентам:
F(X,Y,Z)=R**2-X**2-Y**2-Z**2
Если P(X)=0, то X лежит на сфере; если F(X)<0, то точка лежит вне сферы; если F(X)>0, то точка лежит внутри сферы.
Функциональное представление поверхностей весьма полезно при нахождении точек пересечения
поверхностей. Однако, это представление особенно ценно при выяснении того, лежат ли две точки P и Q по одну сторону от поверхности. Для этого достаточно сравнить знаки F(P) и F(Q); если они одного знака, то точки P и Q лежат по одну сторону от поверхности, а если разного - то по разные, что означает, что любая кривая, соединяющая P и Q, пересекает поверхность хотя бы в одной точке. Ниже приведен пример, иллюстрирующий вышесказанное. Лежит ли точка по ту же сторону от плоскости, что и начало координат? Предположим, что плоскость задана тремя неколлинеарными точками. Тогда уравнение плоскости:
((P1-P2)*(P3-P1))*(X-P1)=0 Это уравнение можно переписать в функциональном виде
F(X)=((P2-P1)*(P3-P1))*(X-P1) Все, что нам надо сделать, это сравнить значение F(0) с F(E), где 0 - начало координат, а E - выбранная нами точка. Мы предполагаем, что ни E, ни 0 не лежат в плоскости.
Этот метод является чрезвычайно полезным при исследовании алгоритмов скрытых линий. Пример 7.Ж
Лежат ли точка (1,1,3) и начало координат по одну сторону от плоскости, проходящей через точки (0,1,1), (1,2,3) и (-2,3,-1)?
Из примера 7.Г мы видим, что функция, определяющая плоскость, есть:
F(X)=((-6,-2,4)*(X-(0,1,1))
Отсюда
F(0,0,0)=-(-6,-2,4)*(0,1,1)=-2 F(1,1,3)=(-6,2,4)*(1,1,3)-(0,1,1))=2
Мы видим, что начало координат и точка (1,1.3) лежат по разные стороны от плоскости, так что отрезок, соединяющий эти две точки, пересечет плоскость в точке (1-MU)*(0,0,0)+MU(1,1,3), где 0<MU<1. Каково направление обхода двумерного многоугольника, заданного последовательностью своих
вершин?
Начнём со случая треугольника, заданного вершинами P1=(X1,Y1), P2=(X2,Y2), P3=(X3,Y3). Хотя эти точки заданы на двумерной плоскости, мы можем считать их лежащими в пространстве, полагая, что они принадлежат плоскости X/Y и полагая, что координата Z этих точек равна нулю. Направление сторон треугольника есть (P2-P1), (P3-P2), (P1-P3). Так как эти прямые лежат в X/Y плоскости, то для каждого 1=1,2,3 существует действительное R(I) такое, что
(P(I+1)-P(I))*(P(I+2)-P(I+1))=(0,0,R(I))
Это справедливо потому, что вектор, перпендикулярный плоскости X/Y, имеет одну отличную от нуля координату - Z. Сложение в индексах считается по модулю 3. Так как считается, что точки многоугольника задаются в последовательности обхода многоугольника, то знаки всех R(I) совпадают. Более того, если этот знак положителен, то обход производится против часовой стрелки, а если отрицателен - то по часовой стрелке.
Для заданного многоугольника достаточно проверить три точки для того, чтобы установить последовательность обхода многоугольника. Этот метод окажется незаменимым при исследовании алгоритмов скрытых прямых. На листинге 7.8 приведена программа, устанавливающая порядок обхода трех точек. Пример 7.И
Почему многоугольник, приведенный в примере 3.Г, обходится против часовой стрелки? Вершины этого многоугольника есть (1,0,0), (5,2,0), (4,4,0) и (-2,1,0). Направление сторон - (4,2,0), (-1,2,0), (-6,-3,0), (3.-1.0). Тогда:
(4,2,0)*(-1,2,0) =(0,0,10) (-1,2,0)*(-6,-3,0) =(0,0,15) (-4,-3,0)*(3,-1,0) =(0,0,15) (3,-1,0)*(4,2,0) =(0,0,10)
Мы видим, что все R(I) положительны и, следовательно, многоугольник обходится против часовой стрелки. Будьте внимательны, соблюдая последовательность обхода, так как нарушение последовательности может привести к неверному результату, например: (-6,-3,0)*(4,2,0)=(0,0,0) - прямые параллельны! или (-1,2,0)*(3,-1,0)=(0,0,-5) - мы пропустили вершину. LISTING 7.8
100 REM ORIENTATION OF 2-D TRIANGLE 110 DIM X(3): DIM Y(3)
120 LET K$="TYPE IN ": LET J$="COORDINATES OF TRIANGLE:" 130 FOR I=1 TO 3
140 LET I$="VERTEX ("+STR$ I+") - (" 150 INPUT (K$+J$+I$);X(I);",";Y(I);")" 160 PRINT AT 2+2*1,0;I$;X(I);",";Y(I);")" 170 NEXT I
180 PRINT AT 12,0;"THE TRIANGLE IS ";
188 REM (DX1,DY1) IS 2-D DIRECTOIN VECTOR JOINING POINT 1 TO POINT 2.
189 REM (DX2,DY2) IS 2-D DIRECTION VECTOR JOINING POINT 2 TO POINT 3.
190 LET DX1=X(2)-X(1): LET DY1=Y(2)-Y(1) 200 LET DX2=X(3)-X(2): LET DY2=Y(3)-Y(2)
209 REM USE 3-D VECTOR PRODUCT TO CHECK ON ORIENTATION OF TRIANGLE.
210 IF DX1*DY2-DX2*DY1>0 THEN PRINT "ANTI-";
220 PRINT "CLOCKWISE"
230 STOP
Список программ
1. Листинг 7.1 (пересечение прямой и плоскости). Необходимая информация: базовый вектор (B(1),B(2),B(3)) и направляющий вектор (D(l),D(2),D(3)), задающие прямую; нормаль (N(1),N(2),N(3)) и константа K, задающая плоскость. В качестве входных данных попробуйте (1,2,3), (1,1,-1), (1,0,1) и 2 соответственно.
2. Листинг 7.2 (пересечение двух прямых). Необходимая информация: базовые векторы и направляющие векторы этих прямых: (B(1),B(2),B(3)), (D(1),D(2),D(3)) и (C(1),C(2),C(3)), (E(1),E(2),E(3)). Попробуйте (1,2,3), (1,1,-1) и (-1,1,3), (1,0,1).
3. Листинг 7.3 и 7.4 (MAIN PROGRAM "VECPROD" - "векторное произведение", "DOTPROD" - "скалярное произведение"). Входные данные: два вектора (L(l),L(2),L(3)) и (M(1),M(2),M(3)). Попробуйте (1,2,3), (1,1,-1).
