ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : FAQ Robot                            2:5015/185     21 Apr 2002  23:37:56
 To : All
 Subject : [1/4] FAQ по геометрии.
 -------------------------------------------------------------------------------- 
 

 _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], и
 является вектором.
   Геометрическое определение. с = [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 так больше pi, и 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* ). 
   В 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 Перенос и поворот координат._
 
  - Пусть начало координат системы Ox1y1 не совпадает с 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 - A2B2       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 Hекоторая особенность программирования.*
 
 В программах, решающих геометрические задачи, обычно используются вещественные
 числа. При проведении с ними операций необходимо учитывать погрешность вычисле-
 ний, вызванную накоплением ошибок в последних разрядах. Это приводит к тому, 
 что вещественные числа, как правило, нельзя сравнивать обычным образом - их 
 нужно сравнивать с какой-то заданной точностью eps. Hапример, для выяснения,
 равно ли вещественное число 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
 d)      a<=b -> a-b<eps
 e)      a>b -> a>b
 f)      a>=b -> b-a>eps
 
 _1.3.3. Как выбирать eps?_
 
     Обычно в условии говорится, с какой точность должен быть выдан результат.
 Тогда в качестве eps можно взять число в 100, или 1000 раз меньшее. Hапример, 
 если  надо  выдать результат с точностью четыре знака после десятичной точки, 
 то я беру eps  равным  1e-6. Вообще если eps не влияет на производительность, 
 то лучше брать число поменьше.
 
 --- FIDOGATE 4.4.3-snp19beta4
  * Origin: DO THE SKA! (2:5015/185)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор