Программная реализация алгоритма Кируса-бека

 

2. Направление векторов

Учет  ориентации помогает корректно идентифицировать полностью видимые отрезки. Это  соображение используется при формальной записи алгоритма Кируса — Бека, которая приводится ниже.

Для формализации этого алгоритма напомним, что параметрическое описание отрезка  имеет вид:

 

Р(t) = P₁ + (Р₂ - P₁)t    0 £ t £ 1                    (1)

 

а скалярное произведение внутренней нормали на вектор, начинающийся в  произвольной точке отрезка и  заканчивающийся в другой точке, лежащей на той же границе окна, т. е.

 

n_i[P(t)-f_i]     i=1,2,3,...                                 (2)

 

будет положительно, равно нулю или отрицательно — в зависимости от того, будет  ли избранная точка отрезка лежать с внутренней стороны границы, на самой этой границе или с ее внешней стороны. Последнее соотношение применимо к любой плоскости или ребру номер i, ограничивающим область. Подстановка (1) в (2) дает условие пересечения отрезка с границей области:

n_i[P₁ +(P₂ - P_i)t-f_i]=0                       (3)

В другой форме уравнение (3) имеет  вид:

n_i[P₁ - f_i] + n_i [Р₂ - P₁]t = 0                         (4)

Заметим, что вектор Р₂ - P₁ определяет ориентацию отрезка, а вектор P₁ - f_i, пропорционален расстоянию от первого конца отрезка до избранной граничной точки. Обозначим через D = Р₂ - Р₁ директрису или ориентацию отрезка, а через w_i = Р₁ — f_i — некий весовой множитель. Тогда уравнение (4) можно записать так:

t(n_i*D) + w_in_i =0                          (5)

Решая последнее уравнение относительно t, имеем:

t = -(w_i*n_i)/(D*n_i)   D¹0  i=1, 2, 3, ...     (6)

Здесь Dn_i может быть равным нулю только при D = О, а это означает, что Р₂ = P₁ т. е. вырождение отрезка в точку. Если

 

 

Уравнение (6) используется для получения значений t, соответствующих пересечениям отрезка с каждой стороной окна. Если значение t лежит за пределами интервала 0 £ t £ 1, то можно его проигнорировать. Хотя известно, что отрезок может пересечь выпуклое окно не более чем в двух точках, т. е. при двух значениях t, уравнения (6) могут дать большее число решений в интервале О £ t £ 1. Эти решения следует разбить на две группы: нижнюю и верхнюю, в зависимости от того, к началу или к концу отрезка будет ближе соответствующая точка. Нужно найти наибольшую из нижних и наименьшую из верхних точек. Если Dn_i > 0, то найденное значение t рассматривается в качестве возможного нижнего предела. Если Dn_i < 0, то значение t рассматривается в качестве возможного верхнего предела. Ниже приводится запись этого алгоритма на псевдокоде.

Алгоритм  двумерного отсечения Кируса — Бека

Р1, P2 — концевые точки отрезка

k      — число сторон отсекающего окна

n_i     — вектор нормали к i-и стороне окна

f_i      — точка, лежащая на i-й стороне окна

D     — директриса отрезка, равная  Р2 — P1

w_i      — весовая функция, равная Р1 — f_i

tн, tв  — нижний и верхний пределы значений параметра t

инициализировать  пределы значений параметра, предполагая  что отрезок полностью видимый 

tн = 0

tв = 1

вычислить директрису D

D = Р2 - Р1

начать  главный цикл

for i = 1 to k

вычислить W_i, Dn_i и w_in для данного i

w_i = Р1 - f_i

call Скал-произвед(D, n_i, D_Ck)

call Скал-произвед(w_i, n_i, W_Ck)

отрезок вырождается в точку?

if D_Ck = 0 then 2

отрезок невырожден, вычислить t

t = -Wc_k/Dc_k,

поиск верхнего и нижнего пределов t

if D_Ck > 0 then 1

поиск верхнего предела

верно ли, что 0 £ t £ 1?

if t < 0 then 4

tв = min(t, tв)

go to 3

поиск нижнего предела верно ли, что t £ 1?

1     if t > 1 then 4

tл = max (t, tл)

go to 3

отрезок выродился в точку

2     if Wс_k < 0 then 4

точка видима относительно текущей границы

3     next i

произошел нормальный выход из цикла проверка фактической видимости отрезка 

if tн > tв then 4

Начертить отрезок от P(tн) до P(tв)

4     Обработать следующий отрезок

подпрограмма  вычисления скалярного произведения

subroutine Скал-произвед (Вектор1, Вектор2; Скал)

Вектор1 — первый вектор, заданный компонентами х и у 

Вектор2 — второй вектор, заданный компонентами х и у 

Скал  — скалярное произведение векторов

Скал = Вектор1х * Вектор2х + Вектор1у * Вектор2у 

return

 

 

 

 

3. Структурная схема алгоритма  Кируса – Бека

 

2.Практическая часть

 

2.1 Постановка задачи

Разработать программу, реализующую алгоритм двумерного отсечения Кируса – Бека.

 

2.2 Назначение

Приложение  предназначено для демонстрации возможностей языка Delphi при программировании задач компьютерной графики. Программа выполняет:

• ввод окна отсекателя;
• ввод отсекаемых отрезков;
• отсечение.

 

2.3 Системные требования

Для разработанной программы необходимы следующие минимальные системные требования.

Таблица1 – такблица системных требований

Процессор	Pentium с тактовой частотой 233 МГц или  выше; рекомендуется Pentium III
Операционная система	Microsoft Windows 2000 с пакетом обновления 3 (SP3) или  более поздней версии; Windows XP или  более поздняя версия (рекомендуется)
Память	64 Мбайт ОЗУ (минимум); 128 Мбайт ОЗУ  (рекомендуется)
Место на жестком диске	600 Кбайт
Монитор	SVGA (800´600) или с более высоким разрешением, 256 цветов
Указывающее устройство	Microsoft Mouse, Microsoft IntelliMouse или совместимое указывающее  устройство

 

2.4 Структура программы

Ниже  перечислены самые необходимые  процедуры для создания такого  рода программ.

Функция UseBWForContrast

Определение цвета контрастного заданному.

Процедура ClearListOfLines

Очистка списка линий.

Процедура StartNewLine

Начать  рисование новой линии.

Процедура DeleteTopmostLine

Удаление  линии.

Процедура SetMode

Установка режима вывода линий.

Процедура PaintBox1Paint

Вывод сцены.

Процедура DoClipping

Управляющая процедура отсечения.

Процедура PaintBox1MouseUp

Обработка отпускания кнопки мыши.

Процедура PaintBox1MouseMove

Обработка перемещения мыши.

Процедура ButtonLineClick

Включение режима рисования линий.

Процедура ButtonRectClick

Включение режима рисование окна отсекателя.

Процедура FormDestroy

Удаление  формы из памяти.

Процедура FormCreate

Инициализация формы.

Процедура ItemColorDrawItem

Вывод цветного пункта меню.

Процедура ItemColorClick

Выбор цвета.

Процедура FileExitExecute

Выход из программы.

Процедура ButtonClipClick

Нажатие кнопки выполнения отсечения.

Процедура Button1Click

Очистка области построения.

Процедура ClipLineWithRectangle

Алгоритм  Кируса – Бека для двумерного отсечения.

 

2.5 Инструкция пользователю

Установка системы производится путем копирования  папки Kirus, не нарушая внутреннюю структуру каталогов (это повлечет за собой различного рода сбои и ошибки при работе программы), на любой магнитный носитель позволяющий перезаписывать и дописывать данные (без этих функций в базу данных невозможно вносить изменения).

Для начала работы пользователь должен запустить  программу любым имеющимся для  этого способом операционной системы  Windows. После запуска программы на экране появится главная форма. Данная форма представлена на рисунке 4.

Состав  и назначение элементов окна.

 Кнопки управления:

• Отрезок: чертить отрезки;
• Окно: чертить отсекатель;
• Отсечь: выполнить отсечение;
• Очистить: очистка области построения;
• Выход: завершить работу с программой.

 

 

4. Окно программы

‚ Область построений.

ƒ Область выбора цвета.

• Цвет окна: цвет отсекающего окна;
• Внешняя часть отрезка: выбор цвета отрезка за пределами отсекателя;
• Внутренняя часть отрезка: выбор цвета отрезка внутри отсекателя.

Флажки  «внешнее отсечение» и «внутренне отсечение» запрещают или разрешают соответствующий  вид отсечения относительно отсекающего  окна.

Последовательность  работы с программой.

1) Рисуем окно отсекателя. Для этого  нажимаем на кнопку Окно. Устанавливаем курсор мыши в точку начала рисования, нажимаем левую кнопку. Отпускаем кнопку и «растягиваем» прямоугольник до нужных размеров.

2) Рисуем отрезки. Нажимаем кнопку Отрезки. Устанавливаем курсор мыши в точку начала отрезка, нажимаем левую кнопку. Отпускаем кнопку и проводим линию нужных размеров.

3) Нажимаем кнопку Отсечь. Программа выполняет отсечение и выводит результат: отрезки, расположенные внутри отсекателя при этом окрашены одним цветом, за пределами отсекателя – другим.

Очистка области построения выполняется  после нажатия кнопки Очистить.

Для завершения работы с программой нажать кнопку Выход.

 

2.6. Контрольный пример

 

 

Заключение

 

По  результатам выполнения курсовой работы на тему «Разработка программы реализующей алгоритм Кируса – Бека» можно сделать следующие выводы:

Главным итогом выполнения является создание программы, реализующей указанный метод. В программе используются оригинальные процедуры которые обеспечивают возможность нахождения точек пересечения заданного многоугольника и прямой и построения на экране результатов. Эти процедуры могут без изменений переноситься и использоваться программами в которых решаются различные задачи графических построений.

В программе был использован модульный  принцип разработки, что позволило приобрести навыки программирования с использованием этого принципа и сделать программу более надежной и простой в отладке.

Программа имеет развитый пользовательский интерфейс, что позволяет работать с разработанной  программой пользователю с минимальной  квалификацией.

 

 

 

 

 

 

 

 

 

 

 

 

 

Список  литературы

 

1. Глушаков С.В., Клевцов А.Л., Теребилов  С.А. Программирование на Delphi. –Харьков: Фолио, 2002. -518 с.
2. Зозулевич Д. И. Машинная графика в автоматизированном проектировании. – М.: Машиностроение, 1996. – 240 с.
3. Корриган Дж.  Компьютерная  графика: Секреты и решения. –М.: Диалог – МИФИ,  2005. –372 с.
4. Павлидис Т. Алгоритмы машинной графики и обработки изображений: Пер. с англ. –М.:Радио и связь, 1986. –400 с.
5. Роджерс Д. Алгоритмические основы машинной графики. Пер. с англ. -М.: Мир, 1989. -512 с.
6. Шикин А. В., Боресков Л. В. Компьютерная графика. Полигональные модели. –M.: ДИАЛОГ–МИФИ, 2001. –464 с.
7. Энджел Э. Практическое введение в машинную графику: Пер. с англ. –М.: Радио и связь, 1984.  –136 с.

 

Приложение. Листинг программы

 

unit Main;

 

interface

 

uses

  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,

  StdCtrls, Menus, ExtCtrls, ClippingRoutines, ComCtrls, ToolWin, ImgList;

 

type

  TMode = (mNone, mLineP1, mLineP2, mRectP1, mRectP2, mView, mClip);

  PLine = ^TLine;

  TLine = record

    P1, P2 : TPoint;

    ClipP1, ClipP2 : TPoint;

    Vis  : TVisibility;

    Next : PLine;

    ExchangeLeftAndRight : Boolean;

  end;

 

  TFormMain = class(TForm)

    PanelView: TPanel;

    ToolBar1: TToolBar;

    ToolButton1: TToolButton;

    ToolButton2: TToolButton;

    ToolButton3: TToolButton;

    ToolButton4: TToolButton;

    ImageList1: TImageList;

    PaintBox1: TPaintBox;

    Panel1: TPanel;

    Label1: TLabel;

    ToolButton5: TToolButton;

    cbRect: TColorBox;

    Label2: TLabel;

    cbOut: TColorBox;

    cbIn: TColorBox;

    Label3: TLabel;

    chbOut: TCheckBox;

    chbIn: TCheckBox;

    procedure PaintBox1Paint(Sender: TObject);

    procedure PaintBox1MouseUp(Sender: TObject; Button: TMouseButton;

      Shift: TShiftState; X, Y: Integer);

    procedure PaintBox1MouseMove(Sender: TObject; Shift: TShiftState; X,

      Y: Integer);

    procedure ButtonLineClick(Sender: TObject);

    procedure FormDestroy(Sender: TObject);

    procedure ButtonRectClick(Sender: TObject);

    procedure FormCreate(Sender: TObject);

    procedure ItemColorDrawItem(Sender: TObject; ACanvas: TCanvas;

      ARect: TRect; Selected: Boolean);

    procedure ItemColorClick(Sender: TObject);

    procedure FileExitExecute(Sender: TObject);

    procedure ButtonClipClick(Sender: TObject);

    procedure ButtonClearClick(Sender: TObject);

    procedure chbOutClick(Sender: TObject);

    procedure chbInClick(Sender: TObject);

  private

    { Private declarations }

    OldMode, Mode : TMode;

  public

    { Public declarations }

    LineList : PLine;

    Rect : PRect;

    procedure SetMode(NewMode : TMode);

    procedure DoClipping;

    procedure ClearListOfLines;

    procedure StartNewLine;

    procedure DeleteTopmostLine;

  end;

 

var

  FormMain: TFormMain;

 

implementation

 

{$R *.dfm}

function UseBWForContrast(Color : TColor) : TColor;

var

  I, B, Max, Sum : Word;

begin

  Sum := 0;

  Max := 0;

  for I := 1 to 3 do

  begin

    B := Color and $000000FF;

    if B > Max then Max := B;

    Sum := Sum + B;

    Color := Color shr 8;

  end;

  if (Color = 0) and ((Sum <= 240) or (Max <= 192)) then

    Result := clWhite

  else

    Result := clBlack;

end;

 

{---------------------------------------------------------}

procedure TFormMain.ClearListOfLines;

begin

  while (LineList <> nil) do DeleteTopmostLine;

end;

 

{---------------------------------------------------------}

procedure TFormMain.StartNewLine;

var

  P : PLine;

begin

  New(P);

  P.Next := LineList;

  LineList := P;

end;

 

{---------------------------------------------------------}

procedure TFormMain.DeleteTopmostLine;

var

  P : PLine;

begin

  P := LineList;

  LineList := P.Next;

  Dispose(P);

end;

 

{---------------------------------------------------------}

procedure TFormMain.SetMode(NewMode : TMode);

begin

  OldMode := Mode;

  if (OldMode = mLineP1) and (NewMode <> mLineP2) then

     DeleteTopmostLine

  else if Assigned(Rect) and (NewMode in [mNone, mRectP1]) or

       (OldMode = mRectP2) and (NewMode = mLineP1) then

  begin

    Dispose(Rect);

    Rect := nil;

  end;

  if NewMode = mNone then

    ClearListOfLines

  else if NewMode = mLineP1 then

    StartNewLine

  else if NewMode = mClip then

    DoClipping;

  Mode := NewMode;

  InvalidateRect(PanelView.Handle, nil, True);

end;