Лабораторная работа № 7

Стеки + Графика в Delphi

Теоретическая часть

Стек (Stack) – это линейный список, в котором все включения и исключения (и обычно всякий доступ) производятся с одного конца списка. Элемент, вставленный в стек, делает недоступными все элементы, вставленные до него. Удаление элемента делает доступным элемент, вставленный предпоследним. Единственно доступным элементом в стеке является тот, который вставлен последним. Процесс помещения объектов в стек называется проталкиванием (pushing), а процесс извлечения верхнего элемента из стека называется выталкиванием (popping). Учитывая характер дисциплины обслуживания списка, стек называют списком типа LIFO ("last-in-first-out" - "последним-пришел первым-вышел"). Графически стеки чаще всего изображаются как вертикальные объекты: элементы располагаются снизу вверх, так что наверху оказывается элемент, вставленный последним.

Для стека определены следующие основные функции:

• Push( x, S); эта функция проталкивает элемент x в стек S.

• Pop(S); эта функция выталкивает элемент, находящийся на вершине стека S, и возвращает на него ссылку. Если стек пустой, то функция Pop возвращает nil.

• Top(S) или Peek(S); эта функция возвращает ссылку на элемент, находящийся на вершине стека S, не удаляя его из стека. Если стек пустой, то функция Top (или Peek)возвращает nil.

В модуле Contnrs определены два класса, которые моделируют работу стека: TStack и TObjectStack. Различие между ними заключается в том, что TStack это стек указателей на объекты, а TObjectStack это стек самих объектов.

Класс TObjectStack поддерживает следующие методы:

constructor Create; // Создает объект-стек

function Push(AObject: TObject): TObject; // Вталкивает объект в стек и возвращает ссылку на него.

function Pop: TObject;  // Выталкивает объект из стека и возвращает ссылку на на него.

function Peek: TObject; // Возвращает ссылку на верхний объект стека.

function Count: Integer; // Возвращает количество объектов в стеке.

В лабораторной работе предлагается использовать класс TObjectStack для решения задачи из области вычислительной геометрии, которая называется «Задача о выпуклой оболочки конечного множества точек».

Построение выпуклой оболочки

Выпуклой оболочкой (convex hull) множества точек Q называется наименьший выпуклый многоугольник P, такой что каждая точка из Q находится либо на границе многоугольника P, либо в его внутренней области. Обозначим выпуклую оболочку множества Q как CH (Q). Интуитивно можно представлять каждую точку множества Q в виде торчащего из доски гвоздя; тогда выпуклая оболочка будет иметь форму, полученную в результате наматывания на гвозди тугой резиновой нити. Пример множества точек и их выпуклой оболочки приведен на рис. 1.

Рис. 1. Множество точек Q = {p₀, p₁, ... , p₁₂} и их выпуклая оболочка CH (Q)

Наиболее известны два алгоритма, позволяющие построить выпуклую оболочку множества, состоящего из точек. Оба алгоритма выводят вершины выпуклой оболочки в порядке обхода против часовой стрелки. Время работы первого из них, известного как сканирование по Грэхему, равно O(nlgn). Второй алгоритм, который называется обходом по Джарвису, выполняется в течение времени O(nh), где h - количество вершин выпуклой оболочки. Как видно из рис. 1, каждая вершина CH (Q) - это точка из множества Q. Это свойство используется в обоих алгоритмах. В них принимается решение, какие точки из множества Q выступают в роли вершин выпуклой оболочки, а какие следует отбросить. И при сканировании по Грэхему, и при обходе по Джарвису используется метод, который называется "выметанием по кругу". Вершины обрабатываются в порядке возрастания их полярных углов, которые они образуют с некоторой базисной вершиной.

Сканирование по Грэхему

В методе сканирования по Грэхему (Graham's scan) задача о выпуклой оболочке решается с помощью стека S, сформированного из точек-кандидатов. Все точки входного множества Q заносятся в стек, а потом точки, не являющиеся вершинами CH (Q), со временем удаляются из него. По завершении работы алгоритма в стеке S остаются только вершины оболочки CH(Q), в порядке их обхода против часовой стрелки.

В качестве входных данных процедуры GRAHAM_SCAN выступает множество точек Q, где |Q| >= 3. В ней вызывается функция TOP (S), которая возвращает точку, находящуюся на вершине стека S, не изменяя при этом его содержимое. Кроме того, используется также функция NEXT_TO_TOP (S), которая возвращает точку, расположенную в стеке S на одну позицию ниже от верхней точки; стек S при этом не изменяется. В литературе по вычислительной геометрии строго доказывается, что стек S, возвращаемый процедурой GRAHAM_SCAN, содержит только вершины CH (Q), причем расположенные в порядке обхода против часовой стрелки, если просматривать их в стеке снизу вверх.

GRAHAM_SCAN (Q)

1. Пусть p₀ - точка из множества Q с минимальной координатой y или самая левая из таких точек при наличии совпадений.

2. Пусть <p₁, p₂, …, p_m> - остальные точки множества Q, отсортированные в порядке возрастания полярного угла, измеряемого против часовой стрелки относительно точки p₀ (если полярные углы нескольких точек совпадают, то из множества удаляются все эти точки, кроме одной, самой дальней от точки p₀).

3. PUSH (p₀, S).

4. PUSH (p_l, S).

5. PUSH (p₂, S).

6. for i := 3 to m do

7. while угол, образованный точками NEXT_TO_TOP (S), ТOР (S) и p_i, образует не левый поворот (при движении по ломаной, образованной этими точками, мы движемся прямо или вправо) do

8. POP (S).

9. Конец цикла while

10. PUSH (p_i, S).

11. Конец цикла for

12. return S.

Работа процедуры GRAHAM_SCAN проиллюстрирована на рис. 2.

Рис. 2. Обработка процедурой GRAHAM_SCAN множества точек Q, показанного на рис. 1.

Выпуклая оболочка, содержащаяся на данный момент в стеке S, на каждом этапе показана серым цветом. В строке 1 процедуры выбирается точка p₀ с минимальной координатой у; при наличии нескольких таких точек выбирается крайняя левая. Поскольку во множестве Q отсутствуют точки, расположенные ниже точки p₀, и все другие точки с такой же координатой расположены справа от точки p₀, p₀ - вершина оболочки CH (Q). В строке 2 остальные точки множества Q сортируются в порядке возрастания их полярных углов относительно точки p₀. При этом используется метод сравнения векторных произведений. Если полярные углы двух или нескольких точек относительно точки p₀ совпадают, все такие точки, кроме самой удаленной от точки p₀, являются выпуклыми комбинациями точки p₀ и самой удаленной от нее из числа таких точек, поэтому все они исключаются из рассмотрения. Обозначим через m количество оставшихся точек, отличных от точки p₀. Величина полярного угла каждой из точек множества Q, измеряемого в радианах относительно точки p₀, принадлежит полуоткрытому интервалу [0, ). Поскольку точки отсортированы по величине возрастания их полярных углов, они расположены относительно точки p₀ в порядке обхода против часовой стрелки. Обозначим эту упорядоченную последовательность точек как < p₁, p₂, …, p_m>. Заметим, что точки p₁ и p_m являются вершинами оболочки CH (Q). На рис. 2а изображены точки из рис. 1, последовательно пронумерованные в порядке возрастания полярных углов относительно точки p₀. В остальной части процедуры используется стек S. В строках 3-5 стек инициализируется, и в него заносятся снизу вверх три точки p₀, p₁ и p₂. На рис. 2а показано начальное состояние стека S. В каждой итерации цикла for в строках 6-9 обрабатывается очередная точка подпоследовательности < p₃, p₄, ... , p_m>. Цель этой обработки - сделать так, чтобы в результате в стеке S в порядке размещения снизу вверх содержались вершины оболочки CH ({p₀, p₁, ... , p_i}) в порядке обхода против часовой стрелки. В описанном в строках 7-8 цикле while точки удаляются из стека, если будет обнаружено, что они не являются вершинами выпуклой оболочки. При обходе выпуклой оболочки против часовой стрелки в каждой вершине должен производиться поворот влево. Каждый раз, когда в цикле while встречается вершина, в которой не производится поворот влево, такая вершина выталкивается из стека. (Выполняется именно проверка того, что поворот – не левый, а не проверка того, что поворот правый. Такая проверка исключает наличие развернутого угла в полученной в результате выпуклой оболочке. Развернутых углов быть не должно, поскольку ни одна из вершин выпуклого многоугольника не может быть выпуклой комбинацией других вершин этого многоугольника.) После выталкивания из стека всех вершин, в которых при переходе к точке p_i не производится левый поворот, в стек заносится точка p_i. На рис. 2б-л показано состояние стека S после каждой итерации цикла for. По окончании работы в строке 10 процедуры GRAHAM_SCAN возвращается стек S. На рис. 2м показана полученная выпуклая оболочка.