Главная страница
Навигация по странице:

  • Вывод результата очевиден уже в данный момент

  • 250 5. Алгоритмы вычислительной геометрии

  • А сейчас одна из ключевых процедур логики. Для множест- ва точек, описываемых их номерами из массива ow, формиру- ется множество точек из их выпуклой оболочки.

  • 5. Алгоритмы вычислительной геометрии 251

  • 5. Алгоритмы вычислительной геометрии 253 4., 10

  • Уточнению подлежит процедура

  • Пример. 3 0 0 10 5 5 15 - 1 . 5 0 Ответ: 10 15 7 8 6 258 5. Алгоритмы вычислительной геометрии

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


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    АнкорОкулов.Программирование.в.алгоритмах.pdf
    Дата26.04.2017
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаОкулов.Программирование.в.алгоритмах.pdf
    ТипДокументы
    #5718
    страница17 из 26
    1   ...   13   14   15   16   17   18   19   20   ...   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;

    1   ...   13   14   15   16   17   18   19   20   ...   26


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