Скачиваний:
14
Добавлен:
01.05.2014
Размер:
13.31 Кб
Скачать
// CHHelp.cpp : implementation file
//

#include "stdafx.h"
#include "CHRealTime.h"
#include "CHHelp.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CCHHelp dialog


CCHHelp::CCHHelp(CWnd* pParent /*=NULL*/)
	: CDialog(CCHHelp::IDD, pParent)
{
	//{{AFX_DATA_INIT(CCHHelp)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
}


void CCHHelp::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CCHHelp)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}


BEGIN_MESSAGE_MAP(CCHHelp, CDialog)
	//{{AFX_MSG_MAP(CCHHelp)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CCHHelp message handlers

BOOL CCHHelp::OnInitDialog() 
{
	CDialog::OnInitDialog();
	
	// TODO: Add extra initialization here
	CListBox *clist = (CListBox *)this->GetDlgItem(IDC_LIST1);
CString str("         Построение выпуклой оболочки в реальном времени");
str.MakeUpper();
clist->AddString(str);
clist->AddString("     Во многих прикладных областях, где возникают геометрические задачи, в част-");
clist->AddString("ности связанные с обработкой данных в реальном времени, и ряд вычислений должен ");
clist->AddString("выполняться по мере поступления точек (данных). В общем случае алгоритм, обраба-");
clist->AddString("тывающий данные по мере поступления, называется открытым.");
clist->AddString("     Основной чертой открытых алгоритмов является отсутствие ограничений на время");
clist->AddString("коррекции, что равносильно тому, что новый элемент данных (точка) вводится по ");
clist->AddString("запросу сразу же после того, как завершается коррекция, связанная с предыдущим ");
clist->AddString("элементом данных. Будем называть временной интервал между вводом двух последова-");
clist->AddString("тельных элементов данных задержкой поступления данных. Более сложный в смысле ");
clist->AddString("предъявляемых требований случай применения открытых алгоритмов возникает, когда ");
clist->AddString("задержка поступления данных находится вне контроля алгоритма. Иначе говоря, дан-");
clist->AddString("ные поступают не по запросу алгоритма, а подаются на вход алгоритма в некоторые ");
clist->AddString("моменты времени, никак не связанные с работой алгоритма.");
clist->AddString("     Однако мы будем считать, что поступление данных происходит (распределено) ");
clist->AddString("равномерно по времени. В такой ситуации коррекция должна выполняться за время, ");
clist->AddString("не превышающее постоянную задержку поступления данных. Алгоритмы, работающие в ");
clist->AddString("таком режиме, и называются соответственно алгоритмами реального времени. Следует");
clist->AddString("отметить, что обычно открытые алгоритмы глобально являются менее эффективными по");
clist->AddString("сравнению с соответствующими закрытыми алгоритмами (какая-то плата должна быть ");
clist->AddString("внесена за открытость алгоритма).");
clist->AddString("     Рассмотрим алгоритм построения выпуклой оболочки в реальном времени.");
clist->AddString("     Задача (ВЫПУКЛАЯ ОБОЛОЧКА В РЕАЛЬНОМ ВРЕМЕНИ). На плоскости задана после-");
clist->AddString("довательность из N точек pi, .... рN. Требуется найти их выпуклую оболочку при ");
clist->AddString("условии, что время задержки поступления точек постоянно.");
clist->AddString(" ");
clist->AddString("     При решении задачи, единственное, что необходимо, - это уметь быстро строить");
clist->AddString("две опорные прямые к выпуклому многоугольнику, проходящие через некоторую точку. ");
clist->AddString("В частности, если точки обрабатываются в порядке p1, p2, ... и pi - текущая точка,");
clist->AddString("то обозначим через Сi-1 выпуклую оболочку множества { p1, p2, ..., pi-1 }. Необ-");
clist->AddString("ходимо построить из точки pi опорные прямые к Ci-1, если они существуют (т. е. ");
clist->AddString("если точка pi является внешней для Ci-1). Таких прямых не существует тогда и то-");
clist->AddString("лько тогда, когда точка pi является внутренней для Ci-1. В последнем случае точка");
clist->AddString("pi просто удаляется. В первом случае должна быть удалена соответствующая цепочка");
clist->AddString("вершин, заключенная между двумя опорными точками, и вместо них должна быть встав-");
clist->AddString("лена точка pi. Для удобства будем называть опорную прямую левой или правой в со-");
clist->AddString("ответствии с тем, по какую сторону она находится,  если смотреть из точки pi на ");
clist->AddString("Ci-1.");
clist->AddString("     Рассмотрим построение опорных прямых из некоторой точки р к выпуклому много-");
clist->AddString("угольнику С. Важную роль играет классификация вершин многоугольника С по отношен-");
clist->AddString("ию к отрезку pv, соединяющему вершину v с точкой р. Вершина v называется вогнутой, ");
clist->AddString("если отрезок pvпересекает внутренность многоугольника С. Иначе, если две смежные ");
clist->AddString("с v вершины лежат по одну сторону от прямой, проходящей через точки р и v, верши-");
clist->AddString("на v называется опорной. В оставшемся случае v называется выпуклой вершиной. Вер-");
clist->AddString("шина и может быть классифицирована за постоянное время.");
clist->AddString("     Если v - опорная вершина, то на этом решение задачи завершается. Предположим,");
clist->AddString("что ищется левая опорная прямая. Если точка v не является опорной, то необходимо ");
clist->AddString("идти по вершинам многоугольника С против или по часовой стрелке в зависимости от ");
clist->AddString("того, является ли и вогнутой или выпуклой вершиной. Таким способом можно опреде-");
clist->AddString("лить две опорные точки (если они существуют). Если это сделано, необходимо иметь ");
clist->AddString("возможность удалить из циклической последовательности вершин многоугольника С це-");
clist->AddString("почку вершин (возможно, пустую) и вставить в образовавшийся разрыв точку р.");
clist->AddString("     Необходимо иметь возможность эффективно   выполнять следующие операции:");
clist->AddString("I. ПОИСК в упорядоченной последовательности элементов (кольцевого списка вершин ");
clist->AddString("оболочки) для определения опорных прямых из точки рг,");
clist->AddString("II. РАСЦЕПЛЕНИЕ последовательности на две последовательности и СЦЕПЛЕНИЕ двух ");
clist->AddString("последовательностей;");
clist->AddString("III. ВСТАВКА одного элемента (текущей точки pi).");
clist->AddString("     Структура данных, в полной мере удовлетворяющая перечисленным требованиям ");
clist->AddString("известна и называется сцепляемой очередью. Она реализуется с помощью сбалансиро-");
clist->AddString("ванного по высоте дерева поиска, и при этом каждая из указанных выше операций мо-");
clist->AddString("жет быть выполнена за время O(logi) в худшем случае, где i-число узлов дерева. ");
clist->AddString("Естественно, кольцевая последовательность вершин представляется в этой древовид-");
clist->AddString("ной структуре данных (называемой далее Т) цепочкой, и при этом первый и послед-");
clist->AddString("ний элементы считаются смежными.");
clist->AddString("     В структуре Т будут выделены две вершины: т - самый левый член цепочки и М -");
clist->AddString("корневой член цепочки. Кроме того, мы будем использовать угол  (m pi M), который ");
clist->AddString("обозначим а. Этот угол называется выпуклым, если он меньше или равен  , и вогну-");
clist->AddString("тым в противном случае.");
clist->AddString("     В зависимости от классификации вершин m и М (вогнутая, опорная или выпуклая) ");
clist->AddString("и угла а возможны всего восемнадцать случаев. Однако все эти случаи можно свести");
clist->AddString("к восьми (покрывающим все возможности), сведенным в табл. I.");
clist->AddString(" ");
clist->AddString("Таблица I");
clist->AddString("Случай       a             m             M");
clist->AddString("  1      выпуклый     вогнутая      вогнутая");
clist->AddString("  2      выпуклый     вогнутая      невогнутая");
clist->AddString("  3      выпуклый     невогнутая    выпуклая");
clist->AddString("  4      выпуклый     невогнутая    невыпуклая");
clist->AddString("  5      вогнутый     выпуклая      выпуклая");
clist->AddString("  6      вогнутый     выпуклая      невыпуклая");
clist->AddString("  7      вогнутый     невыпуклая    вогнутая");
clist->AddString("  8      вогнутый     невыпуклая    невогнутая");
clist->AddString(" ");
clist->AddString("     Перечисленные случаи можно изобразить в виде диаграмм (используются в прог-");
clist->AddString("рамме).Диаграммы расшифровываются следующим образом: окружность, на которой ле-");
clist->AddString("жат точки М и m, обозначает многоугольник Р; упорядоченная последовательность ве-");
clist->AddString("ршин начинается в точке m и располагается по окружности в порядке против часовой");
clist->AddString("стрелки; L(M) и R(M) -это последовательности вершин, хранимые в левом и правом ");
clist->AddString("поддеревьях корня дерева Т.");
clist->AddString("     Каждый из случаев требует различной обработки для определения левой и пра-");
clist->AddString("вой опорных точек, обозначаемых соответственно I и r.");
clist->AddString("Рассмотрим сначала случаи 2, 4, 6 и 8. Для этих случаев известно, что I и r су-");
clist->AddString("ществуют (так как р не может быть внутренней точкой многоугольника) и их следует ");
clist->AddString("искать в различных поддеревьях корня дерева Т (одно из этих поддеревьев расширя-");
clist->AddString("ется, чтобы включить сам корень). Таким образом, поиск I и r должен проходить ");
clist->AddString("одинаково. Например, следующая процедура осуществляет поиск вершины I:");
clist->AddString("function ЛЕВЫЙ-ПОИСК(T) ");
clist->AddString("Input: дерево Т, описывающее последовательность вершин Output: вершина I");
clist->AddString("1.   begin с :=КОРЕНЬ(T);");
clist->AddString("2.      if (pc - опорная прямая) then l := с");
clist->AddString("3.      else begin if (с-выпуклая вершина) then");
clist->AddString("                Т := ЛДЕРЕВО(с) else Т := ПДЕРЕВО(с)");
clist->AddString("4.              l:== ЛЕВЫЙ-ПОИСКА) ");
clist->AddString("             end;");
clist->AddString("5.      return ;");
clist->AddString("      end.");
clist->AddString("     Очевидно, что функция ЛЕВЫЙ-ПОИСК проходит по дереву Т некоторый путь, зат-");
clist->AddString("рачивая в каждом узле ограниченное время на классификацию соответствующей узлу ");
clist->AddString("вершины. То же самое имеет место и для функции  ПРАВЫЙ-ПОИСК. Теперь рассмотрим ");
clist->AddString("случаи 1. 3, 5 и 7. В каждом из этих случаев обе вершины l и r следует искать в ");
clist->AddString("одном и том же поддереве корня, если они только существуют (следует отметить, ");
clist->AddString("что в случаях 1 и 7 точка р может быть внутренней точкой Р). Таким образом, в ");
clist->AddString("каждом случае процедура поиска рекурсивно вызывает себя для поиска в поддереве ");
clist->AddString("текущего дерева (выбирается поддерево, соответствующее последовательности, обве-");
clist->AddString("денной на диаграмме штриховой линией) до тех пор, пока не встретится один из слу-");
clist->AddString("чаев 2. 4, 6 или 8. В этом месте инициируется раздельный поиск с помощью функций ");
clist->AddString("ЛЕВЫЙ-ПОИСК и ПРАВЫЙ-ПОИСК. Если в процессе поиска будет достигнут лист дере-");
clist->AddString("ва Т и при этом не имел место ни один из случаев 2, 4, 6 или 8, то точка р явля-");
clist->AddString("ется внутренней для многоугольника. Учитывая, что дерево Т сбалансировано и со-");
clist->AddString("держит не более i < N вершин, а на обработку в каждом узле требуется ограниченное ");
clist->AddString("время, получаем для времени поиска оценку О (log i).");
clist->AddString("     Чтобы завершить описание, рассмотрим процедуру перестройки многоугольника ");
clist->AddString("Ci-1 , выполняемую, если точка pi является внешней для него. Вершины между l и ");
clist->AddString("r должны быть удалены, a pi должна быть вставлена на их место. В зависимости от ");
clist->AddString("того, предшествует вершина I вершине r в дереве Т или нет, требуется выполнить ");
clist->AddString("немного различные действия. В первом случае необходимо дважды выполнить операцию ");
clist->AddString("расцепления и один раз сцепления; во втором случае только дважды выполняется опе-");
clist->AddString("рация расцепления.");
clist->AddString("     Обе операции РАСЦЕПИТЬ и СЦЕПИТЬ выполняются за время O(log i). В результа-");
clist->AddString("те, учитывая, что коррекция выпуклой оболочки может быть выполнена за время ");
clist->AddString("О(log i), получаем: ");
clist->AddString("     Выпуклая оболочка множества из N точек на плоскости может быть найдена с по-");
clist->AddString("мощью открытого алгоритма за время O(N log N) со временем коррекции O(log N), т.e.");
clist->AddString("может быть построена в реальном времени.");
	
	return TRUE;  // return TRUE unless you set the focus to a control
	              // EXCEPTION: OCX Property Pages should return FALSE
}
Соседние файлы в папке Source