Материал: Контрольная работа

Министерство образования Республики Беларусь

Учреждение образования

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ»

Институт информационных технологий

Специальность Программное обеспечение информационных технологий

Контрольная работа

По курсу Алгоритмы компьютерной графики

Тема: «Отсечение многоугольным окном»

Вариант № 6

Студент-заочник 3 курса

Группы № 781074

ФИО Красносельская Полина Юрьевна

Преподаватель: Коренская И.Н.

Минск, 2019

Цель работы: Написать программу, выполняющую заданное (внутреннее или внешнее) отсечение окном заданной формы движущегося объекта. Освоить алгоритм отсечения прямоугольным окном Кируса-Бэка.

Индивидуальное задание

Необходимо написать программу, выполняющую заданное (внутреннее или внешнее) отсечение окном заданной формы. Форма окна определяется индивидуальным заданием. Программа должна быть основана на алгоритме отсечения прямоугольным окном Кируса-Бэка.

Конкретные размеры заданного окна выбираются с учетом сохранения заданной формы.

Краткие теоретические сведения

Алгоритм Кируса – Бэка является одним из наиболее известных алгоритмов отсечения выпуклым многоугольником.

Отрезок может пересекать выпуклый многоугольник не более, чем в двух точках, при этом, если рассматривать ориентированный отрезок, то он входит в тело многоугольника через одно ребро (фронтальное) и выходит через другое ребро (тыльное). Если отрезок рассматривать как вектор, то независимо от его положения в двумерном пространстве, для заданной направленности вектора все множество ребер многоугольника можно разбить на подмножество фронтальных и подмножество тыльных ребер.

В качестве критерия отнесения отрезка к подмножеству тыльных или фронтальных ребер используется скалярное произведение вектора внутренней нормали n_вт  к соответствующему ребру и  вектора директрисы отрезка  D, при этом если скалярное произведение  положительное, то ребро фронтальное, в противном случае –  ребро тыльное.

Точкой входа отрезка в многоугольник может быть только одна из точек пересечения линий, несущих фронтальные ребра, и линии, несущей отрезок. 

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

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

Для работы с алгоритмом Кируса-Бэка следует убедиться, что многоугольник выпуклый. Факт выпуклости многоугольника можно определить по знаку векторного произведения его смежных сторон.

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

В общем случае, при отсечении многоугольников требуется решать два типа задач – внутреннее (отображение части изображения, попавшего в окно) и внешнее (отображение изображения, находящегося вне окна).

Листинг программы

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Linq;

using System.Text;

using System.Threading;

using System.Threading.Tasks;

using System.Windows.Forms;

namespace LR1

{

public partial class Form1 : Form

{

public Form1()

{

InitializeComponent();

}

private readonly Pen col1 = new Pen(Color.Green, 3);

private readonly Pen col2 = new Pen(Color.White, 3);

private SolidBrush col4 = new SolidBrush(Color.White);

private SolidBrush col6 = new SolidBrush(Color.Yellow);

private double[] smeshen_pravo = new double[6];

private double[] smeshen_vniz = new double[6];

private PointF[] tekushie = new PointF[6];

private PointF[] konechnie = new PointF[6];

private PointF[] vnesh = new PointF[4];

private PointF[] vnut = new PointF[4];

private int num_shag = 0;

private const int shag = 30;

private Bitmap img;

private Graphics gr;

int c = 0;

private List<PointF> vnesh_granici;

private List<PointF> vnutr_granici;

private bool button_otsech = false;

private void button1_Click(object sender, EventArgs e)

{

double Sin60 = 0.866;

img = new Bitmap(pictureBox1.Width, pictureBox1.Height);

gr = Graphics.FromImage(img);

gr.Clear(Color.White);

num_shag = 0;

tekushie = new PointF[]

{

new PointF(10, 10),

new PointF(70, 10),

new PointF(70, 70),

new PointF(10, 70),

new PointF(10, 10),

new PointF(70, 10)

};

konechnie = new PointF[]

{

new PointF(665, 425 - (int)(60*Sin60)),

new PointF(605, 425 - (int)(60*Sin60)),

new PointF(575, 425),

new PointF(605, 425 + (int)(60*Sin60)),

new PointF(665, 425 + (int)(60*Sin60)),

new PointF(695, 425),

};

float x = (float)pictureBox1.Width / 2;

float y = (float)pictureBox1.Height / 2;

PointF[] peregorodka =

{

new PointF(x, y - 30),

new PointF(x, y - 15),

new PointF(x, y - 7),

new PointF(x, y + 7),

new PointF(x, y + 15),

new PointF(x, y + 30)

};

for (int i = 0; i < 6; i++)

{

smeshen_pravo[i] = (double)(peregorodka[i].X -

tekushie[i].X) / (shag / 2);

smeshen_vniz[i] = (double)(peregorodka[i].Y –

tekushie[i].Y) / (shag / 2);

}

if (button_otsech == false)

for (int i = 0; i < 6; i++)

gr.DrawLine(col1, tekushie[i], tekushie[(i+1) % 6]);

timer1.Enabled = true;

timer2.Enabled = true;

pictureBox1.Image = img;

if (button_otsech == true)

{

gr.FillPolygon(col6, vnesh);

gr.FillPolygon(col4, vnut);

}

}

private void timer1_Tick(object sender, EventArgs e)

{

num_shag++;

if (num_shag == shag)

{

timer1.Enabled = false;

timer2.Enabled = false;

c = 0;

button_otsech = false;

}

else

{

if (regim2.Checked)

for (int i = 0; i < 6; i++)

gr.DrawLine(col2, tekushie[i], tekushie[(i+1)%6]);

if (button_otsech == true)

{

if (regim2.Checked)

{

gr.FillPolygon(col6, vnesh);

gr.FillPolygon(col4, vnut);

}

}

if (num_shag == shag / 2)

for (int i = 0; i < 6; i++)

{

smeshen_pravo[i] = (double)(konechnie[i].X –

tekushie[i].X) / (shag / 2);

smeshen_vniz[i] = (double)(konechnie[i].Y –

tekushie[i].Y) / (shag / 2);

}

for (int j = 0; j < 6; j++)

{

tekushie[j].X += (float)smeshen_pravo[j];

tekushie[j].Y += (float)smeshen_vniz[j];

}

if (button_otsech == false)

for (int i = 0; i < 6; i++)

gr.DrawLine(col1, tekushie[i], tekushie[(i+1)%6]);

if (button_otsech == true)

{

DrawWindow(vnesh_granici, gr);

DrawWindow(vnutr_granici, gr);

}

pictureBox1.Image = img;

}

}

private void timer2_Tick(object sender, EventArgs e)

{

c = c + 1;

label1.Text ="Время движения объекта "+c.ToString()+" сек.";

}

private void trackBar1_Scroll(object sender, EventArgs e)

{

timer1.Interval = trackBar1.Value;

label2.Text = "Задержка " + trackBar1.Value + " мс";

}

private void button2_Click(object sender, EventArgs e)

{

button_otsech = true;

vnesh_granici = new List<PointF>

{

new PointF(100, 420),

new PointF(100, 60),

new PointF(600, 60),

new PointF(600, 420),

};

vnutr_granici = new List<PointF>

{

new PointF(350, 60),

new PointF(600, 230),

new PointF(350, 420),

new PointF(100, 230)

};

vnesh = new PointF[]

{

new PointF(100, 420),

new PointF(100, 60),

new PointF(600, 60),

new PointF(600, 420),

};

vnut = new PointF[]

{

new PointF(350, 60),

new PointF(600, 230),

new PointF(350, 420),

new PointF(100, 230)

};

gr.FillPolygon(col6, vnesh);

gr.FillPolygon(col4, vnut);

}

private void DrawWindow(List<PointF> window, Graphics gr)

{

var lines = new List<Line>();

for (int i = 0; i < 6; i++)

{

lines.Add(new Line

{

Start = tekushie[i],

End = tekushie[(i + 1) % 6]

});

}

List<Line> drawLines = KirusBek.start(lines,

vnesh_granici);

foreach (var line in drawLines)

gr.DrawLine(col1, line.Start, line.End);

drawLines = KirusBek.start(lines, vnutr_granici);

foreach (var line in drawLines)

gr.DrawLine(col2, line.Start, line.End);

}

}

class Line

{

public PointF Start { get; set; }

public PointF End { get; set; }

}

class KirusBek

{

private static List<PointF> okno;

public static List<Line> start(List<Line> lines, List<PointF> coords)

{

List<Line> result = new List<Line>();

okno = coords;

foreach (var line in lines)

{

Line vnut_chast = Get_vnut_chast(line);

if (vnut_chast != null)

result.Add(vnut_chast);

}

return result;

}

private static Line Get_vnut_chast(Line line)

{

double t_vh = 0;

double t_vih = 1;

for (int i = 0; i < 4; i++)

{

var kray = new Line

{

Start = okno[i],

End = okno[(i + 1) % 4]

};

Vector n = normal(kray, okno[(i + 2) % 4]);

var d = new Vector(line.End.X - line.Start.X,

line.End.Y - line.Start.Y);

var w = new Vector(line.Start.X - kray.End.X,

line.Start.Y - kray.End.Y);

if (Math.Abs(d*n) < 0.0001)

if (w*n < 0)

return null;

else

continue;

double t = -(w*n)/(d*n);

if (d*n >= 0)

t_vh = t > t_vh ? t : t_vh;

else

t_vih = t < t_vih ? t : t_vih;

}

if (t_vh < t_vih)

return new Line

{

Start = Get_tochka(line, t_vh),

End = Get_tochka(line, t_vih)

};

return null;

}

private static Vector normal(Line krayLine, PointF nextPoint)

{

var kray = new Vector(krayLine.End.X - krayLine.Start.X,

krayLine.End.Y - krayLine.Start.Y);

var n = Math.Abs(kray.Y) < 0.001 ? new Vector(0, 1) : new

Vector(1, - kray.X / kray.Y);

var nextEdge = new Vector(nextPoint.X - krayLine.End.X,

nextPoint.Y - krayLine.End.Y);

if (nextEdge * n < 0)

n *= -1;

return n;

}

private static PointF Get_tochka(Line line, double t)

{

return new PointF(line.Start.X + (float)t*(line.End.X –

line.Start.X),

line.Start.Y + (float)t*(line.End.Y - line.Start.Y));

}

}

}

В режиме 2 объект движется и превращается из четырехугольника в шестиугольник. Стандартная задержка при движении составляет 300 мс. Ее можно регулировать, чтобы изменить скорость движения объекта. Также отображается время движения объекта. Начало движения объекта представлено на рисунке 1.

Рисунок 1 – Начало движения объекта