Компьютерная графика

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ 
Государственное образовательное учреждение  
высшего профессионального образования 
Южный Федеральный Университет

Факультет автоматики и вычислительной техники

Кафедра Вычислительной техники

 

 

 

          

 

 

 

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

Компьютерная графика

«Задача двумерного отсечения»

Вариант № 4

 

 

Выполнили:

студенты группы А-30

Дудников  С.В

__________________

 

Проверил:

Селянкин  В.В

__________________

 

 

«___» ____________ 2012г

 

 

 

 

 

 

Таганрог 2012

                               

 

Программа написана на языке Turbo Pascal.

 

Задание к лабораторной работе: Реализовать общий алгоритм отсечения отрезка регулярным окном.При этом предусмотреть все возможные варианты отсечения.

 

Описание алгоритма: Идея алгоритма заключается в том, что каждая грань отсекающего окна делит плоскость на две полуплоскости – внутреннюю, содержащую отсекающее окно, и внешнюю. В свою очередь отрезок в точке пересечения с гранью окна также делится на две части, которые располагаются во внутренней и внешней полуплоскостях. Часть отрезка, расположенная во внешней полуплоскости, в соответствии с алгоритмом отбрасывается, как заведомо невидимая.

Более потробно алгоритм можно описать  так:

1. Генирируются координаты прямой P1 и P2,причём P1>P2(Всегда кроме случая x1=x2).
2. Проверка отрезка на видимость-не видимость(Если условие выполняется то отрезок либо чертится,либо не чертится).Proverka1
3. Проверка отрезка на перпендикулярность сторонам прямоугольника(Если отрезок будет перпендикулярным,тогда мы не сможем просчитать точки Т1 и Т2).Proverka2

Если  условие выполняется,тогда чертим отрезок.

4. Если пункты 2 и 3 не выполняется,тогда находятся 4 точки пересечения(см.ниже),при этом точки сортируются в порядке возрастания.Далее выделяются 2 средние точки и также сортируются по возрастанию.(Врезультате имеем T1 и T2, причём T1>T2 всегда).
5. Проверяем точки P1 и P2 на принадлежность внутренней области прямоугольника provT.(Если P1 находится внутри,тогда чертим линию P1,T2.Если Р2 находится внутри,тогда линия Р2,Т1.Если обе точки не  внутри области,тогда чертим линию Т1 и Т2(При этом необходимо проверить условия на принадлежность точек прямоугольнику).

 

Более потробно по каждому пункту:

1. Координаты прямой генерируются с помощью функции Random.

Посе  чего они сортируются по значению y.

2. Проверка отрезка на видимость-невидимость:

Условие полной видимости:

(xл £ x1 £ xп) & (xл £ x2 £ xп) & (yн £ y1 £ yв) & (yн £ y2 £ yв).

 

Условие полной невидимости:

((x1 < xл) & (x2 < xл)) V ((x1 > xп) & (x2 > xп)) V ((y1 < yн) & (y2 < yн)) V ((y1 > yв) & ( y2 > yв)).

 

3. Если X1=X2 или Y1=Y2 значит отрезок перпендикулярен сторонам прямоугльника.

Находим расположения точек X1,Y1 и  X2,Y2.Если одна из этих точек лежит внутри области,тогда чертим отрезок от этой точки и до края прямоугольника.Если обе точки снаружи,тогда чертим линию от грани до грани.

4. Необходимо найти 4 точки пересечения.Они находятся следующим образом:

 

 

 

 

 

 

 

 

На рисунке они расположены  соответсвенно:

 

Далее сортируем их по возрастанию  занчения Y и выделяем среди них 2 и 3.

5. Проверяем Р1 и Р2 на принадлежность внутренней области прямоугольника с помощью функции provT,которая возвращает значения истина если точка внутри и ложь если снаружи.

 

Описание программы:

Переменные:

Versh-массив,содержащий 4 вершины прямоугольника.

P-массив,содержащий координаты точек отрека(X,Y).

t-массив,содержащий координаты 4 точек пересечения.

Tg1,tg2-точки пересечения,лежащие на ребрах прямоугольника.

f-логическая переменная,используемая как флаг.

i-переменная для организации циклов.

С-для организации общего цикла программы.

Процедуры и функции:

Функция tochka(пер) возращает координату точки(X или Y).Где пер-координата(X или Y) одной из вершин прямоугольника.

Процедура poisk(tg1,tg2) находит точки t1(x,y),tg2(x,y) причём tg1>tg2 по значению y.

Процедура okno рисует ортогональное окно по данным из массива Versh.

Процедура vvoddata генерирует координаты x1,y1,x2,y2.

Функция provT(пер) проверяет находится ли точка внутри области(возвращает логическое значение).

Процедура proverka1 проверка на видимость-невидимость отрезка.

Процедура proverka2 проверяет отрезок на перпендикулярность граням окна.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                               Общий алгоритм программы(блок-схема):

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                          Текст программы:

uses graph,crt;

const

versh:array[1..4] of pointtype= ((x:75;y:100),(x:75;y:50),

                            (x:175;y:50),(x:175;y:100));

type

point=record

x,y:integer;

end;

 

var

i:byte;

P:array [1..2]of point;

t:array [1..4]of point;

tg1,tg2,buf:point;

driver,mode:integer;

f:boolean;

c:char;

 

function tochka(a:integer):integer;

var

  k:real;

begin

    k:=((P[2].y-P[1].y)/(P[2].x-P[1].x));

  if ((a=versh[1].x)or(a=versh[2].x)or(a=versh[3].x)or(a=versh[4].x)) then

     tochka:=round((k*(a-P[1].x)+P[1].y))

  else

     tochka:=round(((1/k)*(a-P[1].y)+P[1].x));

end;

 

procedure poisk(var a,b:point);

var

j:byte;

begin

  t[1].x:=tochka(versh[1].y);

  t[1].y:=versh[1].y;

  t[2].x:=versh[1].x;

  t[2].y:=tochka(versh[1].x);

  t[3].x:=tochka(versh[3].y);

  t[3].y:=versh[3].y;

  t[4].x:=versh[3].x;

  t[4].y:=tochka(versh[3].x);

for i:=1 to 3 do begin

    for j:=i+1 to 4 do begin

      with t[i] do begin

       if t[i].y>t[j].y then

         begin

           buf:=t[i];

           t[i]:=t[j];

           t[j]:=buf;

         end;

      end;

    end;

  end;

with t[i] do begin

  a:=t[2];

  b:=t[3];

end;

if a.y>b.y then

with a,b do begin

   buf:=a;

   a:=b;

   b:=buf;

end;

end;

 

procedure okno;

begin

for i:=1 to 3 do line(versh[i].x,versh[i].y,versh[i+1].x,versh[i+1].y);

  line(versh[4].x,versh[4].y,versh[1].x,versh[1].y);

end;

 

procedure vvoddata;

begin

randomize;

for i:=1 to 2 do begin

P[i].x:=random(160);

P[i].y:=random(160);

end;

i:=1;

if P[i].y>P[i+1].y then

with P[i] do begin

   buf:=P[i];

   P[i]:=P[i+1];

   P[i+1]:=buf;

end;

end;

 

function provT(i:byte):boolean;

begin

  if (P[i].x>versh[1].x)and(P[i].x<versh[4].x)

     and(P[i].y>versh[2].y)and(P[i].y<versh[1].y)

      then provT:=true;

end;

 

procedure proverka2(var f:boolean);

begin

  if P[1].x=P[2].x then

    begin

      if provT(1)=true then line(P[1].x,P[1].y,P[1].x,versh[1].y)

         else begin

           if provT(2)=true then line(P[2].x,P[2].y,P[2].x,versh[2].y)

             else line(P[1].x,versh[1].y,P[1].x,versh[2].y)

         end;

     f:=true;

    end else

      begin

        if P[1].y=P[2].y then

          begin

           if P[1].x>P[2].x then begin

            i:=1;

              with P[i] do begin

               buf:=P[i+1];

               P[i+1]:=P[i];

               P[i]:=buf;

              end;

           end;

        if provT(1)=true then line(P[1].x,P[1].y,versh[4].x,P[1].y)

              else begin

                if provT(2)=true then line(P[2].x,P[2].y,versh[1].x,P[2].y)

                  else line(versh[1].x,P[1].y,versh[4].x,P[2].y)

              end;

           f:=true;

          end;

      end;

end;

 

procedure proverka1(var f:boolean);

begin

if ((P[1].x>=versh[1].x)and(P[1].x<=versh[4].x))and((P[2].x>=versh[1].x)and

(P[2].x<=versh[4].x))and((P[1].y>=versh[2].y)and(P[1].y<=versh[1].y))and

((P[2].y>=versh[2].y)and(P[2].y<=versh[1].y)) then

begin

  line(P[1].x,P[1].y,P[2].x,P[2].y);

  f:=true;

end;

if ((P[1].x<versh[1].x)and(P[2].x<versh[1].x)) or ((P[1].x>versh[4].x)and

(P[2].x>versh[4].x)) or ((P[1].y<versh[2].y)and(P[2].y<versh[2].y)) or

((P[1].y>versh[1].y)and(P[2].y>versh[1].y)) then f:=true;

end;

 

begin

driver:=8;

mode:=3;

initgraph(driver,mode,'d:\tp7\bin');

while c<>' 'do begin

ClearDevice;

f:=false;

vvoddata;

okno;

putpixel(P[1].x,P[1].y,1);

putpixel(P[2].x,P[2].y,1);

setcolor(2);

proverka1(f);

if f=false then begin

  proverka2(f);

    if f=false then begin

       setcolor(2);

       poisk(tg1,tg2);

         if provT(1)=true then line(P[1].x,P[1].y,tg2.x,tg2.y)

           else begin

             if provT(2)=true then line(P[2].x,P[2].y,tg1.x,tg1.y)

             else begin

              if ((tg1.x>=versh[1].x)and(tg1.x<=versh[4].x))

              and((tg2.x>=versh[1].x)and(tg2.x<=versh[4].x))

              and((tg1.y>=versh[2].y)and(tg1.y<=versh[1].y))

              and((tg2.y>=versh[2].y)and(tg2.y<=versh[1].y))

               then

                 line(tg1.x,tg1.y,tg2.x,tg2.y);

             end;

           end;

    end;

end;

c:=readkey;

setcolor(3);

end;

end.