[1] FAQ по геометрии.
- From
- FAQ Robot ()
- To
- All
- Date
- 2002-11-03T04:30:06Z
- Area
- RU.ALGORITHMS
*1.1 Векторная алгебра и системы координат.*
_1.1.1 Intro._
В данной части FAQ'а рассматриваются два векторных пространства E^2 -
плоскость, и E^3 - трехмерное пространство. В E^2 вектор задается двумя
координатами {x,y}. В E^3 тремя {x,y,z}.
_1.1.2 Действия над векторами._
В E^2:
Сложение (x1,y1)+(x2,y2)=(x1+x2,y1+y2)
Умножение на число a*(x,y)=(a*x,a*y)
В E^3:
Сложение (x1,y1,z1)+(x2,y2,z2)=(x1+x2,y1+y2,z1+z2)
Умножение на число a*(x,y,z)=(a*x,a*y,a*z)
_1.1.3 Скалярное произведение._
Скалярное произведение векторов *a* и *b* обозначается так ( *a*,*b* ),
и является числом.
Геометрическое определение:( *a*,*b* )=| *a* |*| *b* |*cos( *a* ^ *b* ),
где *a* ^ *b* - угол между векторами a и b.
В E^2: ((x1,y1),(x2,y2))=x1*x2+y1*y2.
В E^3: ((x1,y1,z1),(x2,y2,z2))=x1*x2+y1*y2+z1*z2.
_1.1.4 Векторное произведение._
Векторное произведение векторов a и b обозначается так [a,b], и
является вектором из E^3.
Геометрическое определение. с = [a,b] - вектор заданный как:
1) | *c* |=| *a* |*| *b* |*|sin( *a* ^ *b* )|
2) с ортогонален a, с ортогонален b.
3) a, b, c - правая тройка.
В E^2: отсутвует, говориться о числе r = x1*y2-x2*y1, причем |r|=| *c* |,
и r < 0, если *a* ^ *b* больше pi, и r > 0 в противном случае, при r = 0, век-
тора коллинеарны. r также называется ориентированной площадью параллелограмма
построенного на векторах a и b.
В E^3: [(x1,y1,z1),(x2,y2,z2)] = (x3,y3,z3), где
x3 = y1*z2-y2*z1,
y3 = z1*x2-z2*x1,
z3 = x1*y2-x2*y1. Что гораздо проще запомнить как
|i j k |
|x1 y1 z1|
|x2 y2 z2|, где i,j,k - базис, т.е. (x,y,z) = x*i+y*j+z*k.
_1.1.5 Смешанное произведение векторов._
Смешанное произведение векторов a,b,c обозначается так (*a*,b,*c*).
Определение ( *a*,b,*c* )=( *[a,b]*,*c* )=( *a*, *[b,c]*)
В E^2: отсутствует.
|x1 y1 z1|
В E^3: ((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)) = |x2 y2 z2|
|x3 y3 z3|.
При чем СВП равно ориентированному объему параллепипеда построенного на
векторах a, b, c, т.е. равна объему(V) параллепипеда когда a,b,c - правая
тройка, и -V, если a,b,c - левая тройка, если (*a*,b,*c*) = 0, то вектора
a,b,c копланарны.
*1.2 Аналитическая геометрия на плоскости.*
_1.2.1 Основные формулы в Декартовой системе координат._
P1(x1, y1), P2(x2, y2), P3(x3, y3), P4(x4, y4)
- Расстояние:
d(P1, P2) = sqrt((x1-x2)^2 + (y1-y2)^2)
- Угол между двумя веторами P1P2 P3P4:
(x2-x1)(x4-x3) + (y2-y1)(y4-y3) (P1P2, P3P4)
cos(al) = --------------------------------- = -------------------
d(P1, P2)*d(P3, P4) d(P1, P2)*d(P3, P4)
(x2-x1)(y4-y3) - (x4-x3)(y2-y1) [P1P2, P3P4]
sin(al) = --------------------------------- = ------------------
d(P1, P2)*d(P3, P4) d(P1, P2)*d(P3, P4)
(x2-x1)(y4-y3) - (x4-x3)(y2-y1) [P1P2, P3P4]
tg (al) = --------------------------------- = ------------------
(x2-x1)(x4-x3) + (y2-y1)(y4-y3) (P1P2, P3P4)
- Координаты x, y точки P, делящей P1P2 в отношении m/n = p/1
mx2 + nx1 x1 + qx2
x = --------- = ---------;
n + m 1 + p
my2 + ny1 x1 + qx2
y = --------- = ---------;
m + n 1 + p
- Соответственно, если P - середина (n=m), то
x2 + x1 y2 + y1
x = -------; y = -------;
2 2
- Ориентированная площадь S треугольника с вершинами P1, P2, P3:
| x1 y1 1 |
S = 1/2 | x2 y2 1 | = 1/2*[x1(y2-y3)+x2(y3-y1)+x3(y1-y2)]
| x3 y3 1 |
- Площадь положительна, если направление обхода P1P2P3 совпадает с
положительным
(против часовой стрелки) направлением врашения.
_1.2.2 Перенос и поворот координат._
- Пусть начало координат системы O1x1y1 не совпадает с Oxy и угол xOx1 равен
T, то:
x' = (x-x1)cosT + (y-y1)sinT
y' =-(x-x1)sinT + (y-y1)cosT
_1.2.3 Уравнения прямой линии._
- Каноническое уравнение: Ax + By + C = 0, где A^2 + B^2 <> 0
- Уравнение с угловым коэффициентом: y = kx + b, k = tg(alpha)
- Уравнение прямой, проходящей через две не совпадаюшие точки (x1, y1) и (x2,
y2)
y - y1 x - x1 | x y 1 |
------- = ------- или | x1 y1 1 | = 0
y2 - y1 x2 - x1 | x2 y2 1 |
- Параметрическое задание прямой:
/ x = x0 + at
\ y = y0 + bt, где t - параметр.
- Параметрическое через две точки
/x=x1(1-t)+x2*t
\y=y1(1-t)+y2*t,
_1.2.4 Взаимое расположение точек и прямых._
*Точки и прямые.*
- Расстояние от точки P(x0, y0) до прямой Ax+By+C=0 находиться по формуле:
|Ax0 + By0 + C|
S = -----------------
sqrt(A^2 + B^2)
- Три точки лежат на одной прямой, если
| x1 y1 1 |
| x2 y2 1 | = 0
| x3 y3 1 |
*Две прямые:*
A1x + B1y + C1 = 0 A2x + B2y + C2 = 0
- Пересекаются в точке:
B1C2 - B2C1 C1A2 - C2A1
x = -----------; y = -----------
A1B2 - A2B1 A1B2 - A2B1
- Угол между ними:
A1B2 - A2B1
tg(alpha)= -----------
A1A2 + B1B2
- Прямые параллельны, если A1B1 - A2B1 = 0
- Прямые перпендикулярны, если A1A2 + B1B2 = 0
- Уравнение нормали к прямой, проходящей через точку (x1, y1):
A1(y - y1) = B1(x - x1)
- Уравнение параллельной: A1x + B1y + C = 0
- Расстояние между параллельными (с точностью до знака):
C1 C2
S= --------------- - ---------------
sqrt(A1^2+B1^2) sqrt(A2^2+B2^2)
- Для того, чтобы три прямые пересекались в одной точке необходимо и
достаточно:
| A1 B1 C1 |
| A2 B2 C2 | = 0
| A3 B3 C3 |
_1.2.5 Окружность._
- Уравнение окружности с радиусом R и центром в (x0, y0):
(x-x0)^2 + (y-y0)^2 = R^2
или
/ x = x0 + R*cos(t)
\ y = y0 + R*sin(t), где -pi <= t <= pi
или
x^2 + y^2 + Ax + By + C = 0
- Уравнение касательной в точке (x1, y1) к окружности с центром в начале
координат
y - y1 -x1y1 _+_ R*sqrt(x1^2 + y1^2 - R^2)
------ = ----------------------------------
x - x1 R^2 - x1^2
Также уравнение касательной можно искать из условия, что в уравнении:
_+_ sqrt(R^2-(x-x0)^2) + y0 = kx + b
дискриминант = 0
- Уравнение касательной, имеющей заданный угловой коэффициент k:
y = kx _+_ R*sqrt(1+ k^2)
- Уравнение нормали к кривой в точке (x1, y1):
y = (y1/x1)*x
- Уравнение окружности, проходящей через три точки (x1, y1), (x2, y2) и (x3,
y3)
| x^2 + y^2 x y 1 |
| x1^2 + y1^2 x1 y1 1 | = 0
| x2^2 + y2^2 x2 y2 1 |
| x3^2 + y3^2 x3 y3 1 |
- Длина L каждой из касательных, проведённых из точки (x1, y1) к окружности
L = sqrt((x1-x0)^2 + (y1-y0)^2 - R^2)
*1.3 Некоторая особенность программирования.*
В программах, решающих геометрические задачи, обычно используются вещественные
числа. При проведении с ними операций необходимо учитывать погрешность вычисле-
ний, вызванную накоплением ошибок в последних разрядах. Это приводит к тому,
что вещественные числа, как правило, нельзя сравнивать обычным образом - их
нужно сравнивать с какой-то заданной точностью eps. Например, для выяснения,
равно ли вещественное число a нулю вместо условия a=0 следует записать
abs(a)<eps. Вот об этом мы и поговорим в этой части FAQ'а.
_1.3.1. Зачем это надо?_
Могу привести небольшой пример, специально написанный под этот случай. Имеются
два отрезка, отрезки выбраны случайно, но так что бы точка их пересечения была
фиксированной. Вот этот фрагмент кода стоит в конце программы, после того как
точка пересечения восстановлена по координатам концов отрезков.
writeln(p.x,#32,p.y); {p - заданная точка пересечения}
writeln(r.x,#32,r.y); {r - рассчитанная точка пересечения}
writeln((r.x=p.x)and(r.y=p.y));
Получается довольно интересный вывод, у меня:
5.00000000000000E+0000 2.00000000000000E+0000
5.00000000000000E+0000 2.00000000000000E+0000
FALSE
Я думаю, комментарии излишни.
_1.3.2. Как правильно организовать сравнение?_
a) a=b -> abs(a-b)<=eps
b) a<>b -> abs(a-b)>eps
c) a<b -> a<b-eps
d) a<=b -> a<=b+eps
e) a>b -> a>b+eps
f) a>=b -> a>=b-eps
_1.3.3. Как выбирать eps?_
Обычно в условии говорится, с какой точность должен быть выдан результат.
Тогда в качестве eps можно взять число в 100, или 1000 раз меньшее. Например,
если надо выдать результат с точностью четыре знака после десятичной точки,
то я беру eps равным 1e-6. Вообще если eps не влияет на производительность,
то лучше брать число поменьше.
--- FIDOGATE 4.4.3-snp19beta4
* Origin: Мой скейт несёт меня в ад (2:5015/185)