По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
4. Алгоритмы на графах 219 Разработать программу, которая за возможно меньшее коли- чество ходов расставляет элементы массива по порядку, т. е. в первой строке — от 1 до М, во второй строке — от до и т. д. Указание. Рассмотрим метод поиска системы различных представителей для нашей задачи. Обозначим элементы каж- дой строки нашей таблицы как Считаем, что есть множества (l 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, для кото- рой треугольник Если точек имеется более одной, то выбирается та из них, для которой угол |