 |
|
From: FAQ Robot <FAQ.Robot@f185.n5015.z2.fidonet.org>
Date: Mon, 21 Oct 2002 03:40:57 +0400
Subj: FAQ по геометрии.
-+-----------[ Часто задаваемые вопросы по геомерии.]--------------------
[ Создано на основе вопросов, возникавших к конференции Ru.Algorithms. ]
[ Авторство: ]
*Политов Сергей Седов Михаил*
*2:5015/176.18 2:5015/185.2*
[ Последнее обновление: 06.04.2002 ]
[ Все вопросы, дополнения, исправления и прочее просьба отсылать по ]
[ вышеуказанным адресам с пометкой "до востребования". ]
[ Притом: ]
[ с ошибками и дополнениями в алгоритмах по *2:5015/176.18* ]
[ c описками и техническими проблемами по *2:5015/185.2* ]
[ PS У кого есть материал, связанный с тематикай FAQ'а,кто считает, что ]
[ сделано довольно оптимально и понятно, то непременно напишите. ]
Оглавление:
Часть первая. Теория.
1.1 Векторная алгебра и системы координат.
1.1.1 Intro.
1.1.2 Действия над векторами.
1.1.3 Скалярное произведение.
1.1.4 Векторное произведение.
1.1.5 Смешанное произведение векторов.
1.2 Аналитическая геометрия на плоскости.
1.2.1 Основные формулы в Декартовой системе координат.
1.2.2 Перенос и поворот координат.
1.2.3 Уравнения прямой линии.
1.2.4 Взаимое расположение точек и прямых.
1.2.5 Окружность.
1.3 Некоторая особенность программирования.
1.3.1. Зачем это надо?
1.3.2. Как правильно организовать сравнение?
1.3.3. Как выбирать eps?
Часть вторая. Стандартные функции и простейшие задачи.
+ Константы и типы.
1. Площадь многоугольника.
2. Проверка вхождения точки в треугольник.
3. Точка пересечения перпендикуляра и прямой.
4. Задача N 3 с использованием параметрического задания прямой.
5. Расстояние от точки до прямой.
6. Принадлежность точки отрезку.
7. Расстояние от точки до прямой (прямая задана через Ax + By + C = 0).
8. Принадлежность точки прямой.
9. Получение уравнения прямой.
10. Расстояние от точки до отрезка.
11. Проверка выпуклости многоугольника.
12. Проверка вхождения точки в многоугольник.
Часть третья. Нетривиальные алгоритмы.
3.1. Как простроить триангуляцию произвольного многоугольника?
3.2. Как простроить выпуклую оболочку?
3.3 Как построить окружность, проходящую через три точки?
[Новости последней версии: ]
[ - Исправлены мелкие ошибки. ]
[ - Добавлены один вопрос в третью часть. ]
*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 не влияет на производительность,
то лучше брать число поменьше.
Часть вторая.
Стандартные функции и простейшие задачи.
+ Константы и типы.
1. Площадь многоугольника.
2. Проверка вхождения точки в треугольник.
3. Точка пересечения перпендикуляра и прямой.
4. Задача N 3 с использованием параметрического задания прямой.
5. Расстояние от точки до прямой.
6. Принадлежность точки отрезку.
7. Расстояние от точки до прямой (прямая задана через Ax + By + C = 0).
8. Принадлежность точки прямой.
9. Получение уравнения прямой.
10. Расстояние от точки до отрезка.
11. Проверка выпуклости многоугольника.
12. Проверка вхождения точки в многоугольник.
const
maxn = 100; { Максимальное количество вершин в многоугольнике }
eps = 1e-9; { Малое число выбирается в зависимости от необходимой
точности ответа, подробнее в 1.3 }
{ Используемые типы }
type
float = double; { Для простоты замены используемого типа в зависимости
от необходимой точности и ограничения на память. }
tpoint = record x, y : float; end;
tsegment = record { Отрезок, задается кому как нравится }
case byte of
0: (a: array [1..2] of tpoint;);
1: (p1, p2: tpoint);
2: (x1, y1, x2, y2: float);
end;
tpoly = array[0..maxn] of tpoint;
{ Первый способ задания полигона, количество вершин
храниться в отдельной переменной, лучше использовать
когда в задаче рассматривается 1-2 полигона }
tpolygon = record
n : integer;
p : tpoly;
{ Второй способ задания полигона, используется когда
полигонов много}
end;
ttriangle = array[1..3] of tpoint;
tline = record a,b,c: float; end; { Для Ax + By + C = 0 }
{ *Внимание*:
Все функции написаны в расчете на то что выполнено "замыкание"
многоугольника,
т.е. p[0] := p[n]; p[n+1] := p[1]; }
{ _Функция возвращает площадь многоугольника._
Используется свойство векторного произведения : векторное произведение равно
ориентированной прощади параллелограмма, построенного на векторах, входящих
в векторное прозведение. Складывать площадь будем из треугольников (одна вер-
шина - (0, 0), другие - две соседние из массива tpoly). }
function square(p: tpoly; n: integer): float;
var
i: integer;
s: float;
begin
s:= 0.0;
for i:= 1 to n do
s:= s + (p[i].x*p[i-1].y-p[i-1].x*p[i].y);
square:= abs(s)*0.5;
end;
{ _Проверка вхождения точки в треугольник._
Опять же векторное произведение. Проверяем лежит ли точка по одну сторону от
всех сторон треугольника.}
function intriangle(q: tpoint; t: ttriangle): boolean;
var v: float;
begin
v:= (q.x-t[1].x)*(t[2].y-t[1].y)-(q.y-t[1].y)*(t[2].x-t[1].x);
intriangle:= false;
if((q.x-t[2].x)*(t[3].y-t[2].y)-(q.y-t[2].y)*(t[3].x-t[2].x))*v>-eps then
if((q.x-t[3].x)*(t[1].y-t[3].y)-(q.y-t[3].y)*(t[1].x-t[3].x))*v>-eps then
intriangle:= true;
end;
{ _Точка пересечения перпендикуляра опущенного из точки, и прямой_
_к которой он опущен(прямая задана точками через которые проходит)._
Голая математика, с использованием свойств в.п. и с.п.}
procedure crsort(q: tpoint; p: tsegment; var w: tpoint);
var a,b,c,d,e,f,g: float;
begin
a:= p.x2-p.x1; b:= p.y2-p.y1; c:= a*q.x+b*q.y;
d:= b; e:= -a; f:= d*p.x1+e*p.y1;
g:= a*e-b*d;
w.x:= (c*e-b*f)/g;
w.y:= (a*f-c*d)/g;
end;
{ Тоже самое только с использованием _параметрического_ задания прямой (может
понадобиться для определения попала точка на отрезок, или нет). }
procedure crsortp(q: tpoint; p: tsegment; var t: float; var w: tpoint);
begin
t:= -((p.x1-q.x)*(p.x2-p.x1)+(p.y1-q.y)*(p.y2-p.y1))/
(sqr(p.x2-p.x1)+sqr(p.y2-p.y1));
w.x:= p.x1*(1.0-t)+p.x2*t;
w.y:= p.y1*(1.0-t)+p.y2*t;
end;
{ _Расстояние от точки до прямой (прямая задана точками через отрезок, оба
конца которого лежат на данной прямой)._
Используем свойства в.п.}
function point2piece(q: tpoint; p: tsegment): float;
begin
point2piece:= abs((q.x-p.x1)*(p.y2-p.y1)-(q.y-p.y1)*(p.x2-p.x1))/
sqrt(sqr(p.x2-p.x1)+sqr(p.y2-p.y1));
end;
{ _Принадлежность точки отрезку._
Считаем расстояние от данной точки до отрезка, и сравниваем с eps.
1) Квадрат расстояния меньше sqr(eps)
2) Находится между перпендикулярными прямыми, проведенными через концы
отрезка.
Проверяется через с.п.}
function belong2piece(q: tpoint; tsegment): boolean;
var t: float;
begin
t:= sqr((q.x-p.x1)*(p.y2-p.y1)-(q.y-p.y1)*(p.x2-p.x1))/
(sqr(p.x2-p.x1)+sqr(p.y2-p.y1));
belong2piece:= false;
if t>sqr(eps) then exit;
if((q.x-p.x1)*(p.x2-p.x1)+(q.y-p.y1)*(p.y2-p.y1))*
((q.x-p.x2)*(p.x2-p.x1)+(q.y-p.y2)*(p.y2-p.y1))<eps then
belong2piece:= true;
end;
{ _Расстояние от точки до прямой (прямая задана через Ax + By + C = 0)._
"Голая теория". Без комментариев.}
function point2line(q: tpoint; s: tline): float;
begin
point2line:= abs(s.a*q.x+s.b*q.y+s.c)/sqrt(sqr(s.a)+sqr(s.b));
end;
{ _Принадлежность прямой._
Считаем квадрат расстояния от точки до прямой и сравниваем с sqr(eps).
Попутно используем умножение вместо деления. }
function belong2line(q: tpoint; s: tline): boolean;
begin
belong2line:= false;
if sqr(s.a*q.x+s.b*q.y+s.c) < sqr(eps)*(sqr(s.a)+sqr(s.b)) then
belong2line:= true;
end;
{ _Получение уравнения прямой_ через координаты отрезка, концы которого лежат
на этой прямой.
Задача решена теоретически. При решение использовался такой способ: запи-
сывалось параметрическое уравнение прямой и, путём исключения параметра, была
получена формула. Если часто используется поиск расстояния от точки до
прямой,
или прямую надо двигать на паралленое расстояние, то можно это уравнение нор-
мировать. Т. е. разделить на sqrt(A^2+B^2). Тогда при нахождении расстояния
не надо делить на эту величину.}
procedure piece2line(p: tsegment; var s: tline);
begin
if (abs(p.x1-p.x2) < eps) and (abs(p.y1-p.y2) < eps) then
writeln('За последствия не ручаюсь!')
else begin
s.a:= p.y2-p.y1;
s.b:= p.x1-p.x2;
s.c:= -s.a*p.y1-p.x1*s.b;
end;
end;
{ _Расстояние от точки до отрезка._
Задача особенна тем, что рассояние до отрезка не всегда равно расстоянию
до прямой, содержашей отрезок. Надо просто немного переделать уже написанный
belong2piece}
function distance2piece(q: tpoint; p: tsegment): float;
var t,w: float;
begin
if((q.x-p.x1)*(p.x2-p.x1)+(q.y-p.y1)*(p.y2-p.y1))*
((q.x-p.x2)*(p.x2-p.x1)+(q.y-p.y2)*(p.y2-p.y1))>-eps then
begin
t:= sqr(q.x-p.x1)+sqr(q.y-p.y1);
w:= sqr(q.x-p.x2)+sqr(q.y-p.y2);
if w<t then t:= w;
end else
t:= sqr((q.x-p.x1)*(p.y2-p.y1)-(q.y-p.y1)*(p.x2-p.x1))/
(sqr(p.x2-p.x1)+sqr(p.y2-p.y1));
distance2piece:= sqrt(t);
end;
{ _Проверка выпуклости многоугольника._
"Классическая задача". Попарно берётся два соседних вектора и векторное
произведение должно иметь один и тот же знак для любой вершины.}
function isconvex(p: tpoly; n: integer): boolean;
var
t: float;
i: integer;
begin
isconvex:= true;
t:= (p[1].x-p[n].x)*(p[2].y-p[1].y)-(p[2].x-p[1].x)*(p[1].y-p[n].y);
for i:= 1 to n-1 do
begin
if abs(t)<eps then
t:= (p[i+1].x-p[i].x)*(p[i+2].y-p[i+1].y)-
(p[i+2].x-p[i+1].x)*(p[i+2].y-p[i].y) else
if t*((p[i+1].x-p[i].x)*(p[i+2].y-p[i+1].y)-
(p[i+2].x-p[i+1].x)*(p[i+2].y-p[i].y))<-eps then
begin isconvex:= false; break end;
end;
end;
{ _Проверка вхождения точки в многоугольник._
Считается количество пересечений луча из этой точки и многоугольника.}
function inpoly(p: tpoint; q: tpoly; n: integer): shortint;
var ans: boolean;
function crs(a1,a2: tpoint): integer;
var x: float;
begin
crs:= 0;
if abs(a1.y-a2.y) < eps then
begin
if(abs(p.y-a1.y) < eps) and ((p.x-a1.x)*(p.x-a2.x)<0.0)then ans:= false;
exit;
end;
if((a1.y-p.y)*(a2.y-p.y)>0.0)then exit;
x:= a2.x-(a2.y-p.y)/(a2.y-a1.y)*(a2.x-a1.x);
if abs(x-p.x)<eps then ans:= false else
if(x<p.x)then
begin
crs:= 1;
if(abs(a1.y-p.y)<eps)and(a1.y<a2.y)then crs:= 0 else
if(abs(a2.y-p.y)<eps)and(a2.y<a1.y)then crs:= 0;
end;
end;
var i,c: integer;
begin
c:= 0; ans:= true;
for i:= 1 to n do
begin
inc(c,crs(q[i],q[i+1]));
if not ans then break;
end;
if not ans then inpoly:= -1 else inpoly:= c and 1;
end;
Часть третья. Нетривиальные алгоритмы.
3.1. Как построить триангуляцию произвольного многоугольника?
3.2. Как построить выпуклую оболочку?
3.3 Как построить окружность, проходящую через три точки?
3.1. Как построить триангуляцию произвольного многоугольника?
Дан произвольный многоугольник. Необходимо найти разбиение этого
многоугольника на треугольники, вершины которых являются вершинами
данного многоугольника. Сложность O(n^2). Алгоритм. Пусть
многоугольник задан координатами своих вершин в порядке обхода по или
против часовой стрелки. При чем порядок обхода является циклическим,
т.е. после последней вершины идет первая, а перед первой последняя.
1) Пусть текущей является первая вершина.
2) Проверяем можно ли добавить треугольник, образованный
текущей вершиной и смежными ей, к триангуляции. Текущую вершину будем
называть основной вершиной многоугольника.
3) Если да, то добавляем его к триангуляции, и удаляем из
многоугольника. Просто удаляем текущую вершину из многоугольника, и
соединяем смежные ей ребром. Текущей вершиной становится вершина,
которая шла перед удаленной. Если же добавить нельзя, то переходим к
следующей вершине.
4) Повторяем пункты 2-4, пока количество вершин в
многоугольнике не станет равным трем.
Возникает логичный вопрос: <Как проверить, что треугольник
можно добавить к триангуляции?>. Отвечаю. Во-первых, угол,
заключенный между сторонами треугольника являющимися сторонами
многоугольника, должен быть меньше пи. Пусть треугольник ABC, и AB,AC
являются сторонами многоугольника, тогда для того, что бы угол BAC,
был меньше пи необходимо и достаточно что бы знак в.п. *BA,BC* ,
совпадал со знаком обхода многоугольника. Во-вторых, треугольник не
должен содержать других вершин многоугольника, кроме тех на которых
построен. Доказательство правильности алгоритма и его сложности.
1) Докажем, что алгоритм работает верно. Т.к. все треугольники
полученные в результате выполнения алгоритма не пересекаются, имеют
своими вершинами только вершины исходного многоугольника и покрывают
весь многоугольник можно сделать вывод что алгоритм работает
правильно.
2) Докажем что сложность алгоритма не превосходит O(n^3).
Очевидно, что за один проход многоугольника мы гарантированно найдем,
по крайней мере, один треугольник удовлетворяющий нашим условиям.
Т.е. всего проходов будет не более чем n-2, количество вершин,
просмотренных за каждый проход n, так же на для проверки вершины на
возможность удаления сложность составляет O(n), в результате
получается сложность O((n-2)*n*(n-3)), или O(n^3).
3) Докажем что сложность алгоритма не превосходит O(n^2). Для
этого достаточно доказать, что триангуляция будет найдена за один
проход. Действительно, новый <правильный> треугольник, может
получиться только в результате удаления вершины, которая являлась
смежной основной вершине этого треугольника, а т.к. при удалении
вершины происходит <откат назад>, то все треугольники будут найдены
за один проход.
3.2. Как построить выпуклую оболочку? (Списано из Thomas H.
Cormen, Charles E. Leiserson, Ronald L. Rivest: "Introduction to
Algorithms"). Выпуклой оболочкой (convex hull) конечного множества
точек Q называется наименьший выпуклый многоугольник, содержащий все
точки из Q (некоторые из точек могут быть внутри многоугольника,
некоторые - на его сторонах, а некоторые будут его вершинами).
Выпуклую оболочку множества Q мы будем обозначать CH(Q). Наглядно
можно представлять себе дело так: в точках Q вбиты гвозди, на которые
натянута резинка, охватывающая из все - эта резинка и будет выпуклой
оболочной множества гвоздей. Описание просмотра Грэхема. Просмотр
Грэхема использует стек S, в котором хранятся точки, являющиеся
кандидатами в выпуклую оболочку. Каждая точка исходного множества Q в
некоторый момент помещается в стек; если она не является вершиной
выпуклой оболочки CH(Q), то через некоторое время точка будет удалена
из стека, а если является - останется. В момент окончания работы
алгоритма в стеке S находятся в точности все вершины выпуклой
оболочки CH(Q) в порядке обхода против часовой стрелки. Исходными
данными для Graham-Scan является множество Q из (не менее чем трех)
точек. Процедура использует функцию Top(S), которая возвращает точку,
находящуюся в вершине стека S (не меняя содержимого стека), а также
функцию NextToTop(S), которая возвращает следующий за вершиной
элемент стека, так же не меняя содержимого.
GrahamScan(Q)
1) пусть p0 - точка из множества Q с наименьшей ординатой (если
таковых несколько - самая левая)
2) пусть <p1,p2,:,pm> - остальные точки множества Q,
отсортированные в порядке возрастания полярного угла (против часовой
стрелки) относительно точки p0. Если есть несколько точек с
одинаковым полярным углом, то оставляем самую удаленную от p0.
3) top[S]<-0
4) Push(S,p0)
5) Push(S,p1)
6) Push(S,p2)
7) for i<=3 to m
8) do while при движении по ломаной
NextToTop(S)->Top(S)-pi
мы двигаемся прямо или направо
9) do Pop(S)
10) Push(S,pi)
11) return S
3.3. Построение окружности, проходящей через три точки.
A = b_x - a_x;
B = b_y - a_y;
C = c_x - a_y;
D = c_y - a_y;
E = A*(a_x + b_x) + B*(a_y + b_y);
F = C*(a_x + c_x) + D*(a_y + c_y);
G = 2.0*(A*(c_y - b_y)-B*(c_x - b_x));
p_x = (D*E - B*F) / G;
p_y = (A*F - C*E) / G;
Если G равно нулю, это значит, что три точки дежат на одной прямой
и не существует окружности конечного радиуса, проходящей через них.
Иначе радиус равен:
r^2 = (a_x - p_x)^2 + (a_y - p_y)^2
r^2 = (a_x - p_x)^2 + (a_y - p_y)^2
© faqs.org.ru