Размещено на http://www.allbest.ru/

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

«Белорусский государственный педагогический университет имени Максима Танка»

Физико-математический факультет

Кафедра информатики и методики преподавания информатики

Программирование решения задач о пересечении двух выпуклым многоугольником

Допущена к защите

Заведующий кафедрой_______Зенько С.И.

Курсовая работа

студентки 302 группы 3 курса специальности «Математика. Информатика»

дневной формы

получения образования

_______________ Витько Марии Игоревны

Научный руководитель,

доктор физико-математических наук, профессор _________В.М. Котов

Минск, 2015



ВВЕДЕНИЕ

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

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

Цель моей работы заключаеться в том, чтобы показать как решить геометрическую задачу «О пересечеии двух выпуклым многоугольников» на языке программирования С#.

Курсовая работа состоит из четырех глав. В первой главе рассказываеться про алгоритм решения задач,во-второй реализация алгоритма на языке программирования,в-третей представлены тесты для проверки и в четветой графическое представление решение задачи.



ГЛАВА 1. Разработка алгоритма решения задачи

Ребром называется направленный отрезок или кривая. Ребро, начинающееся в точка a и заканчивающееся в точке b обозначается как E(a, b).

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

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

Входными данными для алгоритма являются два полигона. Каждый из них - набор не пересекающихся контуров. Включение или исключение внутренней части контура задается направлением обхода его ребер (по часовой - исключение, против часовой - включение).

Наложим исходные полигоны друг на друга. Форма исходных полигонов и способ наложения подобраны так, чтобы отразить большую часть возможных вариантов взаимного расположения ребер двух полигонов.
Найдем все точки пересечения и объединения двух полигонов.



ГЛАВА 2. Реализация разработанного алгоритма на языке программирования

Задача: Найти пересечение и объединение двух выпуклым многоугольником. Многоугольники задаются координатами вершин в порядке обхода по контуру.

Класс Polygon

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Планиметрия

{

class Polygon

{

Point[] mas;

int size;

public Polygon(int size)

{

mas = new Point[size];

this.size = size;

}

public Point this[int i]

{

get

{

return mas[i];

}

set

{

mas[i] = value;

}

}

public void Input_peaks()

{

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

{

mas[i] = new Point();

Console.WriteLine("Введите координаты {0} вершины: ",i+1);

mas[i].Input_Point();

}

}

public void List_Input_peaks(List<Point> list)

{

for (int i = 0; i < list.Count; i++)

{

mas[i] = list[i];

}

}

public void Show_peaks()

{

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

{

Console.Write("Вершина {0}: ",(i + 1));

mas[i].Show();

}

}

public static bool Is_convex(Polygon Ob)

{

double D = 0;

int count_1 = 0, count_2 = 0;

int j = 0;

for (int i = 0; i<Ob.size-1; i++)

{

j = i + 1;

for (int k = 0; k < Ob.size; k++)

{

if (k!=i && k!=j)

{

D = (Ob.mas[k].koord_x - Ob.mas[i].koord_x) * (Ob.mas[j].koord_y - Ob.mas[i].koord_y) - (Ob.mas[k].koord_y - Ob.mas[i].koord_y) * (Ob.mas[j].koord_x - Ob.mas[i].koord_x);

if (D == 0)

return false;

else

if (D < 0)

count_1++;

else

count_2++;

}

}

if (count_1 != 0 && count_2 != 0)

return false;

}

return true;

}

public static bool Intersection_1(Polygon Ob_1, Polygon Ob_2) // true - пересекаются, false - не пересекаются

{

int j = 0, n = 0;

for (int i = 0; i < Ob_1.size; i++)

{

j = i == Ob_1.size - 1 ? 0 : i + 1;

Otrezok Otr = new Otrezok(Ob_1[i], Ob_1[j]);

for (int k = 0; k < Ob_2.size - 1; k++)

{

n = k == Ob_2.size - 1 ? 0 : k + 1;

if (Otrezok.Intersection(Otr, new Otrezok(Ob_2[k], Ob_2[n])))

return true;

}

}

return false;

}

public static Polygon Intersection(Polygon Ob_1, Polygon Ob_2)

{

List<Point> mas_T_1 = Polygon.Contains_T(Ob_1, Ob_2);

List<Point> mas_T_2 = Polygon.Intersection_T(Ob_1, Ob_2);

List<Point> mas_T_3 = Polygon.Contains_T(Ob_2, Ob_1);

var mas_T = mas_T_1.Concat(mas_T_2);

mas_T = mas_T.Concat(mas_T_3);

List<Point> result_mas = mas_T.ToList();

result_mas = Polygon.List_Unique(result_mas);

Polygon P = new Polygon(result_mas.Count);

P.List_Input_peaks(result_mas);

return P;

}

public static Polygon Union(Polygon Ob_1, Polygon Ob_2)

{

List<Point> mas_T_1 = new List<Point>();

List<Point> mas_T_2 = new List<Point>();

for (int i = 0; i < Ob_1.size; i++)

mas_T_1.Add(Ob_1[i]);

for (int i = 0; i < Ob_2.size; i++)

mas_T_2.Add(Ob_2[i]);

List<Point> mas_T_3 = Polygon.Intersection_T(Ob_1, Ob_2);

var mas_T = mas_T_1.Concat(mas_T_2);

mas_T = mas_T.Concat(mas_T_3);

List<Point> mas_T_result = mas_T.ToList();

List<Point> mas_remove_1 = Polygon.Contains_T(Ob_1, Ob_2);

List<Point> mas_remove_2 = Polygon.Contains_T(Ob_2, Ob_1);

var mas_remove = mas_remove_1.Concat(mas_remove_2);

List<Point> mas_remove_result = mas_remove.ToList();

for (int i = 0; i < mas_remove_result.Count; i++)

mas_T_result.Remove(mas_remove_result[i]);

mas_T_result = Polygon.List_Unique(mas_T_result);

Polygon P = new Polygon(mas_T_result.Count);

P.List_Input_peaks(mas_T_result);

return P;

}

public static List<Point> Contains_T(Polygon Ob_1, Polygon Ob_2) // возвращает вершины многоугольника Ob_1, которые лежат в Ob_2

{

List<Point> mas_T = new List<Point>();

int count_tmp = 0, k = 0;

for (int i = 0; i < Ob_1.size; i++)

{

count_tmp = 0;

double max_x = Polygon.max_abs(Ob_2).koord_x;

Point T_1 = Ob_1[i];

Point T_2;

for (int j = 0; j < Ob_2.size; j++)

{

k = j == Ob_2.size - 1 ? 0 : j + 1;

Otrezok Otr_2 = new Otrezok(Ob_2[j], Ob_2[k]);

if (T_1.koord_y == Otr_2.Get_A.koord_y)

T_2 = new Point(max_x + 1, Otr_2.Get_A.koord_y - 1);

else

if (T_1.koord_y == Otr_2.Get_B.koord_y)

T_2 = new Point(max_x + 1, Otr_2.Get_B.koord_y - 1);

else

T_2 = new Point(max_x + 1, T_1.koord_y);

Otrezok Otr_1 = new Otrezok(T_1, T_2);

if (Otrezok.Intersection(Otr_1, Otr_2))

count_tmp++;

}

if (count_tmp % 2 != 0)

mas_T.Add(T_1);

}

return mas_T;

}

public static List<Point> Intersection_T(Polygon Ob_1, Polygon Ob_2)

{

List<Point> mas_T = new List<Point>();

int j = 0, n = 0;

double x, y;

double A1, B1, C1, A2, B2, C2;

for (int i = 0; i < Ob_1.size; i++)

{

j = i == Ob_1.size - 1 ? 0 : i + 1;

Otrezok Otr = new Otrezok(Ob_1[i], Ob_1[j]);

for (int k = 0; k < Ob_2.size; k++)

{

n = k == Ob_2.size - 1 ? 0 : k + 1;

if (Otrezok.Intersection(Otr, new Otrezok(Ob_2[k], Ob_2[n])))

{

Prjamaja Pr_1 = new Prjamaja(Otr.Get_A, Otr.Get_B);

Prjamaja Pr_2 = new Prjamaja(Ob_2[k], Ob_2[n]);

A1 = Pr_1.koef_a;

B1 = Pr_1.koef_b;

C1 = Pr_1.koef_c;

A2 = Pr_2.koef_a;

B2 = Pr_2.koef_b;

C2 = Pr_2.koef_c;

x = (C2 * B1 - C1 * B2) / (A1 * B2 - B1 * A2);

y = (C1 * A2 - A1 * C2) / (A1 * B2 - B1 * A2);

mas_T.Add(new Point(x,y));

}

}

}

return mas_T;

}

public static bool Contains(Polygon Ob_1, Polygon Ob_2) // true - Ob_1 содержится в Ob_2, false - Ob_1 не содержится в Ob_2

{

if (Polygon.Intersection_1(Ob_1, Ob_2))

return false;

int count_tmp = 0, k = 0, count = 0;

for (int i = 0; i < Ob_1.size; i++)

{

count_tmp = 0;

double max_y = Polygon.max_abs(Ob_2).koord_y;

double max_x = Polygon.max_abs(Ob_2).koord_x;

Point T_1 = Ob_1[i];

Point T_2;

if (T_1.koord_y == max_y)

T_2 = new Point(max_x + 1, max_y - 1);

else

T_2 = new Point(max_x + 1, max_y);

Otrezok Otr_1 = new Otrezok(T_1, T_2);

for (int j = 0; j < Ob_2.size - 1; j++)

{

k = j + 1;

Otrezok Otr_2 = new Otrezok(Ob_2[j], Ob_2[k]);

if (Otrezok.Intersection(Otr_1, Otr_2))

count_tmp++;

}

if (count_tmp % 2 != 0)

count++;

}

if (count == Ob_1.size)

return true;

else

return false;

}

private static Point max_abs(Polygon P)

{

double max = P[0].koord_x;

int index = 0;

for (int i = 1; i < P.size; i++)

{

if (P[i].koord_x > max)

{

max = P[i].koord_x;

index = i;

}

}

return P[index];

}

private static List<Point> List_Unique(List<Point> temp_list)

{

List<Point> list = new List<Point>();

list.Add(temp_list[0]);

bool flag = true;

for (int i = 1; i < temp_list.Count; i++ )

{

flag = true;

for (int j = 0; j < list.Count; j++)

{

if (list[j].koord_x == temp_list[i].koord_x && list[j].koord_y == temp_list[i].koord_y)

{

flag = false;

break;

}

}

if (flag)

list.Add(temp_list[i]);

}

return list;

}

}

}

Класс Triangle

using System;

using System.Collections.Generic;

using System.Text;

namespace Планиметрия

{

class Triangle : Point

{

Point B = new Point();

Point C = new Point();

// Конструкторы:

public Triangle()

{

//Console.WriteLine("Работает конструктор класса Triangle без параметров");

reality = false;

///////reality отвечает за существование объекта

}

public Triangle(Point T1, Point T2, Point T3)

: base(T1)

{

//Console.WriteLine("Работает конструктор класса Triangle с 3-мя параметрами");

B = T2;

C = T3;

if (T1 != T2 && T2 != T3 && T1 != T3 && Storona_a + Storona_b > Storona_c && Storona_a + Storona_c > Storona_b && Storona_b + Storona_c > Storona_a)

reality = true;

else

reality = false;

}

// Конструктор копирования

public Triangle(Triangle Ob)

{

//Console.WriteLine("Работает конструктор-копировщик класса Triangle");

this.FigureSizes[0] = Ob.FigureSizes[0];

this.FigureSizes[1] = Ob.FigureSizes[1];

///// FigureSizes[0] берется из базового класса, т.к тут только 2е точки есть

B = Ob.B;

C = Ob.C;

reality = Ob.reality;

}

// переопределение методов базового класса

// Безопасный код! Если треугольник не существует, его периметр и площадь равны 0.

public override double Perimetr()

{

if (this.reality == false) return 0;

return Storona_a + Storona_b + Storona_c;

}

public override double area()

{

if (this.reality == false) return 0;

double p = this.Perimetr() / 2;

return Math.Sqrt(p * (p - Storona_a) * (p - Storona_b) * (p - Storona_c));

}

public string Style1()

{

if ((Storona_a != Storona_b) && (Storona_b != Storona_c) && (Storona_a != Storona_c))

return "Разносторонний";

else

if ((Storona_a == Storona_b) && (Storona_b == Storona_c))

return "Равностороний";

else

return "Равнобедренный";

}

public string Style2()

{

double a = Storona_a;

double b = Storona_b;

double c = Storona_c;

if ((Math.Pow(a, 2) + Math.Pow(b, 2) > Math.Pow(c, 2) - 0.001 && Math.Pow(a, 2) + Math.Pow(b, 2) < Math.Pow(c, 2) + 0.001)

|| (Math.Pow(a, 2) + Math.Pow(c, 2) > Math.Pow(b, 2) - 0.001 && Math.Pow(a, 2) + Math.Pow(c, 2) < Math.Pow(b, 2) + 0.001)

|| (Math.Pow(c, 2) + Math.Pow(b, 2) > Math.Pow(a, 2) - 0.001 && Math.Pow(c, 2) + Math.Pow(b, 2) < Math.Pow(a, 2) + 0.001))

return "Прямоугольный";

else

if ((a * a + b * b - c * c) / (2 * a * b) < 0 || (a * a + c * c - b * b) / (2 * a * c) < 0 || (c * c + b * b - a * a) / (2 * c * b) < 0)

return "Тупоугольный";

else

return "Остроугольный";

}

public bool Is_Triangle

{

get

{

return reality;

}

}

public void Show_Triangle()

{

Console.WriteLine("Сторона a={0:#.##},сторона b={1:#.##},сторона c={2:#.##}", Storona_a, Storona_b, Storona_c);

}

public double Storona_a

{

get

{

Point A = new Point(FigureSizes[0], FigureSizes[1]);

return new Otrezok(A, B).Perimetr();

}

/////set нету т.к фигуру изсенить нельзя

}

public double Storona_b

{

get { return new Otrezok(C, B).Perimetr(); }

}

public double Storona_c

{

get

{

Point A = new Point(FigureSizes[0], FigureSizes[1]);

return new Otrezok(A, C).Perimetr();

}

}

}

}

Класс Program

using System;

using System.Collections.Generic;

using System.Text;

namespace Планиметрия

{

class Program

{

static void Main(string[] args)

{

int size_1, size_2;

Console.WriteLine("Введите количество вершин в первом многоугольнике:");

size_1 = Convert.ToInt32(Console.ReadLine());

Console.WriteLine("Введите количество вершин во втором многоугольнике:");

size_2 = Convert.ToInt32(Console.ReadLine());

Polygon P_1 = new Polygon(size_1);

Polygon P_2 = new Polygon(size_2);

Console.WriteLine("Введите координаты вершин первого многоугольника:");

P_1.Input_peaks();

Console.WriteLine("Введите координаты вершин второго многоугольника:");

P_2.Input_peaks();

Console.Clear();

Console.WriteLine("Координаты вершин первого многоугольника:");

P_1.Show_peaks();

Console.WriteLine("Координаты вершин второго многоугольника:");

P_2.Show_peaks();

if (!Polygon.Is_convex(P_1) || !Polygon.Is_convex(P_2))

{

Console.WriteLine("Один из многоугольников не является выпуклым!");

}

else

{

Polygon P_I = Polygon.Intersection(P_1, P_2);

Console.WriteLine("Пересечение:");

P_I.Show_peaks();

Polygon P_U = Polygon.Union(P_1, P_2);

Console.WriteLine("Объединение:");

P_U.Show_peaks();

}

Console.ReadKey();

}

}

}

Класс Prjamaja

using System;

using System.Collections.Generic;

using System.Text;

namespace Планиметрия

{

class Prjamaja : Figure

{

///Конструкторы////

public Prjamaja()

{

FigureSizes = new double[3];

reality = false;

FigureSizes[0] = 0;

FigureSizes[1] = 0;

FigureSizes[2] = 0;

}

public Prjamaja(Point A, Point B)

{

FigureSizes = new double[3];

if (A == B)

{

reality = false;

FigureSizes[0] = 0;

FigureSizes[1] = 0;

FigureSizes[2] = 0;

}

else

{

reality = true;

FigureSizes[0] = B.koord_y - A.koord_y;

FigureSizes[1] = A.koord_x - B.koord_x;

FigureSizes[2] = B.koord_x * A.koord_y - A.koord_x * B.koord_y;

}

}

///////Свойства/////////

public double koef_a

{

get { return FigureSizes[0]; }

}

public double koef_b

{

get { return FigureSizes[1]; }

}

public double koef_c

{

get { return FigureSizes[2]; }

}

public bool Is_prjamaja

{

get { return reality; }

}

}

}

Класс Point

using System;

using System.Collections.Generic;

using System.Text;

namespace Планиметрия

{

class Point : Figure

{

// Конструкторы:

public Point()

{

reality = true;

FigureSizes = new double[2];

FigureSizes[0] = 0;

FigureSizes[1] = 0;

}

public Point(Point Ob)

{

reality = true;

FigureSizes = new double[2];

FigureSizes[0] = Ob.FigureSizes[0];

FigureSizes[1] = Ob.FigureSizes[1];

}

public Point(double x, double y)

{

reality = true;

FigureSizes = new double[2];

FigureSizes[0] = x;

FigureSizes[1] = y;

}

// Свойства:

public double koord_x

{

get

{

return FigureSizes[0];

}

set

{

FigureSizes[0] = value;

}

}

public double koord_y

{

get

{

return FigureSizes[1];

}

set

{

FigureSizes[1] = value;

}

}

public void Show()

{

Console.WriteLine("x = {0:0.##} ,y = {1:0.##}",

FigureSizes[0], FigureSizes[1]);

}

public void Input_Point()

{

Console.Write("Координата x = ");

FigureSizes[0] = Double.Parse(Console.ReadLine());

Console.Write("Координата y = ");

FigureSizes[1] = Double.Parse(Console.ReadLine());

}

}

}

Класс Otrezok

using System;

using System.Collections.Generic;

using System.Text;

namespace Планиметрия

{

class Otrezok:Point

{

Point B = new Point();

public Otrezok()

{

reality = false;

}

public Otrezok(Point Ob1, Point Ob2):base(Ob1)

{

if (Ob1 != Ob2)

reality = true;

else reality = false;

B = Ob2;

}

public Point Get_A

{

get { return this; }

}

public Point Get_B

{

get { return B; }

}

//Свойство

public bool Is_Otrezok

{

get { return reality; }

}

public override double Perimetr()

{

return Math.Sqrt(Math.Pow(B.koord_x - this.koord_x, 2) + Math.Pow(B.koord_y - this.koord_y, 2));

}

public static bool Intersection(Otrezok Otr_1, Otrezok Otr_2)

{

bool flag = true;

double x1, y1, x2, y2, x3, y3, x4, y4;

x1 = Otr_1.Get_A.koord_x;

y1 = Otr_1.Get_A.koord_y;

x2 = Otr_1.Get_B.koord_x;

y2 = Otr_1.Get_B.koord_y;

x3 = Otr_2.Get_A.koord_x;

y3 = Otr_2.Get_A.koord_y;

x4 = Otr_2.Get_B.koord_x;

y4 = Otr_2.Get_B.koord_y;

double Z_1 = (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1);

double Z_2 = (x4 - x1) * (y2 - y1) - (y4 - y1) * (x2 - x1);

if (Z_1 * Z_2 > 0)

flag = false;

double Z_3 = (x1 - x3) * (y4 - y3) - (y1 - y3) * (x4 - x3);

double Z_4 = (x2 - x3) * (y4 - y3) - (y2 - y3) * (x4 - x3);

if (Z_3 * Z_4 > 0)

flag = false;

if (Z_1 == 0 && Z_2 == 0)

{

flag = false;

if (y1 == y3 && y2 == y4)

{

double k_1 = Otrezok.min(x1, x2);

double k_2 = Otrezok.max(x1, x2);

double k_3 = Otrezok.min(x3, x4);

double k_4 = Otrezok.max(x3, x4);

double L_x = Otrezok.max(k_1, k_3);

double R_x = Otrezok.min(k_2, k_4);

if (L_x <= R_x)

flag = true;

}

else

{

double k_5 = Otrezok.min(y1, y2);

double k_6 = Otrezok.max(y1, y2);

double k_7 = Otrezok.min(y3, y4);

double k_8 = Otrezok.max(y3, y4);

double L_y = Otrezok.max(k_5, k_7);

double R_y = Otrezok.min(k_6, k_8);

if (L_y <= R_y)

flag = true;

}

}

return flag;

}

private static double min(double x, double y)

{

return x < y ? x : y;

}

private static double max(double x, double y)

{

return x > y ? x : y;

}

}

}

Класс Figure

using System;

using System.Collections.Generic;

using System.Text;

namespace Планиметрия

{

abstract class Figure

{

protected double [] FigureSizes;

protected bool reality;

public virtual double area()

{

return 0.0;

}

public virtual double Perimetr()

{

return 0.0;

}

}

}

ГЛАВА 3. Тесты для проверки работы программы

1). Проверить, если первый многоугольник находиться внутри второго многоугольника и его вершины принадлежат сторонам второго.



В B₁ С

A₁ C₁

А D₁ D

A(2,2); B(2,6); C(6,6); D(6,2); A₁(2,4); B₁(4,6); C₁(6,4); D₁(4,2)

2). Проверить, если один многоугольник находится внутри другого.

С D

В E

А F

Q G

A(2,4); B(2,6); C(4,8); D(6,8); E(8,6); F(8,4); G(6,2); Q(4,2); A₁(4,4);B₁(4,6);C₁(6,6);D₁(6,4).



3). Проверить, если они не пересекаются.

B₁ C₁

B C

A D A₁ D₁

A(1,1); B(1,3); C(3,3); D(3,1), A₁(4,1); B₁(4,4); C₁(6,4);D₁(6,1)

ГЛАВА 4. Графическая иллюстрация решения задачи

C₁

B D₁

D

C₁

B D₁

D



ЗАКЛЮЧЕНИЕ

программа решение задача многоугольник

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

Чтобы реализовать цель, мы выбрали задачу «О пересечении выпуклых многоугольников» и изучили суть вычислительной геометрии и способы алгоритмизации.

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

Иинструментальной средой разработки программ стала MS Visual Studio 2010.



СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Котов В.М. Информатика. алгоритмизации. Учебное пособие 9 класса.

2.Андреева Е.В. Вычислительная геометрия на плоскости.

3. Голицина О. Л., Попов И. И. Основы алгоритмизации и программирования: Учебное пособие.

Размещено на Allbest.ru