Базовые соотношения и алгоритмы геометрии (RU)
Простейшими фигурами на плоскости (геометрическими примитивами) являются точка и прямая.
Отрезком называется ограниченная часть прямой.
Углом называется совокупность двух лучей, которые выходят из одной точки.
Векторомназывается направленный отрезок прямой.
Пусть a(x1, y1) и b(x2, y2) – векторы.
Модуль вектора a: |a| = ;
Скалярное произведение векторов a и b:
(a, b) = |a|·|b|·cos(a, b) = x1·x2 + y1·y2.
Векторное произведение векторов a и bна плоскости:
ax b = |a|·|b|·sin(a, b) = = x1y2 – x2y1 = - b x a.
Векторное произведение a и b положительно, если кратчайший поворот, который совмещает b с a, происходит по часовой стрелке, и отрицательно, если против.
Векторным произведением векторов a и bв пространстве называется вектор ax b, определяемый следующими тремя условиями:
- Модуль векторного произведения равен произведению модулей перемножаемых векторов на синус угла между ними: |ax b| = |a|·|b|·sin(a, b);
- Векторное произведение ax b перпендикулярно и вектору a и вектору b.
- Упорядоченная тройка векторов a, b, ax b имеет положительную ориентацию.
Если координаты векторов равны a(x1, y1, z1) и b(x2, y2, z2), то
Уравнение прямой на плоскости имеет вид ax + by + c = 0. Вектор нормали прямой имеет координаты (a, b), направляющий вектор прямой (-b, a).
Прямая с угловым коэффициентом k, которая проходит через точку (0, b), задается уравнением y = kx + b.
Уравнение прямой, проходящей через точки A(x1, y1) и B(x2, y2), имеет вид:
Доказательство. Прямой, проходящей через две точки A и B, является геометрическое место точек X(x, y), для которых векторы AX и AB колинеарны. Векторы AX(x – x1, y – y1) и AB(x2 – x1, y2 – y1) колинеарны, если их координаты пропорциональны. Искомым уравнением прямой является условие пропорциональности координат векторов AX и AB.
Но в таком виде не представимы горизонтальные и вертикальные прямые, так как для них имеет место y1 = y2 или x1 = x2. Уравнение прямой можно переписать в виде:
(y2 – y1) x – (x2 – x1) y – x1y2 + y1x2 = 0
Расстояниемежду точками (x1, y1) и (x2, y2) равно
Расстояние от точки M(x0, y0) до прямойax + by + c = 0равно
d =
Доказательство. Пусть n(a, b) – вектор нормали, проведенной к прямой из точки M1(x1, y1). MA n, искомое расстоняние d = AM1. Обозначим через j угол AM1M. Тогда d = M1M·cosj, скалярное произведение векторов n и M1M (обозначим его через (n, M1M)) равно |n|·|M1M|·cosj, откуда
Пересечение прямых. Пусть на плоскости заданы две прямые a1x + b1y = c1 и a2x + b2y = c2. Прямые параллельны, если их векторы нормалей параллельны, то есть если
В случае параллельности прямые совпадают, если
Если прямые не параллельны, то они пересекаются в одной точке. Точка их пересечения находится решением системы линейных уравнений
методом Крамера:
Функция kramer находит координаты пересечения двух прямых. На вход ей передаются значения a1, b1, c1,a2, b2, c2, а также адреса двух переменных 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(x1, y1), B(x2, y2), C(x3, y3) лежат на одной прямой, если векторы AB(x2 – x1, y2 – y1) и AC(x3 – x1, y3 – y1) колинеарны, то есть имеет место равенство
Для избежания деления на нуль и возможности использования формулы для любых входных данных, следует переписать равенство в виде (x2 – x1)·(y3 – y1) = (x3 – x1)·(y2 – y1).
Расположение двух точек относительно прямой. Две точки А и В лежат по разные стороны от прямой CD, если векторные произведения CD x CA и CD x CB имеют разные знаки, то есть (CD x CA)·(CD x CB) < 0.
Если прямая задана уравнением f(x, y) = ax + by + c = 0, то две точки A(x1, y1) и B(x2, y2) лежат по разные от нее стороны тогда и только тогда, когда
f(x1, y1)· f(x2, y2) < 0
Направление поворота. Совершается движение от точки А до В, затем от В до С. При движении имеет место левый поворот (движение происходит против часовой стрелки), если AB x BC > 0 и правый, если AB x BC < 0.
Уравнение отрезка. Пусть A(x1, y1), B(x2, y2) – концы отрезка AB. Точка X(x, y) принадлежит отрезку AB тогда и только тогда, когда |AX| + |XB| = |AB| или в координатном виде:
Параметрическое уравнение отрезка. Пусть A(x1, y1), B(x2, y2) – концы отрезка AB. Параметрическое уравнение отрезка имеет вид:
x(t) = x1 + (x2 – x1)·t, y(t) = y1 + (y2 – y1)·t, 0 ≤ t ≤ 1
Отрезок является геометрическим местом точек (x(t), y(t)), где 0 ≤ t ≤ 1.
Расстояние от точкиO(x, y) до отрезка AB, заданного координатами концов: A(x1, y1), B(x2, y2). Рассмотрим три варианта взаимного расположения точки и отрезка:
Обозначим d = AB, d1 = OA, d2 = OB. В первом случае угол А не острый, d22 ≥ d21 + d2, искомое расстояние равно d1. Во втором случае угол B не острый, d21 ≥ d22 + d2, искомое расстояние равно d2. Если углы A и B острые, то расстояние от точки O до отрезка AB равно длине высоты треугольника OAB, которая вычисляется по формуле 2·S/d, где S – площадь треугольника OAB.
Пересечение отрезков на прямой. Пусть [x1, x2] и [x3, x4] – два отрезка на прямой (x1 < x2, x3 < x4). Отрезки не пересекаются, если имеет место одно из двух расположений:
Если x3 > x2, то должно быть x4 > x1. Если x1 > x4, то должно быть x2 > x3. Эти два условия можно объединить в одно. Отрезки не пересекаются тогда и только тогда, когда имеет место неравенство: (x3 – x2)·(x4 – x1) > 0. Если это произведение неположительно, то отрезки пересекаются.
Мера пересечения отрезков на прямой. Пусть [x1, x2] и [x3, x4] – два пересекающихся отрезка.
Пусть left = max(x1, x3) – максимум левых концов, right = min(x2, x4) – минимум правых. Тогда значение right–left будет длиной общей части отрезков.
Пересечение отрезков на плоскости. Пусть заданы два отрезка AB и CD координатами своих концов.
Ограничивающим прямоугольникомгеометрической фигуры называется наименьший из прямоугольников со сторонами, параллельными осям координат, который содержит в себе эту фигуру. Для отрезка с концами (x1, y1) и (x2, y2) ограничивающим будет прямоугольник с левым нижним углом (x1', y1') и правым верхним углом (x2', y2'), где x1' = min(x1, x2), y1' = min(y1, y2), x2' = max(x1, x2), y2' = max(y1, y2).
Отрезки AB и CD пересекаются тогда и только тогда, когда:
- Пересекаются прямоугольники, которые их ограничивают;
- [AC x AB]·[AD x AB] ≤ 0;
- [CA x CD]·[CB x CD] ≤ 0.
Ниже представлены различные случаи взаимного расположения двух отрезков и соответствующие значения векторных произведений:
В следующем примере каждый из отрезков пересекает прямую, содержащую второй отрезок. Но при этом не пересекаются прямоугольники, их ограничивающие.
Пусть концы отрезков AB и CD имеют координаты: A(x1, y1), B(x2, y2), C(x3, y3), D(x4, y4). Функция 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(x1, y1), B(x2, y2) – концы отрезка AB, C(x3, y3), D(x4, y4) – концы отрезка CD. Запишем параметрические уравнения отрезков:
AB: x(t1) = x1 + (x2 – x1)·t1, y(t1) = y1 + (y2 – y1)·t1, 0 ≤ t1 ≤ 1,
CD: x(t2) = x3 + (x4 – x3)·t2, y(t2) = y3 + (y4 – y3)·t2, 0 ≤ t2 ≤ 1,
Отрезки пересекаются, если существуют такие t1, t2 (0 ≤ t1, t2 ≤ 1), что
x(t1) = x(t2), y(t1) = y(t2)
Или то же самое, что
x1 + (x2 – x1)·t1= x3 + (x4 – x3)·t2
y1 + (y2 – y1)·t1 = y3 + (y4 – y3)·t2
Имеем систему линейных уравнений относительно t1 и t2, которую решаем методом Крамера.
Серединный перпендикуляр. Пусть A(x1, y1), B(x2, y2) – координаты концов отрезка, ax + by + c = 0 уравнение серединного перпендикуляра к нему. Тогда
a = x2 – x1, b = y2 – y1,
Уравнение окружности с центром в точке (a, b) и радиусом r имеет вид:
(x – a)2 + (y – b)2 = r2
Полярный угол. Пусть A(x1, y1) и B(x2, y2) – две точки на плоскости, О – начало координат. Вектор OA образует больший угол с осью абсцисс, нежели OB, если выполняется одно из следующих условий:
а) y1 < 0, y2 ≥³ 0; б) y2 = 0, x1 > 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(x1, y1), B(x2, y2), C(x3,y3), равна
Вычтем со второй и из третьей строки первую и распишем определитель по третьему столбцу:
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 тогда и только тогда, когда одновременно выполняются следующие три условия:
- вершины C и D лежат по разные стороны от прямой AB: (AB x AC)·(AB x AD) < 0
- вершины C и E лежат по разные стороны от прямой AB: (AB x AC)·(AB x AE) < 0
- вершины C и F лежат по разные стороны от прямой AB: (AB x AC)·(AB x AF) < 0
Пересечение треугольников. Два треугольника не пересекаются тогда и только тогда, когда существует такая прямая, проходящая через одну из шести сторон треугольников, что плоскости треугольников лежат по разные стороны от нее.
Площадь выпуклого многоугольника. Пусть (x1, y1), (x2, y2), …, (xn, yn) – координаты вершин выпуклого многоугольника, заданные в порядке его обхода по или против часовой стрелки. Тогда площадь многоугольника вычисляется по формуле трапеций:
где (xn+1, yn+1) = (x1, y1). Причем значение суммы положительно, если координаты точек заданы в порядке обхода по часовой стрелке, и отрицательно если против.
Пусть массив 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(x1, y1), B(x2, y2), C(x3, y3) – три точки, не лежащие на одной прямой. Тогда уравнение окружности, проходящей через три точки, имеет вид:
Уравнение можно также представить в виде a·(x2 + y2) – bx + cy – d = 0, где
Центр (xc, yc) и радиус r окружности, описанной вокруг треугольника ABC, находится из соотношений:
xc = b / 2a, yc = -c / 2a, r2 = (b2 + c2 – 4ad) / 4a2
Другой метод решения задачи состоит в написании уравнений двух серединных перпендикуляров к отрезкам AB и AC. Точка их пересечения, которую находим методом Крамера, и является центром искомой окружности.
Центр тяжести. Понятие "центр тяжести многоугольника" можно интерпретировать тремя различными способами:
- Масса находится только в вершинах.
- Масса равномерно распределена по границе многоугольника.
- Масса равномерно распределена по области, ограниченной многоугольником.
Рассмотрим каждый из этих случаем в отдельности.
Масса находится только в вершинах. Пусть многоугольник состоит из n вершин, (xi, yi) – координаты i -ой вершины, mi – ее масса. Пусть М – масса всех вершин. Тогда координаты центра тяжести определяются по формулам:
Xc = (m1·x1 + … + mn·xn) / M =
Yc = (m1·y1 + … + mn·yn) / M =
Если каждая вершина весит одинаково, то формулы примут следующий вид:
Xc = (x1 + … + xn) / n =
Yc = (y1 + … + yn) / n =
Масса равномерно распределена по границе многоугольника. В этом случае масса ребра пропорциональна его длине. Каждое ребро мы можем заменить на точечную массу, пропорциональную длине ребра. Обозначим через li длину i - го ребра. Пусть P – периметр многоугольника, P = l1 + … + ln. Тогда формулы координат центра тяжести имеют вид:
Xc = (l1·x1 + … + ln·xn) / P =
Yc = (l1·y1 + … + ln·yn) / P =
Здесь через (xi, yi) обозначены координаты середины i - го ребра.
Масса равномерно распределена по области, ограниченной многоугольником.
Теорема. Пусть фигура Ф является объединением двух других фигур Ф1 и Ф2, пересекающимися только по границе. Тогда центр тяжести фигуры Ф выражается так:
, где
(Xc, Yc) – координаты центра тяжести фигуры Ф;
(Xc1, Yc1) – координаты центра тяжести фигуры Ф1;
(Xc2, Yc2) – координаты центра тяжести фигуры Ф2;
S – площадь фигуры Ф, S1 – площадь фигуры Ф1, S2 – площадь фигуры Ф2.
Кроме того, для треугольника центр тяжести определяется так:
Разобъем многоугольник на треугольники. Для каждого треугольника найдем его центр тяжести (xci, yci) и площадь si. Тогда координаты центра многоугольника можно найти следующим образом:
Здесь m равно количеству треугольников, на которые разбит многоугольник.
Если вершин многоугольника заданы координатами (x0, y0), (x1, y1), …, (xn-1, yn-1), то координаты его центра тяжести вычисляются по формулам
Здесь (xn, yn) = (x0, y0), а через
обозначена площадь многоугольника.
Константа p в языке С объявляется так:
const double pi = acos(-1.0);
Расстояние между точками на сфере. Рассмотрим сферу, на которой точки, задаются парами (широта, долгота) = (latitude, longitude), -89 ≤ latitude ≤ 89, -179 ≤ longitude ≤ 179. Кратчайшее расстояние от точки (lat1, lon1) до (lat2, lon2) на сфере радиуса radius равно
radius·acos(sin(lat1)·sin(lat2) + cos(lat1)·cos(lat2)·cos(lon1 - lon2))
Поворот на угол на плоскости. Выведем формулы поворота на плоскости на угол φ против часовой стрелки. Пусть 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
Отрезок на решетке. Рассмотрим отрезок, концы которого имеют целочисленные координаты (x1, y1) – (x2, y2). Тогда количество целочисленных точек, лежащих на отрезке, равно
1 + НОД(|x1 – x2|, |y1 – y2|)
Пример. Отрезок (1, 0) – (5, 2) содержит 1 + НОД(|5 – 1|, |2 – 0|) = 1 + НОД(4, 2) = 3 целочисленные точки.
Теорема Пика. Площадь S многоугольника с целочисленными вершинами равна сумме
B + G / 2 – 1,
где В равно количеству целочисленных точек внутри многоугольника, а G количеству целочисленных точек на границе многоугольника