В примере, показанном на рис. 6.13, точка p2 является внутренней точкой треугольника. Вершина pi0 является начальной. Эта вершина выбирается среди точек, имеющих наименьшую ординату. Она должна быть самой правой среди этих точек. Вследствие такого выбора начальная вершина будет принадлежать множеству вершин искомого выпуклого многоугольника.
Затем тройки последовательных точек из упорядоченного массива многократно проверяются в порядке обхода против часовой стрелки с целью определить, образуют они или нет угол, больший или равный π. Если внутренний угол pi-1pipi+1 больше или равен π, то говорят, что pi-1pipi+1 образуют правый поворот, иначе они образуют левый поворот. На рис. 6.13 тройка точек p0p1p2 образует левый поворот, а p1p2p3 — правый поворот. Это свойство легко проверяется с помощью векторного произведения плоских векторов: в первом случае векторное произведение (pi – pi-1) × (pi+1 – pi-1) меньше нуля, а во втором векторное произведение будет больше нуля. Напомним, что для векторов в плоскости Oxy векторное произведение будет вектором, параллельным оси Oz, и мы в этом случае под векторным произведением понимаем вещественное число, равное величине проекции этого вектора на ось Oz. Из выпуклости многоугольника следует, что при его обходе будут делаться только левые повороты. В зависимости от величины угла, образуемого текущей тройкой точек, возможны следующие два варианта продолжения просмотра:
q если pi-1pipi+1 образуют правый поворот, то удаляем вершину pi из массива;
q если pi-1pipi+1 образуют левый поворот, то увеличиваем i на 1.
Просмотр завершается, когда, обойдя все вершины, вновь приходим к начальной вершине pi0.
Анализ показывает, что такой просмотр выполняется за линейное время O (m). Тем не менее, сложность алгоритма будет зависеть от сложности метода сортировки точек перед просмотром. Если выбрать быструю сортировку Хоара или турнирную сортировку, то получим, что время работы алгоритма методом обхода Грэхема равно O (m log m).
Приведем программную реализацию метода обхода Грэхема.
Листинг 6.5. Метод Грэхема
// метод Грэхема
//--------------------------------------------------------------------------#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
//--------------------------------------------------------------------------#pragma package(smart_init)
#pragma resource "*.dfm"
#include <math.h>
#include <stdlib.h>
#define PI 3.14159
TForm1 *Form1;
int getmaxx()
{
return Form1->Image1->Width;
}
int getmaxy()
{
return Form1->Image1->Height;
}
struct Pnt // класс точки
{
double x, y; // координаты точки
int code(Pnt q); // код четверти, в которой лежит точка q
double operator*(Pnt q); // векторное произведение
Pnt operator-(Pnt q); // разность векторов
int operator!=(Pnt q);
};
int Pnt::code(Pnt q) // код четверти, в которой лежит точка q
{
// начало координат находится в точке (x, y)
if(q.x - x >= 0 && q.y - y >= 0) return 0;
if(q.x - x < 0 && q.y - y >= 0) return 1;
if(q.x - x >= 0 && q.y - y < 0) return 3;
if(q.x - x < 0 && q.y - y < 0) return 2;
}
double Pnt::operator*(Pnt q)
{
return x * q.y - y * q.x; // векторное произведение
}
Pnt Pnt::operator-(Pnt q) // разность векторов
{
Pnt t; t.x = x - q.x; t.y = y - q.y; return t;
}
double fabs(Pnt p)
{
return sqrt(p.x*p.x+p.y*p.y);
}
int operator<(Pnt p, Pnt q)
{
Pnt t; // сравнение углов радиус-векторов p и q
t.x = 0; t.y = 0; // коды четвертей вычисляются
// относительно (0,0)
if(t.code(p) < t.code(q)) return 1;
if(t.code(p) > t.code(q)) return 0;
return (p * q > 0); // вращение от p к q направлено
// против часовой стрелки
}
int Pnt::operator!=(Pnt q)
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.