Базовые соотношения и алгоритмы геометрии

   Простейшими фигурами на плоскости (геометрическими примитивами) являются точка и прямая.  

   Отрезком называется ограниченная часть прямой.  

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

   Векторомназывается направленный отрезок прямой.

   Пусть a(x₁, y₁) и b(x₂, y₂) – векторы.

   Модуль вектора a: |a| = ;

   Скалярное произведение векторов a и b:

(a, b) = |a|·|b|·cos(a, b) = x₁·x₂ + y₁·y₂.

   Векторное произведение векторов a и bна плоскости:

ax b = |a|·|b|·sin(a, b) = = x₁y₂ – x₂y₁  = - b x a.

   Векторное произведение a и b положительно, если кратчайший поворот, который совмещает b с a, происходит по часовой стрелке, и отрицательно, если против.

   Векторным произведением векторов a и bв пространстве называется вектор ax b, определяемый следующими тремя условиями:

1. Модуль векторного произведения равен произведению модулей перемножаемых векторов на синус угла  между ними: |ax b| = |a|·|b|·sin(a, b);
2. Векторное произведение ax b перпендикулярно и вектору a и вектору b.
3. Упорядоченная тройка векторов a, b, ax b имеет положительную ориентацию.

   Если координаты векторов равны a(x₁, y₁, z₁) и b(x₂, y₂, z₂), то

   Уравнение прямой на плоскости имеет вид ax + by + c = 0. Вектор нормали прямой имеет координаты (a, b), направляющий вектор прямой (-b, a).

   Прямая с угловым коэффициентом k, которая проходит через точку (0, b), задается уравнением y = kx + b.

   Уравнение прямой, проходящей через точки A(x₁, y₁) и B(x₂, y₂), имеет вид:

   Доказательство. Прямой, проходящей через две точки A и B, является геометрическое место точек X(x, y), для которых  векторы AX и AB колинеарны. Векторы AX(x – x₁, y – y₁) и AB(x₂ – x₁, y₂ – y₁)  колинеарны, если их координаты пропорциональны. Искомым уравнением прямой является условие пропорциональности координат векторов AX и AB.

   Но в таком виде не представимы горизонтальные и вертикальные прямые, так как для них имеет место y₁ = y₂ или x₁ = x₂. Уравнение прямой  можно переписать в виде:

(y₂ – y₁) x – (x₂ – x₁) y – x₁y₂ + y₁x₂ = 0

   Расстояниемежду точками (x₁, y₁) и (x₂, y₂) равно 

   Расстояние от точки M(x₀, y₀) до прямойax + by + c = 0равно

d =

   Доказательство. Пусть n(a, b) – вектор нормали, проведенной к прямой из точки M₁(x₁, y₁). MA n, искомое расстоняние d = AM₁. Обозначим через j угол AM₁M. Тогда d = M₁M·cosj, скалярное произведение векторов n и M₁M (обозначим его через (n, M₁M)) равно |n|·|M₁M|·cosj, откуда

   Пересечение прямых. Пусть на плоскости заданы две прямые a₁x + b₁y = c₁ и a₂x + b₂y = c₂. Прямые параллельны, если их векторы нормалей параллельны, то есть если

   В случае параллельности прямые совпадают, если 

   Если прямые не параллельны, то они пересекаются в одной точке. Точка их пересечения находится решением системы линейных уравнений

методом Крамера:

   Функция kramer находит координаты пересечения двух прямых. На вход ей передаются значения a₁, b₁, c₁,a₂, b₂, c₂, а также адреса двух переменных x и y. Если система имеет единственное решение, то функция возвращает 0, а в переменных (x, y) возвращаются координаты точки пересечения. Если прямые параллельны и не имеют общих точек, функция возвращает 1. В случае совпадения прямых функция возвращает 2.

int kramer(double a1, double b1, double c1, double a2,double b2, double c2, double *x, double *y)

{

  double d = a1 * b2 - a2 * b1;

  double dx = c1 * b2 - c2 * b1;

  double dy = a1 * c2 - a2 * c1;

  if (!d) return (dx == 0.0) + 1;

  *x = dx/d; *y = dy/d;

  return 0;

}

   Три точки A(x₁, y₁), B(x₂, y₂), C(x₃, y₃) лежат на одной прямой, если векторы AB(x₂ – x₁, y₂ – y₁) и AC(x₃ – x₁, y₃ – y₁) колинеарны, то есть имеет место равенство

   Для избежания деления на нуль и возможности использования формулы для любых входных данных, следует переписать равенство в виде (x₂ – x₁)·(y₃ – y₁) = (x₃ – x₁)·(y₂ – y₁).

   Расположение двух точек относительно прямой. Две точки А и В лежат по разные стороны от прямой CD, если векторные произведения CD x CA и CD x CB имеют разные знаки, то есть (CD x CA)·(CD x CB) < 0.

   Если прямая задана уравнением f(x, y) = ax + by + c = 0, то две точки A(x₁, y₁) и B(x₂, y₂) лежат по разные от нее стороны тогда и только тогда, когда

f(x₁, y₁)· f(x₂, y₂) < 0

   Направление поворота. Совершается движение от точки А до В, затем от В до С. При движении имеет место левый поворот (движение происходит против часовой стрелки), если AB x BC > 0 и правый, если AB x BC < 0.

  Уравнение отрезка. Пусть A(x₁, y₁), B(x₂, y₂) – концы отрезка AB. Точка X(x, y) принадлежит отрезку AB тогда и только тогда, когда |AX| + |XB| = |AB| или в координатном виде:

   Параметрическое уравнение отрезка. Пусть A(x₁, y₁), B(x₂, y₂) – концы отрезка AB. Параметрическое уравнение отрезка имеет вид:

x(t) = x₁ + (x₂ – x₁)·t, y(t) = y₁ + (y₂ – y₁)·t, 0 ≤ t ≤ 1

   Отрезок является геометрическим местом точек (x(t), y(t)), где 0 ≤ t ≤ 1.

   Расстояние от точкиO(x, y) до отрезка AB, заданного координатами концов:  A(x₁, y₁), B(x₂, y₂). Рассмотрим три варианта взаимного расположения точки и отрезка: 

   Обозначим d = AB, d₁ = OA, d₂ = OB. В первом случае угол А не острый, d²₂  ≥ d²₁ + d², искомое расстояние равно d₁. Во втором случае угол B не острый,  d²₁  ≥ d²₂ + d², искомое расстояние равно d₂. Если углы A и B острые, то расстояние от точки O до отрезка AB равно длине высоты треугольника OAB, которая вычисляется по формуле 2·S/d, где S – площадь треугольника OAB.

   Пересечение отрезков на прямой. Пусть [x₁, x₂] и [x₃, x₄] – два отрезка на прямой (x₁ < x₂, x₃ < x₄). Отрезки не пересекаются, если имеет место одно из двух расположений:

   Если x₃ > x₂, то должно быть x₄ > x₁. Если x₁ > x₄, то должно быть x₂ > x₃. Эти два условия можно объединить в одно. Отрезки не пересекаются тогда и только тогда, когда имеет место неравенство: (x₃ – x₂)·(x₄ – x₁) > 0. Если это произведение неположительно, то отрезки пересекаются.

   Мера пересечения отрезков на прямой. Пусть [x₁, x₂] и [x₃, x₄] – два пересекающихся отрезка.

   Пусть left = max(x₁, x₃) – максимум левых концов, right = min(x₂, x₄) – минимум правых. Тогда значение right–left будет длиной общей части отрезков.

   Пересечение отрезков на плоскости. Пусть заданы два отрезка AB и CD координатами своих концов.

   Ограничивающим прямоугольникомгеометрической фигуры называется наименьший из прямоугольников со сторонами, параллельными осям координат, который содержит в себе эту фигуру. Для отрезка с концами (x₁, y₁) и (x₂, y₂) ограничивающим будет прямоугольник с левым нижним углом (x₁^', y₁^') и правым верхним углом (x₂^', y₂^'), где x₁^' = min(x₁, x₂), y₁^' = min(y₁, y₂), x₂^' = max(x₁, x₂), y₂^' = max(y₁, y₂).

   Отрезки AB и CD пересекаются тогда и только тогда, когда:

1. Пересекаются прямоугольники, которые их ограничивают;
2. [AC x AB]·[AD x AB] ≤ 0;
3. [CA x CD]·[CB x CD] ≤ 0.

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

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

   Пусть концы отрезков AB и CD имеют координаты: A(x₁, y₁), B(x₂, y₂), C(x₃, y₃), D(x₄, y₄). Функция RectanglesIntersects принимает в качестве аргументов 8 координат концов отрезков и выводит 1, если прямоугольники, ограничивающие отрезки AB и CD, пересекаются. Иначе функция возвращает 0.

int RectanglesIntersects(double x1,double y1,double x2,double y2,

                         double x3,double y3,double x4,double y4)

{

  if ((x3 - x2)*(x4 - x1) > 0) return 0;

  if ((y3 - y2)*(y4 - y1) > 0) return 0;

  return 1;

}

   Функция intersect проверяет, пересекаются ли отрезки AB и CD. Сначала проверяется пересечение ограничивающих прямоугольников. Если они пересекаются, то строятся вектора AC, AB, AD, CA, CB, CD (например, координаты вектора CD содержатся в переменных CDx и CDy) и вычисляются векторные произведения, указанные в пунктах 2 и 3. В зависимости от значений векторных произведений формируется возвращаемое значение. Оно равно 1, если отрезки AB и CD пересекаются и 0 иначе.

double intersect(double x1,double y1, double x2, double y2,

                 double x3,double y3, double x4, double y4)

{

  double ABx, ABy, ACx, ACy, ADx, ADy;

  double CAx, CAy, CBx, CBy, CDx, CDy;

  double ACxAB, ADxAB, CAxCD, CBxCD;

  if (!RectanglesIntersects(min(x1,x2),min(y1,y2),max(x1,x2),max(y1,y2),

      min(x3,x4),min(y3,y4),max(x3,x4),max(y3,y4))) return 0;

  ACx = x3 - x1; ACy = y3 - y1;

  ABx = x2 - x1; ABy = y2 - y1;

  ADx = x4 - x1; ADy = y4 - y1;

  CAx = x1 - x3; CAy = y1 - y3;

  CBx = x2 - x3; CBy = y2 - y3;

  CDx = x4 - x3; CDy = y4 - y3;

  ACxAB = ACx * ABy - ACy * ABx;

  ADxAB = ADx * ABy - ADy * ABx;

  CAxCD = CAx * CDy - CAy * CDx;

  CBxCD = CBx * CDy - CBy * CDx;

  return ACxAB * ADxAB <= 0 && CAxCD * CBxCD <= 0;

}

   Точка пересечения отрезков. Пусть A(x₁, y₁), B(x₂, y₂) – концы отрезка AB, C(x₃, y₃), D(x₄, y₄) – концы отрезка CD. Запишем параметрические уравнения отрезков:

AB: x(t₁) = x₁ + (x₂ – x₁)·t₁, y(t₁) = y₁ + (y₂ – y₁)·t₁, 0 ≤ t₁ ≤ 1,

CD: x(t₂) = x₃ + (x₄ – x₃)·t₂, y(t₂) = y₃ + (y₄ – y₃)·t₂, 0 ≤ t₂ ≤ 1,

   Отрезки пересекаются, если существуют такие t₁, t₂ (0 ≤ t₁, t₂ ≤ 1), что

x(t₁) = x(t₂), y(t₁) = y(t₂)

   Или то же самое, что

x₁ + (x₂ – x₁)·t₁= x₃ + (x₄ – x₃)·t₂

y₁ + (y₂ – y₁)·t₁ = y₃ + (y₄ – y₃)·t₂

   Имеем систему линейных уравнений относительно t₁ и t₂, которую решаем методом Крамера.

   Серединный перпендикуляр. Пусть A(x₁, y₁), B(x₂, y₂) – координаты концов отрезка, ax + by + c = 0 уравнение серединного перпендикуляра к нему. Тогда

a = x₂ – x₁, b = y₂ – y₁,  

    Уравнение окружности с центром в точке (a, b) и радиусом r имеет вид:

(x – a)² + (y – b)² = r²

   Полярный угол. Пусть A(x₁, y₁) и B(x₂, y₂) – две точки на плоскости, О – начало координат. Вектор OA образует больший угол с осью абсцисс, нежели OB, если выполняется одно из следующих условий:

а) y₁ < 0, y₂ ≥³ 0;             б) y₂ = 0, x₁ > 0;         в) OA x OB < 0;

   Вычисление полярного угла. Функция PolarAngle вычисляет величину угла вектора p с осью абсцисс. Значение угла изменяется в пределах от 0 до 2π.

double PolarAngle(pair p)

// p != (0,0)

{

  double res = 0;

  int x = p.first, y = p.second;

  if (x == 0)

  {

    if (y > 0)res = PI / 2; else res = 3*PI/2;

  }

  else

  {

    res = atan(1.0*y/x);

    if (x < 0) res = res + PI;

    if (res < 0) res = res + 2*PI;

  }

  return res;

}

   Функция atan(x) вычисляет арктангенс x в пределах от -π/2 до π/2.

   Функция atan2(double y, double x) вычисляет значение арктангенса y/x в пределах от -π до π. Если x = 0, или оба параметра равны нулю,то функция возвращает 0. С использованием atan2 функцию PolarAngle можно переписать в виде:

double PolarAngle(pair p)

{

  double res = atan2(1.0*p.second,1.0*p.first);

  if (res < 0) res += 2*PI;

  return res;

}

   Площадь треугольника ABC, заданного координатами вершин A(x₁, y₁), B(x₂, y₂), C(x₃,y₃), равна

Вычтем со второй и из третьей строки первую и распишем определитель по третьему столбцу:

double TriangleSquare(int x1, int y1, int x2, int y2, int x3, int y3)

{

  return abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)) / 2.0;

}

   Принадлежность точки треугольнику. Точка O лежит внутри треугольника ABC тогда и только тогда, когда все три поворота OAB, OBC и OCA правые  (треугольник ABC ориентирован по часовой стрелке) или левые (треугольник ABC ориентирован против часовой стрелки). То есть все выражения OA x AB, OB x BC, OC x CA имеют одинаковый знак.

   Относительное расположение треугольников. Треугольники ABC и DEF лежат по разные стороны от прямой AB тогда и только тогда, когда одновременно выполняются следующие три условия:

1. вершины C и D лежат по разные стороны от прямой AB: (AB x AC)·(AB x AD) < 0
2. вершины C и E лежат по разные стороны от прямой AB: (AB x AC)·(AB x AE) < 0
3. вершины C и F лежат по разные стороны от прямой AB: (AB x AC)·(AB x AF) < 0

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

   Площадь выпуклого многоугольника. Пусть (x₁, y₁), (x₂, y₂), …, (x_n, y_n) – координаты вершин выпуклого многоугольника, заданные в порядке его обхода по или против часовой стрелки. Тогда площадь многоугольника вычисляется по формуле трапеций:

где (x_n+1, y_n+1) = (x₁, y₁). Причем значение суммы положительно, если координаты точек заданы в порядке обхода по часовой стрелке, и отрицательно если против.

   Пусть массив x содержит абсцисы точек, а y – ординаты, заданные в порядке обхода по или против часовой стрелки. Функция findArea вычисляет площадь многоугольника.

  double findArea(vector x, vector y)

  {

    double s;

    int i;

    x.push_back(x[0]); y.push_back(y[0]);

    for(s = i = 0; i < x.size() - 1; i++)

      s += (y[i+1] + y[i]) * (x[i+1] - x[i]) / 2.0;

    return fabs(s);

  }

   Уравнение окружности через три точки. Пусть A(x₁, y₁), B(x₂, y₂), C(x₃, y₃) – три точки, не лежащие на одной прямой. Тогда уравнение окружности, проходящей через три точки, имеет вид:

   Уравнение можно также представить в виде a·(x² + y²) – bx + cy – d = 0, где

    Центр (x_c, y_c) и радиус r окружности, описанной вокруг треугольника ABC, находится из соотношений:

x_c = b / 2a, y_c = -c / 2a, r² = (b² + c² – 4ad) / 4a²

   Другой метод решения задачи состоит в написании уравнений двух серединных перпендикуляров к отрезкам AB и AC. Точка их пересечения, которую находим методом Крамера, и является центром искомой окружности.

   Центр тяжести. Понятие "центр тяжести многоугольника" можно интерпретировать тремя различными способами:

1. Масса находится только в вершинах.
2. Масса равномерно распределена по границе многоугольника.
3. Масса равномерно распределена по области, ограниченной многоугольником.

   Рассмотрим каждый из этих случаем в отдельности.

   Масса находится только в вершинах. Пусть многоугольник состоит из n вершин, (x_i, y_i) – координаты i -ой вершины, m_i – ее масса. Пусть М – масса всех вершин. Тогда координаты центра тяжести определяются по формулам:

X_c = (m₁·x₁ + … + m_n·x_n) / M =

Y_c = (m₁·y₁ + … + m_n·y_n) / M =

Если каждая вершина весит одинаково, то формулы примут следующий вид:

X_c = (x₁ + … + x_n) / n =

Y_c = (y₁ + … + y_n) / n =

   Масса равномерно распределена по границе многоугольника. В этом случае масса ребра пропорциональна его длине. Каждое ребро мы можем заменить на точечную массу, пропорциональную длине ребра. Обозначим через l_i длину i - го ребра. Пусть P – периметр многоугольника, P = l₁ + … + l_n. Тогда формулы координат центра тяжести имеют вид: 

X_c = (l₁·x₁ + … + l_n·x_n) / P =

Y_c = (l₁·y₁ + … + l_n·y_n) / P =

   Здесь через (x_i, y_i) обозначены координаты середины i - го ребра.

   Масса равномерно распределена по области, ограниченной многоугольником.

   Теорема. Пусть фигура Ф является объединением двух других фигур Ф₁ и Ф₂, пересекающимися только по границе. Тогда центр тяжести фигуры Ф выражается так:

, где

(X_c, Y_c) – координаты центра тяжести фигуры Ф;

(X_c1, Y_c1) – координаты центра тяжести фигуры Ф₁;

(X_c2, Y_c2) – координаты центра тяжести фигуры Ф₂;

S – площадь фигуры Ф, S₁ – площадь фигуры Ф₁, S₂ – площадь фигуры Ф₂.

   Кроме того, для треугольника центр тяжести определяется так:

   Разобъем многоугольник на треугольники. Для каждого треугольника найдем его центр тяжести (x_ci, y_ci) и площадь s_i. Тогда координаты центра многоугольника можно найти следующим образом:

   Здесь m равно количеству треугольников, на которые разбит многоугольник.

   Если вершин многоугольника заданы координатами (x₀, y₀), (x₁, y₁), …, (x_n-1, y_n-1), то координаты его центра тяжести вычисляются по формулам

   Здесь (x_n, y_n) = (x₀, y₀), а через

обозначена площадь многоугольника.

   Константа p в языке С объявляется так:

const double pi = acos(-1.0);

   Расстояние между точками на сфере. Рассмотрим сферу, на которой точки, задаются парами (широта, долгота) = (latitude, longitude), -89 ≤ latitude ≤ 89, -179 ≤ longitude ≤ 179. Кратчайшее расстояние от точки (lat₁, lon₁) до (lat₂, lon₂) на сфере радиуса radius равно

radius·acos(sin(lat₁)·sin(lat₂) + cos(lat₁)·cos(lat₂)·cos(lon₁ - lon₂))

Поворот на угол на плоскости. Выведем формулы поворота на плоскости на угол φ против часовой стрелки. Пусть z’ и z – комплексные числа. Тогда  или x' + iy' = (cosφ + isinφ) (x + iy) = xcosφ – ysinφ + i(xsinφ + ycosφ). Откуда получаем формулы поворота:

x'=xcosφ-ysinφ

y'=xsinφ+ycosφ

#include <stdio.h>

#include <math.h>

#define PI acos(-1.0)

double x, y, fi, xx, yy;

int main(void)

{

  x = 10, y = 0, fi = 90; fi = PI/180 * fi;

  printf("%.4lf %.4lf\n",x,y);

  xx = x * cos(fi) - y*sin(fi);

  yy = x * sin(fi) + y*cos(fi);

  printf("%.4lf %.4lf\n",xx,yy);

  return 0;

}

 Пример. Формула поворота на 90 градусов против часовой стрелки имеют вид:

x'=xcos90°-ysin90°

y'=xsin90°+ycos90°

 или

 x'=-y

y'=x

Отрезок на решетке. Рассмотрим отрезок, концы которого имеют целочисленные координаты (x₁, y₁) – (x₂, y₂). Тогда количество целочисленных точек, лежащих на отрезке, равно

1 + НОД(|x₁ – x₂|, |y₁ – y₂|)

Пример. Отрезок (1, 0) – (5, 2) содержит 1 + НОД(|5 – 1|, |2 – 0|)  = 1 + НОД(4, 2) = 3 целочисленные точки.

 Теорема Пика. Площадь S многоугольника с целочисленными вершинами равна сумме

B + G / 2 – 1,

где В равно количеству целочисленных точек внутри многоугольника, а G количеству целочисленных точек на границе многоугольника