Главная страница

Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться


Скачать 5.46 Mb.
НазваниеПо вопросам приобретения обращаться
АнкорОкулов.Программирование.в.алгоритмах.pdf
Дата26.04.2017
Размер5.46 Mb.
Формат файлаpdf
Имя файлаОкулов.Программирование.в.алгоритмах.pdf
ТипДокументы
#5718
страница16 из 26
1   ...   12   13   14   15   16   17   18   19   ...   26
4. Алгоритмы на графах
219
Разработать программу, которая за возможно меньшее коли- чество ходов расставляет элементы массива по порядку, т. е. в первой строке — от 1 до М, во второй строке — от до и т. д.
Указание. Рассмотрим метод поиска системы различных представителей для нашей задачи. Обозначим элементы каж- дой строки нашей таблицы как
Считаем, что есть множества
(l составленные из элементов, которые не- обходимо разбить на N классов по принадлежности к строке результирующей таблицы. Эти множества удовлетворяют тео- реме Холла, то есть любые q множеств содержат элементы не менее чем q классов.
6 5
2 7
15 13 9
3 10 1
12 16 8
11 14 4
6 1
9 16 8
11 2
-
8 11 14 3
10 5
2
-
15 5
12 4
10 13 2
7
Начинаем работу. Первая итерация (первый столбец правой таблицы). Из выбираем из
— из

так как 2 выбрать нельзя, класс занят, из
— 16, так как
3, 4 и 7 выбирать не имеем права по той же причине. Вторая
итерация. По этой же логике из
— 8,
— 11,
— 2. Вы- брать из нечего — все классы заняты. Строим чередующую- ся цепочку (построение паросоче- тания в двудольном графе), она начинается в и состоит из ре- бер
Эти реб- на рисунке, приведенном ниже, помечены одинарными стрелками. Меняем представите- ля у на 14 из и для по- является представитель — 3 из
(третий столбец правой табли- цы). Третья итерация. Выбира- ем для
— 10, для
— 5, для
— 2. Проблемы выбора для
Строим чередующуюся цепочку:
она выделена на рисунке двойными стрелками и меняем представителей (пятый столбец правой таблицы). Четвертая

220 4. Алгоритмы на графах
итерация. Выбор представителей однозначен. Второй вертика- льный и третий горизонтальный ходы очевидны. При вертика- льном — каждый элемент столбца перемещаем в свою строку, а это можно сделать — у нас по одному представителю; при гори- зонтальном — каждый элемент строки перемещается в свой столбец.
24. Дан взвешенный (ребрам приписаны веса) граф G=(V,E),
естественно связный. Обозначим через D(v,u) минимальное рас- стояние между вершинами Величина
=
называется диаметром графа. Величина мак- симальным удалением в графе от вершины
Величину называют радиусом графа. Любая вершина такая, что называется центром графа. Напи- сать программу поиска диаметра, радиуса и центров графа.
Указание. Первый шаг решения заключается в формирова- нии матрицы минимальных расстояний между всеми парами вершин графа. Дальнейшее очевидно.
25. Плоским графом называ- ется граф, вершины которого являются точками плоскости, а ребра — плоскими непрерывны- ми линиями без самопересече- ний, соединяющими соответст- вующие вершины и не имеющими общих точек, естест- венно, кроме инцидентных им обеим вершинам. Граф, допуска- ющий изображение в виде плоского, называют планарным. Из- вестна теорема Понтрягина-Куратовского: «Граф планарен тогда и только тогда, когда он не содержит в качестве частей графы и
(может быть с добавочными вершинами степе- ни 2)». Графы и
приведены на рисунке.
Планарных графов достаточно мало при больших значениях
N (количества вершин), и выделение в G подграфов типа и
— достаточно сложная задача. Определить, какие подгра- фы содержатся в так называемом графе Пе- терсона, приведенном на рисунке.
26. Гранью называют часть плоско- сти, окруженную простым без самопересечений) и не содержащую внутри себя других элементов графа. Фор- мула Л. Эйлера (1758 г.) связывает число граней, число вершин и ребер пленарного

Алгоритмы на графах 221
графа где | v\ =N, | E \
S+N=M+2. Если граф G без петель и кратных ребер (а в нашем рассмотрении участвуют именно такие графы), то каждая грань ограничена по крайней мере тремя ребрами графа. Из этого факта получается оценка снизу удвоенного числа ребер графа 3*S<2*M. Отсюда следует оценка количества ребер планарного G графа — M<3*N-6 (при
N>3). Проверить то, что графы и
не являются планарны-
27. Согласно теореме Д. Кёнига (1936 г.) для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины. Определить, является ли граф двудольным.
Указание. При поиске в ширину вершины графа помечают- ся метками 0, 1, 2, ... Первой вершине, с которой начинается просмотр, приписывается значение 0, вершинам, связанным с ней, — метка 1 и т. д. Разобьем граф после просмотра на две части: X включает вершины с четными метками, Y — с нечет- ными. Если оба подграфа пусты — исходный граф является двудольным.
28. Задача Штейнера на графах. В связном взвешенном гра- фе G с выделенным подмножеством вершин U требуется найти связный подграф Т, удовлетворяющий двум условиям:
• множество вершин подграфа Т содержит заданное под- множество
• граф Т имеет минимальный вес среди всех подграфов,
удовлетворяющих первому условию.
Указание. Очевидно, что искомый подграф является дере- вом, оно называется деревом Штейнера. Задача сводится к на- хождению дерева минимального веса в подграфах графа G,
множество вершин которых содержит U. Эффективных алго- ритмов решения задачи неизвестно, поэтому ничего другого не остается, как перебрать варианты при небольших значениях N.
29. Задача о пяти ферзях. На шахматной доске 8*8 расста- вить наименьшее число ферзей так, чтобы каждая клетка до- ски была под боем.
Указание. Построить граф для данной доски с учетом пра- вил перемещения ферзя. Всякой искомой расстановке соответ- ствует наименьшее доминирующее множество в графе.
30. Подмножество вершин графа, являющееся как независи- мым, так и доминирующим, называется ядром. Найти ядра графа.
Указание. Независимое множество является максимальным
(не обязательно наибольшим) тогда и только тогда, когда оно является доминирующим. Таким образом, ядра графа — это независимые максимальные множества вершин.

5. Алгоритмы
вычислительной геометрии
В этой главе рассматриваются алгоритмы, связанные с гео- метрией. Они служат хорошим «подспорьем» в изучении данно- го раздела математики. Но это не главное. Главное в том, что вычислительная геометрия (определение Ф. Препарата, В. Шей- моса [24]) является, во-первых, одним из разделов информатики и, во-вторых, источником большого количества научных и при- кладных задач. Эта обширная область знаний, естественно, не рассматривается полностью, а только ее отдельные аспекты, до- ступные школьникам. Дело в том, что задач по информатике,
связанных с вычислительной геометрией, достаточно много, а соответствующих публикаций достаточно мало. В какой-то сте- пени материал этой главы восполняет данный пробел. Кроме того, специфика задач по вычислительной геометрии такова, что их реализация позволяет формировать у школьников структур- ный стиль написания программ.
5.1. Базовые процедуры
Прежде чем перейти к основным алгоритмам, рассмотрим типы данных и базовые процедуры работы с ними. Точка на плоскости описывается парой вещественных чисел. Введем соот- ветствующую запись. При использовании вещественного типа операции сравнения лучше оформить специальными функция- ми. Причина известна, на вещественных типах данных в систе- ме программирования Паскаль нет отношения порядка, поэтому записи вида где а и Ъ вещественные числа, лучше не испо- льзовать. Приведем пример, объясняющий это положение.
Пусть для хранения вещественного типа используются два деся- тичных разряда для порядка и шесть разрядов для хранения мантиссы. Есть два числа:
и fc=0,98765*10-
4
. При сложении и вычитании осуществляется: выравнивание поряд- ков, сложение (вычитание) мантисс и нормализация результата.
После выравнивания порядков
После сложения мантисс имеем: 0,3456700098765*10 4
. Так как для хранения мантиссы у нас шесть десятичных разрядов (в реа- льном компьютере тоже есть ограничение, например, для типа
Real в Турбо Паскале — 11-12 цифр), то результат округляется и

5. Алгоритмы вычислительной геометрии 223
он равен 0,345670*10 4
. Итак,
при fe>0!!! Компьютерная арифметика не совпадает с обычной арифметикой.
На протяжении всей главы используются описанные ниже типы данных, функции и процедуры.
Type Real=Extended;
TPoint=Record x,
Real; End;
Const Eps:
вычисления.*}
ZeroPnt: TPoint = (X:0; Y:0);{*Точка
с координатами 0,0.*}
Реализация операций сравнений: =, <, >,
>.
Function
a, b: Real): Boolean;
равно. *}
Begin
End;
Остальные функции RealMore (строго больше), RealLess
(строго меньше), RealMoreEq (больше или равно), RealLessEq
(меньше или равно) пишутся по аналогии.
Для определения максимального из двух вещественных чи- сел приведенные выше функции уже можно использовать.
Function
a, b: Real): Real;
из двух вещественных чисел. *}
Begin
If RealMore (a, b) Then
Else RealMax:=b;
End;
Аналогично пишется функция RealMin (поиск минимально- го числа) и функция EqPoint совпадения двух точек на плоско- сти.
Function
А, В:
ли точки ?*}
Begin
And
End;
Функция вычисления расстояния между двумя точками на плоскости имеет вид.
Function
А, В: TPoint): Real;
между двумя точками
на плоскости. *}
Begin
+ Sqrt
{*Вспомним теорему Пифагора - «квадрат

224 5. Алгоритмы вычислительной геометрии
гипотенузы прямоугольного
треугольника равен сумме
квадратов катетов». *}
End;
Каждую точку плоскости можно считать вектором, начало которого находится в точке (0,0). Обозначим координаты точки (вектора) v через
Для век-
торов определены следующие операции:
сумма:
• разность:
• скалярное произведение:
;
• векторное произведение:
Скалярным произведением вектора v на вектор w называет- ся число, определяемое равенством где символом I | обозначается длина вектора, а
— угол между векторами. Скалярное произведение обращается в нуль в том и только том случае, когда по крайней мере один из векторов яв- ляется нулевым или когда векторы v и w ортогональны. Для скалярного произведения справедливы следующие равенства:
и Если векторы
заданы своими координатами в ортонормированном базисе i,j,
т. е.
то формула для скалярного произве- дения с учетом перечисленных свойств записывается
Для скалярного произведения векторов и справедливо соотношение
При общей начальной точке у двух векторов скаляр- ное произведение больше нуля, если угол между векторами острый, и меньше нуля,
если угол тупой.
Векторным произведением называ- ется вектор, такой, что:
• длина вектора равна
• вектор перпендикулярен векто- рам v и т. е. перпендикулярен плоскости этих векторов;

5. Алгоритмы вычислительной геометрии
225
• вектор vxw направлен так, что из конца этого вектора кратчайший по- ворот от v к w виден происходящим против часовой стрелки.
Длина векторного произведения чис- ленно равна площади параллелограмма,
построенного на перемножаемых векторах и
как на сторонах.
Пусть векторы v
заданы своими координатами в базисе i,
j, k
и
Векторное произведение vxw =
+
jxi +
jxj +
jxk +
kxi
kxj
kxk. Вектор-
ные произведения координатных ортов равны: ixi =0, jxj =0,
kxk =0, ixj
jxi=-k,
kxj
kxi =j и ixk
Формула
имеет вид: vxw
+
+
Её
можно записать в другом, более компактном виде (через опре- делитель):
Раскрывая определитель, мы получаем ту же самую форму- лу. Учитывая наш случай, а именно то, что координаты v и w
векторов равны нулю, получаем
-v
После не- сложных преобразований получаем
Векторное произведение ненулевых векто- ров равно нулю тогда и только тогда, ког- да векторы параллельны.
Пример. Найти площадь треугольника
ОАВ. Очевидно, что его площадь равна по- ловине площади параллелограмма ОАСВ,
а площадь последнего равна модулю век- торного произведения векторов ОА и ОВ.
Находим,
отсюда
Отметим, что значение
имеет
другой знак (ориентированная площадь).
Рассмотрим процедуры работы с векторами в декартовой си- стеме координат. Тип данных для описания векторов имеет
вид: Type
(Record x, у: Real;End)
Procedure
a, b: TVecCart; Var c:
TVecCart) ;
двух векторов в декартовой
системе
*}

Алгоритмы вычислительной геометрии
Begin
End;
Аналогично пишутся и процедуры вычисления разности двух векторов SubVecCart, умножения вектора на число
VecCart, а также функции нахождения скалярного произведе- ния и векторного произведения VectMulCart векто- ров в декартовой системе координат. Например:
Function SkMulCart (Const a, b: TVecCart): Real;
{* Скалярное
*}
Begin
=a .
x+a .
End;
Вектор v можно задать в полярной системе координат через его длину (модуль) v и угол а относительно оси X. Координаты полярной системы координат и прямоугольной декарто- вой
) связаны соотношениями: и
Тип данных для описания век- тора в полярной системе координат имеет вид Type TVecPol=Re-
cord rst, angle:
Операции перевода из одной системы координат в другую реализуются с помощью следующих процедур и функций. Фун- кция определения угла используется при переводе в полярную систему координат.
Function
x, у: Real): Real;
{ *Возвращает угол от 0 до
(в радианах) . *}
Var rs, с: Real;
Begin
+
расстояние от точки (0,0) до (х,у) . Можно
воспользоваться функцией Dist.*}
If RealEq(rs, 0) Then
Else Begin
If
0) Then c:=Pi/2
Else c:=ArcTan (Sqrt
/c);
If RealLess (c, 0) Then c:=Pi+c;
If RealLess
0) Then
GetAngle:=c;
End;
End;

5. Алгоритмы вычислительной геометрии 227
Procedure
a:
Var b:
TVecPol);{*Перевод из декартовой системы
координат в полярную. *}
Begin
+
:=GetAngle (a
End;
Procedure PolToCart (Const
TVecPol; Var b: TVecCart);
{*Перевод из полярной системы координат
в декартовую. *}
Begin
End;
5.2. Прямая линия и отрезок прямой
Прямая линия на плоскости, проходящая через две точки и
определяется следующим линейным уравнением от двух перемен- ных:
После
преобразований получаем: -(w —v )*x
+
или, после соответствующих обозначе- ний:
где A=v.y-w.y,
Параметры прямой линии описываются с щего типа данных: Type
А, В, С:
Procedure Point2ToLine (Const v, w: TPoint; Var L:
Thine) ; {*Определение уравнения прямой
координатам двух точек. *}
Begin
L.A:= v.y -
L.B:= w.x -v.x;
L.C:=-(v.x*L.A + v.y*L.B);
End;
Если прямые заданы с помощью уравнений и
то точка их пересечения, в случае ее суще- ствования, определяется по формулам
(С,
обычным решением системы двух уравнений с двумя неизвест- ными. Функция CrossLine определяет существование точки пе-

Алгоритмы вычислительной геометрии
ресечения (с учетом тех погрешностей, которые определяются введенной точностью вычислений), а в процедуре Line2ToPoint
вычисляются координаты точки пересечения.
Function
TLine) : Boolean;
существование точки пересечения
двух прямых. Значение функции равно True,
если точка есть, и False, если прямые
параллельны. *}
Var st: Real;
Begin
st:=Ll.A*L2.B-L2.A*Ll.B;
RealEq
0) ;
End;
Procedure
TLine; Var P:
координат точки
пересечения двух линий. *}
Var st: Real;
Begin
End;
Координаты точек отрезка можно задать двумя параметри- ческими уравнениями от одной независимой переменной t:
При точка (х,у) лежит на отрезке, а при или t>l
вне отрезка на прямой линии, продолжающей отрезок.
Для проверки принадлежности точки Р отрезку необходимо выполнение равенства в уравнении и принадлежность координаты, например, х точки Р интервалу,
определяемому координатами х концов отрезков.
Function
А, В, Р: TPoint): Boolean;
{*Проверка принадлежности точки Р отрезку АВ. *}
Begin
В) Then
(A, P)
А и В совпадают, результат
определяется совпадением точек А и Р.*}
Else
*
(Р.х-А.х))
And ( (RealMoreEq(P.x,
And RealMoreEq
Or

5. Алгоритмы вычислительной геометрии 229
And
End;
Измените функцию для случая, когда отрезок описывается параметрическими уравнениями.
Процедура, с помощью которой определяются координаты точки пересечения двух отрезков, пишется на основе ранее приведенных процедур построения прямой по двум точкам и нахождения точки пересечения прямых (не утверждается то,
что точка пересечения принадлежит отрезкам).
Procedure
fL, fR, sL, sR:
TPoint; Var
TPoint);{*Если точки пересечения
не существует, то значение rs равно
*}
Var
L2: TLine;
Begin
Point2ToLine (fL, fR,
Point2ToLine
sR, L2);
If CrossLine (L1,L2) Then Line2ToPoint
rs)
Else rs:=ZeroPnt;
End;
Примечание
Процедуру следует доработать в том случае, если точка пересече- ния прямых совпадает с точкой (0,0).
Пусть два отрезка находятся на одной прямой. Требуется определить их взаимное расположение.
Function
(Const fL, fR, sL, sR:
Tpoint): Byte; {*0трезки находятся на одной
прямой, проверка их взаимного
Результат равен
если отрезки пересекаются
в одной точке, 1 — не имеют пересечения и 2 —
есть пересечение более чем в одной точке. *}
Var
,Maxs : Real;
Begin
(fR,ZeroPnt));
(fR,ZeroPnt));
If RealEq(Minf,Maxs) Or RealEq
Mins) Then
Else If RealMore
Or RealMore
,Maxs)
Then
Else
End;

230 5. Алгоритмы вычислительной геометрии
Даны два отрезка на плоскости, заданные координатами сво-
их концов. Определить их взаимное расположение (до написа-
ния функции попробуйте прорисовать все возможные случаи).
Function
fL, fR, sL, sR: Tpoint):
Byte; {* Результат равен О, если отрезки пересекаются
в одной точке и лежат на одной прямой, 1 - не имеют
пересечения и лежат на одной прямой, 2 - отрезки ле-
жат на одной прямой и есть пересечение более чем в
одной точке, 3 - отрезки лежат на параллельных пря-
мых, 4 - отрезки не лежат на одной прямой и не имеют
точки пересечения, 5 - отрезки не лежат на одной пря-
мой и пересекаются на концах
6 - отрезки не
лежат на одной прямой, точка пересечения принадлежит
одному из отрезков и является концом другого отрезка,
7 - отрезки не лежат на одной прямой и пересекаются в
одной точке, не совпадающей ни с одним концом отрез-
ков . * }
Var
Begin
Point2ToLine (fL, fR,
Point2ToLine (sL, sR, L2);
If CrossLine
Then Begin
rs)
If EqPoint (rs,fL) Or
Or EqPoint
(rs,sL) Or EqPoint
Then
Else If AtSegm(fL,fR,rs) And
Then
7
Else If
Or AtSegm
Then
Else
End
Else If
And Not
(EqPoint (L1.C,L2.C))
Then
Else
SegmLineCross ( fL, fR,
sL, sR);
End;
Задачу о пересечении отрезков на плоскости можно (естест- венно) решать по-другому. На рисунке показаны два отрезка.
Найдем ряд векторных произведений, они показаны на следую- щих четырех рисунках.

5. Алгоритмы вычислительной геометрии
231
Рассмотрим произведения длин
Очевидно, что если и
то отрезки пе- ресекаются (в произведениях бе- рутся длины векторов
При или от- резки не пересекаются. Рассмот- рим варианты, при которых одна из длин равна нулю. Если и
то третья точка лежит на первом отрезке. При и аналогичных условиях чет- вертая точка лежит на первом от- резке,
— первая на втором отрезке и при
— вторая точ- ка на втором отрезке. Особый слу- чай, когда
Отрезки расположены на одной прямой, необходимы дополнитель- ные проверки для выяснения того,
перекрываются они или нет. Все ли особые случаи рассмотрены?
Определите значения векторных произведений при совпадении ка- ких-либо двух точек, например 2-й и 3-й.
Разработайте процедуру определения взаимного расположе- ния двух отрезков на плоскости с использованием рассмотрен- ных векторных произведений.
Еще один вариант решения задачи о пересечении отрезков возможен при использовании параметрической формы записи уравнения прямой. Отрезки заданы координатами своих кон- цов:

и
-
Уравнения имеют вид:
где и
где
В точке пересечения, при её суще- ствовании выполняются равенства:

232 5. Алгоритмы вычислительной геометрии
=
Есть система двух уравнений с двумя неизвестными и
Если существует единственное решение и то отрез- ки пересекаются. Если одно из значений и равно 0 или 1, а второе принадлежит [0,1], то отрезки пересекаются в одной из вершин, в остальных случаях отрезки не пересекаются. Разра- ботка соответствующей процедуры — ваша задача.
Нормальным вектором (п) к прямой L
назы- вают всякий ненулевой вектор, перпендикулярный этой пря- мой. Известно, что координаты векто- ра определяются значениями и в
уравнении линии L -
Для того, чтобы найти уравнение прямой на плоскости L, проходящей через за- данную точку перпендикулярно заданному направлению не- обходимо раскрыть скалярное произведение га)=0. Оно равно
Procedure
n: TLine; Const P: Tpoint;
Var L: TLine); {*Линия, перпендикулярная п,
проходящая через точку Р.*}
Begin
L.A:=n.B;
L.C:=-L.A*P.X-L.B*P.Y
End;
Расстояние от точки до прямой L вычисляется по формуле:
Function DistPointToLine (Const P: TPoint; Const L:
TLine): Real;{*Расстояние от точки до прямой. *}
End;
5.3. Треугольник
Даны три отрезка а, Ъ, с. Для существования треугольника с такими длинами сторон требуется одновременное выполнение условий и

5. Алгоритмы вычислительной геометрии 233
Function
a, b,
Real): Boolean;
существования треугольника
со сторонами а,
с.*}
Begin
(a+b, c) And RealMore (a+c, b)
And
a);
End;
Площадь треугольника. Если известны длины сторон треу- гольника, то для вычисления площади треугольника обычно используется формула Герона S=Sqrt(p*(p-a)*(p-b)*(p-c)),
где
Function
Var
Begin
p:
(a+b+c)/2;
(p* (p-a) * (p-b) * (p-c) ) ;
End;
Возможно использование и других формул:
S =
= (a*b*sin(C))/2 =
=
где большими буквами обозначены углы против соответствую- щих сторон.
Гораздо интереснее второй способ вычисления площади треу- гольника — через векторное произведение. Длина вектора дает удвоенную площадь треугольника, построенного на этих векто- рах. Пусть даны три точки на плоскости, определяющие вершины треугольника. Совместим начало координат с первой точкой. Векторное произведение рав-
1
-х,
-у, О
- х,
-у, О
. Вычисление длины вектора равносиль- но раскрытию определителя
1
(раскрываем по первой строке).
Function
рЗ: TPoint) :
Real; {*Вычисление ориентированной площади
*}
Begin
SquareTrian :=
x* (p2 . y-рЗ
. у (р2 . x-рЗ . x)
+ (p2.x*p3.y-p3.x*p2.y) ) /2;
End;

234 5. Алгоритмы вычислительной геометрии
Пример. Вычислим удвоенную пло- щадь треугольника, изображенного на рисунке.
2
Значение определителя -1 -1 1 -2
равно 9. Значение определителя
2
(-1,-1)
(2,2)
(1,-2)
1 - 2 1 равно —9. Отличие: в первом случае угол считался
-1 -1
против часовой стрелки, во втором — по часовой стрелке.
Еще один пример. Определитель
0 0 1
(-2,3)
-2 3
V
.(3,2)
равен 10, а определитель
2
3
(4,-1)
равен 15. Вывод: при обходе против часовой стрел- ки получаем положительные величины, а при обходе по часо- вой стрелке — отрицательные значения.
Замечательные линии и точки в треугольнике
Высоту треугольника, опущенную на сторону а, обозначим через
Через три стороны она вы- ражается формулой
где
Function GetHeight (Const a, b, с: Real):
длины высоты, проведенной
из вершины, противоположной стороне треугольника
с длиной а. *}
Var p:
Begin
/2;
GetHeight
(p* (p-a) * (p-b) * (p-c) )
End;
Медианы треугольника пересекаются в одной точке (всегда внутри треугольника), являющейся центром тяжести треугольни- ка. Эта точка делит каждую медиану в отношении 2:1, считая от

5. Алгоритмы вычислительной геометрии
235
вершины. Медиану на сторону а обозначим че- рез
Через три стороны треугольника она выражается формулой
Function
a, b, c:
Real): Real;
длины
медианы, проведенной из вершины,
противоположной стороне треугольника с длиной
Begin
End;
Три биссектрисы треугольника пересека- ются в одной точке (всегда внутри треуголь- ника), являющейся центром вписанного кру- га. Его радиус вычисляется по формуле
Биссектрису к стороне а обозначим через ее длина выража- ется формулой
fi
a
=2*SQRT(b*c*p*(p-a))/(b+c), где р — полупериметр.
Function
a, b, с: Real): Real;
{*Вычисление радиуса окружности, вписанной
в треугольник с длинами сторон а,
с.*}
Var p: Real;
Begin
p: (a+b+c) /2;
GetRadlns :=Sqrt ( (p-a) * (p-b) * (p-c) /p) ;
End;
Function
a, b, c: Real): Real;
{*Вычисление длины биссектрисы, проведенной
из вершины, противоположной стороне треугольника
с длиной а . *}
Var
Real;
Begin
/2;
GetBis :=2*Sqrt
(p-a)) / (b+c) ;
End;
Три перпендикуляра к сторонам треу- гольника, проведенные через их середи- ны, пересекаются в одной точке, служа- щей центром описанного круга. В
тупоугольном треугольнике эта точка ле- жит вне треугольника, в остроуголь-

236 5. Алгоритмы вычислительной геометрии
ном — внутри, в прямоугольном — на середине гипотенузы.
Его радиус вычисляется по формуле
В равнобедренном
треугольнике высота, медиана и биссектриса, опущенные на основание, а также перпендикуляр, проведенный через середи- ну основания, совпадают друг с другом; в равностороннем то же имеет место для всех трех сторон. В остальных случаях ни одна из упомянутых линий не совпадает с другой. Центр тяже- сти, центр вписанного круга и центр описанного круга совпада- ют друг с другом только в равностороннем треугольнике.
Function
a, b, с: Real): Real;
радиуса окружности, описанной около
треугольника с длинами сторон а,
с.*}
Var p: Real;
Begin
/2;
(4*Sqrt (p* (p-a) *
* (p-c) ) ) ;
End;
5.4. Многоугольник
Многоугольник назо- вем простым, если ника- кая пара непоследовате- льных его ребер не имеет общих точек. Требуется определить, является ли заданный многоугольник простым. Для решения этой задачи у нас разрабо- тан аппарат, ибо суть решения в определении взаимного распо- ложения сторон многоугольника. Если нет ни одного пересече- ния сторон, включая случай их частичного наложения, то многоугольник простой. Запрещенные ситуации пересечения сторон многоугольника показаны на рисунке (цифрами обозна- чены концы отрезков, соответственно первого и второго).
Function
(Const
Of
int;Const
{*Проверка простоты много-
угольника . Значение функции равно False, если много-
угольник не является простым, и True, если он
Точки в массиве А заданы в порядке обхода по часовой
или против часовой стрелки.
что если от-
резки лежат на одной прямой и пересекаются в одной точ-
то это один отрезок. *}

5. Алгоритмы вычислительной геометрии 237
Var i , j : Integer;
Begin
pp:=True;
While (i<=N-l) And pp Do Begin
While (j<=N) And pp Do Begin
Case
(A[i] ,A[i+l] ,A[j] ,A[
Mod
N])
проверки взаимного расположения
двух отрезков описана ранее. *}
0,2,6,7: pp:=False;
End;
(j) ;
End;
Inc(i) ;
End;
End;
Задача. Дана точка р и про- стой iV-угольник Q. Определить,
принадлежит ли точка р внут- ренней области простого

льника включая его стороны.
Проведем через точку р пря- мую L, параллельную оси X.
Если L не пересекает то р не принадлежит она внешняя по отношению к Q. Найдем количество пересечений (w) луча,
выходящего из точки р влево или вправо. Точка р лежит внут- ри Q тогда и только тогда, когда w нечетно. Это общий (идеаль- ный) случай. В этой, как и в любой геометрической задаче, есть частные случаи. На рисунке для первой точки все хорошо, она внешняя, количество пересечений четно (считаем вправо). Для второй и третьей точек ситуация чуть хуже — на прямой L ле- жит одна из сторон многоугольника; прямая L проходит через вершину многоугольника. Вырожденные случаи. Лучше повер- нуть чуть-чуть прямую L против часовой стрелки, что устранит вырожденность и позволит считать по схеме, приведенной ниже.
Function
A: Array Of TPoint;
Const N: Word; Const P: TPoint) : Boolean;
принадлежности точки многоугольнику
(включая стороны) . * j

238
5. Алгоритмы вычислительной геометрии
Var i,
sc: Integer;
rg: TPoint;
nx: Real;
Begin
sc:=0; IncludPoint:=True;
For i:=0 To
Do Begin
каждой стороны
многоугольника находим координату х точки
пересечения с горизонтальным лучом. *}
nxt:=(i+l) Mod N;
If AtSegm(A[i] ,
, P) Then
*Проверка
принадлежности точки Р отрезку
(A[i]
.*}
lf:=A[i]; rg:=A[i];
If
(A[i]
A[nxt]
Then rg:=A[nxt]
Else. lf:=A[nxt];
If
And RealLessEq
(A[i].y, rg.y) Then Begin
{*Вычисление координаты х
точки пересечения стороны многоугольника
с прямой, параллельной оси X. Для решения
задачи достаточно в уравнение
* (y-vy) = (wy-Vy) *
подставить
координаты соответствующих точек, раскрыть
скобки и сократить подобные члены. *}
If RealMore (nx,
Then Inc(sc);
End;
End;
End;
Задача. Вычислить площадь простого плоского многоуголь- ника. Метод. Соединяем начало координат отрезками с верши- нами многоугольника. Последовательно вычисляем ориентиро- ванные площади треугольников. В результате получим площадь нашего многоугольника.
Рассмотрим задачу на примере. Уд- военная площадь прямоугольного тре- угольника вычисляется по формуле
— стороны треугольника, об- разующие прямой угол), а трапеции —
где а, Ъ — длины оснований,
h — высота. Пусть наш многоуголь- ник является четырехугольником

5. Алгоритмы вычислительной геометрии
239
Вычислим площадь треугольников, пока- занных на рисунках:
Мы могли бы это же самое сделать с помощью векторных произведений, рассмотренных выше (эта формула уже получе- на ранее), но пусть будет так — другой способ.
После суммирования и группировки получаем:
Убедитесь в правильности наших суждений на следующем примере. Пло- щадь многоугольника равна 3,5. По нашим формулам
+2*(2-3)+2*(2-3)+1*(1-2)=7.
После этих рассуждений и примеров можно написать функцию вычисления площади простого мно- гоугольника.
Function
A: Array Of TPoint; Const N:
Word):
Ориентированная площадь многоугольника
из N точек. *}
Var
Word;
Real;
Begin
If N<3 Then
Else Begin
For i:=l To N-2 Do sc:
. x*
(A[i+1] .y-A[i-l]
;
End;
End;

240
Алгоритмы вычислительной геометрии
Задача. Дан многоугольник. Определить, является ли он
выпуклым. Многоугольник выпуклый, если все диагонали ле-
жат внутри него. Сумма внутренних углов в выпуклом много-
угольнике равна
где N — число сторон многоуголь-
ника. Решить задачу определения выпуклости можно и
по-другому. Все треугольники, образованные тройками сосед-
них вершин в порядке их обхода, имеют одну ориентацию. При
этом следует учесть тот факт, что нахождение тройки вершин
на одной прямой не нару-
шает факта выпуклости.
Первые два многоуголь-
ника на рисунке выпук-
лые, третий, независимо
от направления обхода,
не является выпуклым.
Function
A: Array Of TPoint;
Const N: Word):
выпуклости много-
угольника, значение функции равно True, если многоуго-
льник
*}
Var bn,
Byte;
i:
Real;
Begin
If N>3 Then Begin
For i:=0 To
Do Begin
rp:=SquareTrian (A[
Mod N] , A[i], A[(i+1)
Mod N]) ;
площадь
треугольника, построенного по трем
соседним вершинам многоугольника . *}
If
0) Then
находятся
на одной прямой. *}
Else If RealLess
0) Then
Else
If
Then
Else If
And
Then
многоугольника лежат не на одной прямой,
ориентация треугольников не совпадает -
многоугольник не выпуклый. *}
End;
End;
End;

Алгоритмы вычислительной геометрии 241
5.5. Выпуклая оболочка
На плоскости задано множество S, содержащее N точек.
Требуется построить их выпуклую оболочку.
Алгоритм Грэхема. Идея.
Тройки последовательных то- чек проверяются в порядке обхода против часовой стрел- ки на предмет того, образуют ли они угол, больший равный
Если угол лыне или равен то считают,
что образуют «правый поворот», иначе они образуют
«левый поворот».
Логика:
найти внутреннюю точку t;
• используя t как начало координат, отсортировать точки множества по неубыванию в соответствий с полярным углом и расстоянием от
• выполнить обход точек, исключая точки типа
(образую- щие «правый поворот»).
Логику можно упростить. Можно находить не внутреннюю точку, а самую левую и верхнюю. Она заведомо принадлежит выпуклой оболочке. При этом значения углов вычисляются от- носительно
Известно, что сортировка N элементов может быть выполне- на за время O(N*logN) (методы Хоара, слияния, пирамидальной сортировки). Это самая трудоемкая (по времени) часть алгорит- ма. Обход может быть выполнен за время, пропорциональное N.
Значит, выпуклую оболочку можно построить за время, пропор- циональное N*logN.
Опишем структуры данных.
Var
Of TPoint; { *Координаты точек. *}
N:
точек.*}
M:
точек в выпуклой
*}
Of
точек.
В процедуре типа
необходимо
выполнить следующее присвоение: For
i:=l
N Do ls[i] :=i.*}
Идеи всех алгоритмов этого параграфа взяты из прекрасной книги Ф. Препа- рата и М Шеймоса [24].

242 5. Алгоритмы вычислительной геометрии
bb:
Of Boolean;{*Признак
принадлежности точки выпуклой
оболочке, начальное присвоение -
True), все
точки принадлежат выпуклой
*}
Rd:
Of
углов. *}
Фрагмент вывода результата решения задачи имеет вид:
(M) ;
For i:=l
N Do If bb[i] Then Write
[i] ,
') ;
Сейчас мы знаем, к чему стремиться, поэтому перейдем к
основной процедуре.
Procedure Solve;
Var
TPoint;
i , j , r : Integer;
Begin
что самой левой верхней
точкой множества по значению координаты X
является первая точка. *}
For i:=2
N Do {*Поиск точки, заведомо
принадлежащей выпуклой
*}
If RealMore(A[j]
A[i].x)
Or (RealEq(A[i]
A[j].x) And RealMore (A[i]
A[j]
Then j:=i;
;A[1] :
: =aa;
точки,
на первом месте в массиве записана точка,
принадлежащая выпуклой оболочке. *}
значения синусов углов, углы принадлежат
первой
четвертой четвертям, если брать их с противо-
положным знаком и затем отсортировать в порядке неубы-
вания, то выпуклая оболочка будет построена обходом
против часовой стрелки. *}
For i:=2
N Do Begin
.
.x-A[l] .
=A
.y-A[l]
+
End;
(2, N)
Обычная сортировка, например
Следует только не забывать,
что при перестановке ключей - Rd[i]
необходимо переставлять и соответствующие

5. Алгоритмы вычислительной геометрии 243
элементы в массивах
и А (процедура не
приводится). *}
{*Осталось выполнить обход множества точек. *}
If N>3 Then Rounds;{*Обход. *}
End;
И наконец, последняя из рассматриваемых процедур.
Procedure Rounds;
Var
rg: TPoint;
rgi: Integer;
r: Real;
Function
Begin
Integer):
Dec(ldi) ;
While
Predd.
End;
Not(bb[ldi]) Do ldi:
Mod N + 1;
Begin
M:=N;{*Количество точек в выпуклой оболочке.*}
lf:=A[2];
mdi
While rgi<>2 Do Begin
md,
Ориентированная
площадь треугольника.*)
If
0)) Then
точку с номером mdi из выпуклой оболочки. *}
Определяем номер предыдущей
точки. *}
lf:=A[lfi];
Dec (M) ;
End
Else Begin
к следующей точке. *)
Mod N +
md:=rg; rg:=A[rgi];
End;
End;
End;
Рассмотрим другой способ построения выпуклой оболочки —
алгоритм Джарвиса. Он основан на следующем утверждении.
Отрезок L, определяемый двумя точками, является ребром вы- пуклой оболочки тогда и только тогда, когда все другие точки

244
Алгоритмы вычислительной геометрии множества S лежат на L или с одной стороны от него. Из этого утверждения «вытекает» следующая логика. N точек определя- ют т. е. порядка O(N
2
) отрезков. Для каждого из этих отрез- ков за линейное время можно определить положение остальных
N-2 точек относительно него. Таким образом, за время, пропор- циональное можно найти все пары точек, определяющих ребра выпуклой оболочки. Затем эти точки следует расположить в порядке последовательных вершин оболочки. Джарвис заме- тил, что данную идею можно улучшить, если учесть следующий факт. Если установлено, что отрезок является ребром обо- лочки, то должно существовать другое ребро с концом в точке принадле- жащее выпуклой оболочке. Уточнение этого факта приводит к алгоритму с временем работы, пропорциональным
Рисунок, приводимый ниже,
служит иллюстрацией данной идеи.
Структуры данных:
ConstMaxN=100;
Var A: Array
Of
{ *Массив
с координатами точек плоскости. *}
N:
точек.*}
Of
точек,
принадлежащих выпуклой оболочке,
в процедуре типа
(инициализации
и ввода исходных данных) необходим
оператор
M:
точек в выпуклой
оболочке. *}
Найдем номер самой левой нижней точки. Она принадлежит выпуклой оболочке. Задача эквивалентна поиску номера мини- мального элемента в массиве.
Function GetLeft: Integer;
Var i,
Integer;
Begin
lf:=l;
For i :=2 To N Do
If RealLess
A[lf].x) Or
A[lf].x) And RealLess (A[ ].
A[i].y)) Then
End;

5. Алгоритмы вычислительной геометрии 245
Основная процедура.
Procedure Solve;
Var
TPoint;
Begin
точек в выпуклой оболочке. *}
самую левую и нижнюю
точку. *}
While
Or
[1]) Do Begin { *Пока не
вернулись к первой точке.*}
Inc(M);
точка выпуклой
оболочки. *}
M>1 Then
точка
выпуклой оболочки. *}
Else Begin
End;
{*Если рассматриваемая точка является
первой точкой выпуклой оболочки, то
искусственно уменьшаем на единицу ординату
у первой точки и считаем ее предыдущей
точкой оболочки. *}
следующей
точки выпуклой
параметрами
функции являются координаты двух предыдущих
точек оболочки. *}
End;
Перенесли, как обычно, всю «тяжесть» ло- гики на следующую часть — функцию GetNext
(метод последовательного уточнения, техноло- гия «сверху — вниз» в действии). Рассмотрим,
как осуществляется поиск следующей точки выпуклой оболочки. Требуется найти точку множества, такую, что угол, образованный лу- чами (A[i],gn) и (gn,pr), имеет минимальное значение. Если таких точек несколько, то выбирается точка,
находящаяся на максимальном расстоянии от точки gn. Таким образом, мы опять возвращаемся к задаче поиска минимально- го элемента в массиве.
Function GetNext (Const
gn: TPoint): Integer;
Var i, fn: Integer;
rsx,
Real;
Begin

5. Алгоритмы вычислительной геометрии
явных констант в «теле»
программного кода - дурной тон, но простит
нас читатель за эту маленькую слабость. *}
For i:=l
N Do Begin
(pr,
A[i]);(*Найдем
*}
nw) Then Begin
Else If
Then Begin
nw:=Dist(gn, A[i]);
If RealLess (rsx, nw) Then Begin
rsx:=nw;End;
End;
End;
End;
Осталось уточнить функцию вычисления угла по трем точ- кам. Она отличается от ранее рассмотренной функции, поэтому необходимо сказать несколько слов. Пусть и
— две пря- мые, заданные уравнениями соответственно. Угол а между прямы- ми и
равен углу между нормаль- ными векторами и
этих прямых. Отсюда следует, что
Function
А, В, С: TPoint): Real;
Begin
If RealEq(Dist (C,B) , 0) Then GetAngle:=-11
Else
= ( (B.x-A.x) * (C.x-B.x) + (B.y-A.y) *
(C.y-B.y))/(Dist (A,B)
End;
Метод «разделяй и властвуй» при построении выпуклой обо- лочки, основан, как обычно для этого типа алгоритмов, на прин- ципе сбалансированности, суть которого в том, что вычислите- льная задача разбивается на подзадачи примерно одинаковой размерности. Они решаются, и затем результаты объединяются.
Метод эффективен, если время, требуемое на объединение резу- льтатов, незначительно. Суть данного алгоритма построения выпуклой оболочки. Множество разделяется на два подмно-

5. Алгоритмы вычислительной геометрии
247
и примерно равной мощности. Для каждого из подмножеств строится выпуклая оболочка. Если время объеди- нения оболочек пропорционально количеству вершин в них —
то временная зависимость имеет вид:
T(N)<2T(N/2)+0(N).
Итак, разбиваем множест- во из N точек на два под- множества, каждое из кото- рых будет содержать одну из двух ломаных, соединение которых даст многоугольник выпуклой оболочки. Найдем точки и
имеющие, соот- ветственно, наименьшую и наибольшую абсциссы. Про- ведем через них прямую L,
тем самым получим разбие- ние множества точек на два подмножества
(выше или на прямой и
(ниже прямой L). Определим точку h, для кото- рой треугольник имеет наибольшую площадь среди всех треугольников
Если точек имеется более одной,
то выбирается та из них, для которой угол
1   ...   12   13   14   15   16   17   18   19   ...   26


написать администратору сайта