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

• Название: По вопросам приобретения обращаться
• Анкор: Окулов.Программирование.в.алгоритмах.pdf
• Дата: 26.04.2017
• Размер: 5.46 Mb.
• Имя файла: Окулов.Программирование.в.алгоритмах.pdf
• Тип: Документы; #5718
• страница: 17 из 26

наибольший.
Точка h гарантированно принадлежит выпуклой оболочке.
Действительно, если через точку h провести прямую, паралле- льную L, то выше этой прямой не окажется ни одной точки множества S. Через точки w и h проведем прямую через точки h и — прямую
Для каждой точки множества определяется ее положение относительно этих прямых. Ни одна из точек не находится одновременно слева как от так и от кроме того, все точки, расположенные справа от обеих прямых, являются внутренними точками треугольника
и поэтому могут быть удалены из дальнейшей обработки. Про- цесс продолжается до тех пор, пока слева от строящихся пря- мых типа и
есть точки.
Перейдем к описанию более детального решения.
Const MaxN=100;
Type TSpsk =
Of Integer;
Var A:
.
Of TPoint;
N: Integer;
номера точек, составляющих
выпуклую оболочку, в rs[0] фиксируется
количество точек. *}
Вывод результата очевиден уже в данный момент:

248
Алгоритмы вычислительной геометрии
For
Do Write (rs
' ') ;
Опишем ряд вспомогательных функций и процедур, прежде чем разобрать логику (технология «снизу — вверх»). Нам по- требуется определять взаимное расположение точки и линии на плоскости — функция Get Sign. Значение функции равно О,
если точка находится на линии, плюс единице при нахождении в левой полуплоскости и минус единице — в правой.
Function GetSign (Const L: Thine; Const A: TPoint):
Integer;
Var
Real;
Begin
+ A.y*L.B + L.C;
If RealEq(rs, 0) Then
Else If
(rs, 0) Then GetSign:=l
Else
End
Площадь треугольника координатам трех вершин опреде- ляется точно так же, как и ориентированная площадь — функ- ция
(рассмотрена ранее), только берется ее абсо- лютное значение.
Function
Begin
(A.y-B.y))/2);
End;
А, В
•
Y-C
, C:
•У)
TPoint)
+ B.x*(C
: Real/
+ C.x*
Договоримся, что мы работаем с номерами точек. Координа- ты точек хранятся в массиве А. Пусть имеется некоторое мно- жество точек, их номера в массиве fr. Через две заданные точ- ки
rg) проводится прямая линия
Требуется в массив rs
записать номера тех точек из исходного множества, которые находятся в другой полуплоскости относительно линии L, чем заданная точка
Считаем, что точки, по которым строится линия, должны быть в результирующем множестве. Решение этой задачи обеспечивает следующая процедура.
Procedure SelectPoints
rg:
nn:
fr:
Var rs: TSpsk) ;
Var i,
nw: Integer;
Begin
rs[l]:=lf;

5. Алгоритмы вычислительной геометрии
249
Point2ToLine
, A[rg], L) ;{*Построение линии
по двум точкам, процедура описана ранее. *}
lzn:=GetSign (L,
знак
в которой находится точка
с номером
*}
For
fr[0] Do Begin
A[fr[i]]);
If
Then Begin
End;
End;
Пусть есть множество точек. Их номера хранятся в массиве
Требуется найти номер той точки, которая наиболее уда- лена от двух точек с номерами из первых двух элементов мас- сива. Эта задача решается с помощью следующей функции. На- помним, что в нулевом элементе массива хранится количество точек множества.
Function
ow: TSpsk): Integer;
Var max, nw: Real ;
i,
Begin
rs:=3;
For
To
Do Begin
(nw, max) Or (RealEq(nw,
And
Then Begin
End;
End;
Еще одна очевидная процедура. В исходном множестве то- чек находим номера самых крайних левой и правой, а также формируем первоначальный массив номеров точек. При этом на первое и второе места записываем номера найденных то- чек — они заведомо принадлежат выпуклой оболочке.
Procedure
rg: Integer; Var All:
TSpsk);
Var i, sc: Integer;
Begin
Находим номера точек
с минимальным
и с максимальным (rg)
значениями координаты х, при равных

250 5. Алгоритмы вычислительной геометрии
значениях х выбираются точки с меньшим
значением координаты у. *}
For i:=l
N Do Begin
If
A[rg].x) Or
(RealEq(A[i]
A[rg].x) And RealMore (A [ rg] .
A[i].y)) Then rg:=i;
If RealMore (A[lf]
A[i].x) Or
(RealEq(A[i]
A[lf].x) And RealMore (A
].
A[i]
)Then
End;
For
To N Do
If
And (iorg) Then Begin Inc(sc);
End;
End;
А сейчас одна из ключевых процедур логики. Для множест-
ва точек, описываемых их номерами из массива ow, формиру-
ется множество точек из их выпуклой оболочки.
Procedure
ow: TSpsk; Var
TSpsk);
Var i, nw: Integer;
rg, rssc: TSpsk;
Begin
If ow[0]>2 Then Begin
максимально удаленную
точку от точек ow[l] и ow[2]. *}
SelectPoints (ow [1], nw,
ow,
{*'Определяем множество точек, находящихся
в другой
чем точка с номером
ow[2], относительно прямой, проходящей
через точки с номерами ow[l] и nv/. *}
SelectPoints (nw, ow[2], A[ow[l]], ow, rg) ;
{*Определяем множество точек, находящихся
в другой
чем точка
с номером ow[l] относительно прямой,
проходящей через точки с номерами nw
и ow[2]. *)
GetSpisok
продолжаем
строить выпуклую оболочку для выделенного
множества точек. Если мощность выделенного
множества точек равна 2, то процесс
*)
rssc);

5. Алгоритмы вычислительной геометрии 251
For i:=2
rssc[0] Do
два множества точек.*}
Inc(rs[0],
;
End;
End;
Основная процедура после проделанной работы достаточно
«прозрачна».
Procedure Solve;
Var
rg, i: Integer;
fr,
TSpsk;
TPoint;
Begin
rg, rs);{*Находим крайние
значению координаты х точки исходного
*}
SelectPoints(lf, rg, nw, rs, fr);{*B fr
формируется список номеров точек, лежащих
одну сторону от прямой, проходящей через
точки
и
*}
nw.
у+20 ;
SelectPoints (rg,
nw, rs, frl) ;{*B frl

другую сторону. *}
rs);{*Строим выпуклую оболочку для
множества точек с номерами из
*)
GetSpisok
выпуклую оболочку
для множества точек с номерами из
*}
For i:=2
Do
выпуклые
*}
Inc(rs[0] , fr[0]2) ;
End;
5.6.
о прямоугольниках
1. Дано N
прямоугольников со сторонами, па- раллельными координатным осям. Каждый прямоугольник мо- жет быть частично или пол- ностью перекрыт другими прямоугольниками. Вершины всех прямоугольников имеют целочисленные координаты в пределах [-10000, 10000] и каждый прямоугольник име-
•

252 5. Алгоритмы вычислительной геометрии
ет положительную площадь.
Периметром называется об- щая длина внутренних и внешних границ фигур, полу- ченных путем наложения прямоугольников. Найти зна- чение периметра.
На рисунке показана фигура из 7 прямоугольников. Соот- ветствующие границы полученной фигуры показаны на следу- ющем рисунке.
Пример входного файла:
7 (количество прямоугольников)
-15 0 5 10 (границы прямоугольника — нижняя левая и верх- няя правая)
-5 8 20 25 15 -4 24 14 0 -6 16 4 2 15 10 22 30 10 36 20 34 0 40 16
Ответ: 228.
Рассмотрим более простую задачу. На прямую «набросали»
какое-то количество отрезков. Последние могут пересекаться,
находиться один внутри другого и т. д. Требуется определить количество связных областей, образованных этими отрезками.
На рисунке даны три отрезка
(2, 5), (4, 6) и (8,10). Количест- во связных областей две. Как
8 10
их найти? Используем стан- дартный прием. Записываем в один массив координаты отрезков, в другой признаки начала
(1) и конца отрезков (-1). Сортируем элементы первого массива по неубыванию, одновременно переставляя соответствующие элементы второго массива. После этого осталось считать сумму значений признаков. Если ее текущее значение равно нулю, то выделена очередная связная область.
Вернемся к исходной задаче. Очевидно, что можно считать периметр отдельно, по частям. Например, первоначально его составляющую по оси Y, а затем по оси X. Рассмотрим идею решения на примере (рисунок). Даны четыре прямоугольника.
Считаем составляющую периметра по оси Y. Ось разбивается координатами прямоугольников на следующие участки: (0,1),
(1,2), (2,3), (3,4) и (4,6). Рассматриваем каждый участок, т. е.

5. Алгоритмы вычислительной геометрии
253
4.,
10
определяем прямоуголь- ники (точнее их коорди- наты по X с признаками начала и конца интерва- ла), которые могут дать
«вклад» в периметр. Для первого участка — один прямоугольник, для вто- рого — три, для третье- го — два, для четверто- го — три и
—
один. Выписав для каждого участка координаты X с соответст- вующими признаками, выполняем сортировку и находим коли- чество связных областей. Так, на рисунке для первого сечения
(отмечено цифрой 1) количество связных областей равно 1, а для второго сечения — 2. После этого достаточно длину этого участка умножить на количество связных областей и удвоить результат. Получаем составляющую периметра по оси У на этом участке.
После этих замечаний можно приступить к разбору реше- ния. Как обычно, начинаем со структур данных.
Const
Type
Of
1..2] Of
записи координат и соответствующих
признаков начала и конца отрезков.*}
Var N, i: Integer;
Ay:
хранения координат
*}
Основная программа.
Begin
Assign
'...') /Reset (Input) /Read (N) /
For i:=l To N Do Begin Read (Ax [ i*2-l ] ,
) /Read(Ax[i*2] , Ay[i*2]); End/
Close (Input)/
Assign (Output, '...') /Rewrite (Output) /
Ay) +
End.
Вспомогательную процедуру сортировки любому методу с временной оценкой описывать не будем.

254
Алгоритмы вычислительной геометрии
Procedure
MasSw;
rg: Integer) ;
Begin
End;
Функция
Function GetPerim (Const Ax, Ay: MasPn): Longlnt;
Var i: Integer;
sc: Longlnt;
D: MasSw;
Begin
периметра
одному из
*}
FillChar(D, SizeOf (D) , 0) ;
For i:=l
2*N Do D[i, 1 ]
[i] ; { *Массив
координат
этому
*}
1,
;{*Сортировка . *}
For i:=l
N*2-l Do
1]
координаты не
равны, то вычисляем количество связных
областей на этом сечении - функция GetPr,
умножаем на длину участка и на 2.*}
Ay, D[i, 1]) * (D[i+1, 1] -
D[i, 1]) * 2;
GetPerim:=sc;
End;
Следующий шаг уточнения. Вычисляем количество связных областей на сечении, определяемом значением переменной х.
Function
Ay: MasPn; x: Integer):
Integer;
Var i, b, d, sc: Integer;
nn:
прямоугольников многовато
(до 5000), задействуем «кучу». *}
Begin
New (nn) ;
Ay, x,
sc);{*Определяем
имеющие отношение к
рассматриваемому сечению, их количество
значение переменной sc, а координаты в
массиве
*}
If sc<>0 Then Sort
1, sc);{*Выполняем
сортировку с одновременной перестановкой
признаков начала и конца
*}

5. Алгоритмы вычислительной геометрии 255
хранения суммы значений признаков. *}
If sc>0 Then d:=l Else
For i:=l To
Do Begin
2];
If
And
1]) Then
(d) ;
{*Если текущее значение b равно нулю и
координаты не совпадают, то увеличиваем
счетчик числа связных областей. *}
End;
GetPr:=d;
End;
Последний шаг уточнения логики — определение характе- ристик сечения.
Procedure GetRect
Ay: MasPn; x: Integer;
Var nn: MasSw;Var sc: Integer);
Var i: Integer;
Begin
sc:=0;
For
To N Do
If
And (x
прямоугольник имеет отношение
к сечению, то запоминаем координаты
по соответствующему направлению (они
в массиве
и признаки начала
и конца отрезка. *}
Inc (sc) ;
nn[sc,
1]:=Ay[i*2];
nn[sc,
2]:=-l;
Inc (sc);
End;
End;
2. На плоскости задано прямоугольников со сторонами, параллельными координатным осям (пример на ри- сунке). Координаты вершин прямоугольника (х,у) — вещест- венные числа с точностью до двух знаков после запятой. Напи- сать программу поиска площади фигуры, получающейся в результате объединения прямоугольников.
Продлим все верти- кальные линии до пере- сечения с осью X. Эти линии определяют на оси X множество интер-

256 5. Алгоритмы вычислительной геометрии валов, внутри каждого из кото- рых длина сечения по оси У будет постоянной (рисунок). Поэтому для нахождения площади доста- точно отсортировать точки на оси
X, рассмотреть все сечения и до- бавить к площади <длину интер- вала> * <длину сечения>. Для поиска длины сечения исполь- зуем метод из предыдущей задачи. Началу каждого отрезка присвоим значение признака, равное 1, а его концу —
и от- сортируем точки по значению координаты Y. Считаем сумму значения признаков. Если она не равна нулю, то соответствую- щий интервал «плюсуем» к длине сечения.
Из структур данных приведем только те, которые требует уровень детализации объяснения.
Type
Var PrM:
N:
Res: Real;
Ox, Oy:
1. .MaxN*2] Of Real;
В процедуре инициализации и ввода данных координаты вершин прямоугольника записываются в массиве причем в
(это массив) — координаты пер- вой вершины, а в
— вто- рой. Вершина прямоугольника с меньшими значениями за- писывается в
Кроме того,
значения X запоминаются в мас- сиве Ох.
Основная процедура вычисления площади объединения пря- моугольников выглядит следующим образом.
Procedure Solve;
Var i: Longlnt;
Real;
Begin
(Ox, 1,
неубыванию
значения координаты X прямоугольников.
в силу её очевидности, не
*}
Пример.
4 (количество прямоугольников)
0 10.1 5.2 (координаты нижнего левого и правого верхнего углов)
-3 3 5.36 7 1 6 9 15 8 3 20 8
Ответ.
195.188

5. Алгоритмы вычислительной геометрии 257
- длина сечения, Res - значение
площади объединения прямоугольников.*}
For
N*2 Do Begin
If
Then Res:=Res +
*m) ;
площадь очередного сечения.*}
If (i=l)
Then
,
; { *Определяем новое значение длины
*}
End;
End;
Уточнению подлежит процедура
Procedure
x: Real; Var rs: Real);
Var i, M: LongInt;{*M - количество интервалов
на данном сечении. *}
Begin
переменных процедуры, в частности
For i:=l
N Do {*Формируем массив ординат для
данной координаты х. *}
<Если есть пересечение прямоугольника с прямой,
параллельной оси Y и проходящей через точку х, то
занести координаты Y прямоугольника в рабочий
не забыв при этом сформировать признаки начала и
конца
Количество пересечений - значение
переменной М.>;
If
Then
Else Begin ,] ?
f
<Сортируем
6 8 10 1112 13
границы интервалов
оси Y, переставляя
одновременно соответствующие элементы массива
признаков>;
<Вычисляем новую длину сечения - значение
переменной rs>;{*Так, для примера на рисунке длина-
сечения равна 10.*}
End;
End;
Дальнейшее уточнение логики вынесем на самостоятельную работу.
3. Найти площадь пересечения прямоугольников со сторо- нами, параллельными осям координат.
Входные данные. Число N (количество прямоугольников и
четверок действительных чисел
9 3500

Пример.
3
0 0 10
5 5 15
- 1 . 5 0
Ответ:
10
15
7 8
6
258 5. Алгоритмы вычислительной геометрии
задающих координаты левого нижнего и правого верхнего уг- лов прямоугольника.
Выходные данные. Площадь пересечения (общей части) всех данных прямоугольников, либо выдать, что они не пересекают- ся.
Задача предельно проста. Приведем ее с це- лью «закрыть» тему «Прямоугольники на плос- кости со сторонами, параллельными осям коор- динат, их периметр и площади». Оказывается,
что можно независимо найти область пересече- ния интервалов на прямой отдельно по осям X и
Y. Эти интервалы определяют прямоугольник,
являющийся пересечением заданных прямоугольников.
Const MaxN=1000;
;
Type
L, R: Real; End;
Of Segm;
Var N: Integer;
OnX, OnY:
ObX, ObY: Segm;
Procedure
Begin
<ввод
End;
Function Cross
New:Segm) -.Boolean;
факт пересечения двух
отрезков А и В.*}
Begin
If
Then New.L:=A.L Else
If (A.R-B.R)
Else
End;
Function SolSegm(Const On:
Ob:
Segm):
Определяем область
пересечения интервалов на прямой, если
она
*}
Var i ; Integer;
Begin
;
i:=2;
While
And
Ob, Ob) Do Inc(i);
SolSegm:=i>N;
End;