По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
Точка 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; |