Геометрия: отношения между объектами

• Геометрия

Расстояние и площадь

a)      Расстояние между двумя точками с координатами $(x_1,y_1)$ и $(x_2,y_2)$ вычисляется по формуле $d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

b)      Расстояние $d$ от точки $P_1(X_1,Y_1)$ до прямой $Ax + By + C = 0$ вычисляется следующим образом.

Предположим, что выбрана точка $P_0(x_0,y_0)$, лежащая на прямой (рисунок 5), тогда $d$ есть проекция отрезка ${P_1}{P_0}$ на вектор $n(A,B)$. Используя формулы скалярного произведения и свойство $A{x_0}+B{y_0}+C=0$, получим: $d=\frac{|A(x_1-x_0)+B(y_1-y_0)|}{\sqrt{A^2+B^2}}$, или окончательно $d=\frac{|A{x_1}+B{y_1}+C|}{\sqrt{A^2+B^2}}$,

$\frac{a{x_p}+b{y_p}+c}{a^2+b^2}={-{k}}$
$p=\frac{|a{x_p}+b{y_p}+c|\sqrt{a^2+b^2}}{a^2+b^2}=\frac{|a{x_p}+b{y_p}+c|}{\sqrt{a^2+b^2}}$

Альтернативный путь решения (предложен Максимом Кочановым)

Генерируем 2 случайные точки на прямой.

По формуле Герона площадь треугольника: $S=\sqrt{p(p-a)(p-b)(p-c)}$, где $p = \frac{a + b + c}2$ - полупериметр.

С другой стороны $S = \frac{HD}{2}$, где $H$ - высота треугольника (расстояние до точки), $D$ - основание треугольника.

 

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

c)      Вычисление расстояния $d$ от точки (X₁, Y₁) до луча или отрезка отличается от вышеописанного, так как основание перпендикуляра, опущенного из точки на продолженную прямую, может не лежать на луче/отрезке. В этом случае кратчайшим расстоянием будет дистанция от точки до начальной точки луча или одной из начальных точек отрезка.

d)     Площадь треугольника со сторонами $a, b, c$ по формуле Герона $S=\sqrt{p(p-a)(p-b)(p-c)}$, где $p$ – полупериметр треугольника $p = \frac{a + b + c}2$.

e)      Площадь треугольника со сторонами a, b и углом между ними φ вычисляется как половина площади параллелограмма, построенного на этих сторонах, с использованием формулы векторного произведения.

S_D = |[a × b]| / 2 = |(x₁· Y₂ - x₂·Y₁)| / 2.

f)       Площадь произвольного многоугольника вычисляется как сумма ориентированных площадей треугольников, у которых одна вершина – начало координат, а две другие – пары вершин многоугольника (последовательные концы сторон).

$S=\displaystyle\sum\limits_{i=1}^N{S_i}$, где $S_i$ – площадь $i$-го треугольника, $N$ – количество вершин многоугольника.

Площади треугольников вычисляются по следующим формулам:

$S_i=({x_i}{y_{i+1}}-x_{i+1}y_i)/2$, $i=1,2,...,{N-1}$,

$S_N=({x_N}{y_1}-{x_1}{y_N})/2$,

Если вершины нумеровать с 0 и индекс вершины брать по модулю $N$, то эти две формулы объединяются в одну.

Параллельность и перпендикулярность

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

Определение того, пересекаются ли две прямые, заданные уравнениями
A₁x + B₁y + C₁ = 0 и A₂x + B₂y + C₂ = 0, сводится к следующему:

• вычисляется определитель второго порядка Δ = A₁ B₂ – A₂ B₁;
• проверяется, равен ли он нулю;
• если равен, то делается вывод о параллельности прямых;
• если не равен, то прямые пересекаются;
• координаты точки пересечения прямых находятся по следующим формулам Крамера:
  x = -Δ_x/Δ и у = - Δ_у/Δ, где Δ_x = c₁ B₂ – C₂ B₁, Δ_у = A₁ C₂ – A₂ c₁;
• если A₂ = B₁ и B₂ = - A₁, то прямые перпендикулярны.

Взаимное расположение двух отрезков можно проверить с помощью четырех векторных произведений (рис. 6).

V₁ = (x₃ - x₁)(y₄ – y₁) – (x₄ – x₁)(y₃ – y₁)

V₂ = (x₃ - x₂)(y₄ – y₂) – (x₄ – x₂)(y₃ – y₂)

V₃ = (x₁ - x₃)(y₂ – y₃) – (x₂ – x₃)(y₁ – y₃)

V₄ = (x₁ - x₄)(y₂ – y₄) – (x₂ – x₄)(y₁ – y₄)

Отрезки пересекаются, если одновременно выполняются два условия: V₁V₂<0 (векторные произведения V₁ и V₂ разных знаков), V₃V₄<0 (векторные произведения V₃ и V₄ разных знаков). Если V₁V₂>0 или V₃V₄>0, то отрезки не пересекаются.

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

4.2.3. Внутри и снаружи

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

Для выпуклого N-угольника существует несколько способов определения принадлежности точки многоугольнику:

1)      Вычислить сумму площадей треугольников, образованных смежными сторонами многоугольника и заданной точкой, используя формулу Герона. Сравнить с площадью многоугольника, вычисленной по векторному произведению как в пункте 4.2.1. Если площади равны (или отличаются не более чем на заданную малую величину), то точка внутри многоугольника.

2)      Проверить, если вершины и данная точка лежат в одной полуплоскости от каждой стороны N-угольника, то точка внутренняя. В уравнение прямой через каждые две соседние вершины x_i,y_i и X_i+1,y_i+1, подставляем координаты данной точки X,Y и по очереди координаты всех остальных вершин. Другими словами, необходимо, чтобы полученные значения функции F(x_i,y_i,X_i+1,y _i+1,X,y) =  (X_i+1- X_i)(y-Y_i)-(X- X_i)(y_i+1-Y_i) при разных x_i, y_i, X_i+1, y_i+1 (i = 1, …,  N-1) были одного знака, тогда точка внутри многоугольника.

3)      Составить N векторных произведений (один вектор — сторона многоугольника, а второй вектор — из точки до одной из вершин на стороне) и проверить, все ли они одного знака (если одного, то точка внутри).

Для произвольного N-угольника все эти способы работают не всегда. Необходимо использовать следующие способы:

4)      Проверить, чему равна сумма углов вокруг исследуемой точки, то есть сумма углов, под которыми видна каждая сторона многоугольника из искомой точки. Причем углы следует брать со знаком, соответствующим последовательному обходу сторон многоугольника. Знак угла определяется векторным произведением радиус-векторов от заданной точки до вершин многоугольника, определяющих сторону. Величина угла определяется по формуле арккосинуса для найденного из скалярного произведения косинуса угла. Если точка внутренняя, то сумма углов по модулю — 2p, если наружная, то ноль. В программе достаточно произвести сравнение абсолютной величины суммарного угла с p (больше либо меньше π).

5)      Провести через точку произвольную прямую. Если она не пересекает ни одну из сторон многоугольника, то точка лежит снаружи. Если пересечения есть, то определить количество пересечений луча, выходящего из данной точки в любую сторону, со сторонами многоугольника. Точка внутри, если количество пересечений нечетно.

Площадь многоугольника

$S = (x_1 - x_0) (y_2 - y_0) - (y_1 - y_0) (x_2 - x_0)$ - ориентированная площадь