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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Минск, 2015

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

Класс Polygon

using System;System.Collections.Generic;System.Linq;System.Text;System.Threading.Tasks;Планиметрия

{Polygon

{[] mas;size;Polygon(int size)

{= new Point[size];.size = size;

}Point this[int i]

{

{mas[i];

}

{[i] = value;

}

}void Input_peaks()

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

{[i] = new Point();.WriteLine("Введите координаты {0} вершины: ",i+1);[i].Input_Point();

}

}void List_Input_peaks(List<Point> list)

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

{[i] = list[i];

}

}void Show_peaks()

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

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

}

}static bool Is_convex(Polygon Ob)

{D = 0;count_1 = 0, count_2 = 0;j = 0;(int i = 0; i<Ob.size-1; i++)

{= i + 1;(int k = 0; k < Ob.size; k++)

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

{= (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);(D == 0)false;(D < 0)_1++;_2++;

}

}(count_1 != 0 && count_2 != 0)false;

}true;

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

{j = 0, n = 0;(int i = 0; i < Ob_1.size; i++)

{= i == Ob_1.size - 1 ? 0 : i + 1;Otr = new Otrezok(Ob_1[i], Ob_1[j]);(int k = 0; k < Ob_2.size - 1; k++)

{= k == Ob_2.size - 1 ? 0 : k + 1;(Otrezok.Intersection(Otr, new Otrezok(Ob_2[k], Ob_2[n])))true;

}

}false;

}static Polygon Intersection(Polygon Ob_1, Polygon Ob_2)

{<Point> mas_T_1 = Polygon.Contains_T(Ob_1, Ob_2);<Point> mas_T_2 = Polygon.Intersection_T(Ob_1, Ob_2);<Point> mas_T_3 = Polygon.Contains_T(Ob_2, Ob_1);mas_T = mas_T_1.Concat(mas_T_2);_T = mas_T.Concat(mas_T_3);<Point> result_mas = mas_T.ToList();_mas = Polygon.List_Unique(result_mas);P = new Polygon(result_mas.Count);.List_Input_peaks(result_mas);P;

}static Polygon Union(Polygon Ob_1, Polygon Ob_2)

{<Point> mas_T_1 = new List<Point>();<Point> mas_T_2 = new List<Point>();(int i = 0; i < Ob_1.size; i++)_T_1.Add(Ob_1[i]);(int i = 0; i < Ob_2.size; i++)_T_2.Add(Ob_2[i]);<Point> mas_T_3 = Polygon.Intersection_T(Ob_1, Ob_2);mas_T = mas_T_1.Concat(mas_T_2);_T = mas_T.Concat(mas_T_3);<Point> mas_T_result = mas_T.ToList();<Point> mas_remove_1 = Polygon.Contains_T(Ob_1, Ob_2);<Point> mas_remove_2 = Polygon.Contains_T(Ob_2, Ob_1);mas_remove = mas_remove_1.Concat(mas_remove_2);<Point> mas_remove_result = mas_remove.ToList();(int i = 0; i < mas_remove_result.Count; i++)_T_result.Remove(mas_remove_result[i]);_T_result = Polygon.List_Unique(mas_T_result);P = new Polygon(mas_T_result.Count);.List_Input_peaks(mas_T_result);P;

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

{<Point> mas_T = new List<Point>();count_tmp = 0, k = 0;(int i = 0; i < Ob_1.size; i++)

{_tmp = 0;max_x = Polygon.max_abs(Ob_2).koord_x;T_1 = Ob_1[i];T_2;(int j = 0; j < Ob_2.size; j++)

{= j == Ob_2.size - 1 ? 0 : j + 1;Otr_2 = new Otrezok(Ob_2[j], Ob_2[k]);(T_1.koord_y == Otr_2.Get_A.koord_y)_2 = new Point(max_x + 1, Otr_2.Get_A.koord_y - 1);(T_1.koord_y == Otr_2.Get_B.koord_y)_2 = new Point(max_x + 1, Otr_2.Get_B.koord_y - 1);_2 = new Point(max_x + 1, T_1.koord_y);Otr_1 = new Otrezok(T_1, T_2);(Otrezok.Intersection(Otr_1, Otr_2))_tmp++;

}mas_T;

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

{<Point> mas_T = new List<Point>();j = 0, n = 0;x, y;A1, B1, C1, A2, B2, C2;(int i = 0; i < Ob_1.size; i++)

{= i == Ob_1.size - 1 ? 0 : i + 1;Otr = new Otrezok(Ob_1[i], Ob_1[j]);(int k = 0; k < Ob_2.size; k++)

{= k == Ob_2.size - 1 ? 0 : k + 1;(Otrezok.Intersection(Otr, new Otrezok(Ob_2[k], Ob_2[n])))

{Pr_1 = new Prjamaja(Otr.Get_A, Otr.Get_B);Pr_2 = new Prjamaja(Ob_2[k], Ob_2[n]);= Pr_1.koef_a;= Pr_1.koef_b;= Pr_1.koef_c;= Pr_2.koef_a;= Pr_2.koef_b;= Pr_2.koef_c;= (C2 * B1 - C1 * B2) / (A1 * B2 - B1 * A2);= (C1 * A2 - A1 * C2) / (A1 * B2 - B1 * A2);_T.Add(new Point(x,y));

}

}

}mas_T;

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

{(Polygon.Intersection_1(Ob_1, Ob_2))false;count_tmp = 0, k = 0, count = 0;(int i = 0; i < Ob_1.size; i++)

{_tmp = 0;max_y = Polygon.max_abs(Ob_2).koord_y;max_x = Polygon.max_abs(Ob_2).koord_x;T_1 = Ob_1[i];T_2;(T_1.koord_y == max_y)_2 = new Point(max_x + 1, max_y - 1);_2 = new Point(max_x + 1, max_y);Otr_1 = new Otrezok(T_1, T_2);(int j = 0; j < Ob_2.size - 1; j++)

{= j + 1;Otr_2 = new Otrezok(Ob_2[j], Ob_2[k]);(Otrezok.Intersection(Otr_1, Otr_2))_tmp++;

}(count_tmp % 2 != 0)++;

}(count == Ob_1.size)true;false;

}static Point max_abs(Polygon P)

{max = P[0].koord_x;index = 0;(int i = 1; i < P.size; i++)

{(P[i].koord_x > max)

{= P[i].koord_x;= i;

}

}P[index];

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

{<Point> list = new List<Point>();.Add(temp_list[0]);flag = true;(int i = 1; i < temp_list.Count; i++ )

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

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

{= false;;

}

}(flag).Add(temp_list[i]);

}list;

}

}

}

Класс TriangleSystem;System.Collections.Generic;System.Text;Планиметрия

{Triangle : Point

{B = new Point();C = new Point();

// Конструкторы:Triangle()

{

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

reality = false;

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

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

: base(T1)

{

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

B = T2;= T3;(T1 != T2 && T2 != T3 && T1 != T3 && Storona_a + Storona_b > Storona_c && Storona_a + Storona_c > Storona_b && Storona_b + Storona_c > Storona_a)= true;= false;

}

// Конструктор копированияTriangle(Triangle Ob)

{

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

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

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

B = Ob.B;= Ob.C;= Ob.reality;

}

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

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

public override double Perimetr()

{(this.reality == false) return 0;Storona_a + Storona_b + Storona_c;

}override double area()

{(this.reality == false) return 0;p = this.Perimetr() / 2;Math.Sqrt(p * (p - Storona_a) * (p - Storona_b) * (p - Storona_c));

}string Style1()

{((Storona_a != Storona_b) && (Storona_b != Storona_c) && (Storona_a != Storona_c))"Разносторонний";((Storona_a == Storona_b) && (Storona_b == Storona_c))

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

}string Style2()

{a = Storona_a;b = Storona_b;c = Storona_c;((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))"Прямоугольный";((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 "Тупоугольный";"Остроугольный";

}bool Is_Triangle

{

{reality;

}void Show_Triangle()

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

}double Storona_a

{

{A = new Point(FigureSizes[0], FigureSizes[1]);new Otrezok(A, B).Perimetr();

}

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

}double Storona_b

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

}double Storona_c

{

{A = new Point(FigureSizes[0], FigureSizes[1]);new Otrezok(A, C).Perimetr();

}

}

}

}

Класс ProgramSystem;System.Collections.Generic;System.Text;Планиметрия

{Program

{void Main(string[] args)

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

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

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

size_2 = Convert.ToInt32(Console.ReadLine());P_1 = new Polygon(size_1);P_2 = new Polygon(size_2);

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

P_2.Input_peaks();.Clear();

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

P_2.Show_peaks();(!Polygon.Is_convex(P_1) || !Polygon.Is_convex(P_2))

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

}

{P_I = Polygon.Intersection(P_1, P_2);.WriteLine("Пересечение:");_I.Show_peaks();P_U = Polygon.Union(P_1, P_2);.WriteLine("Объединение:");_U.Show_peaks();

}.ReadKey();

}

}

}

Класс PrjamajaSystem;System.Collections.Generic;System.Text;Планиметрия

{Prjamaja : Figure

{

///Конструкторы////Prjamaja()

{= new double[3];= false;[0] = 0;[1] = 0;[2] = 0;

}Prjamaja(Point A, Point B)

{= new double[3];(A == B)

{= false;[0] = 0;[1] = 0;[2] = 0;

}

{= true;[0] = B.koord_y - A.koord_y;[1] = A.koord_x - B.koord_x;[2] = B.koord_x * A.koord_y - A.koord_x * B.koord_y;

}

}

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

{{ return FigureSizes[0]; }

}double koef_b

{{ return FigureSizes[1]; }

}double koef_c

{{ return FigureSizes[2]; }

}bool Is_prjamaja

{{ return reality; }

}

}

}

Класс PointSystem;System.Collections.Generic;System.Text;Планиметрия

{Point : Figure

{

// Конструкторы:Point()

{= true;= new double[2];[0] = 0;[1] = 0;

}Point(Point Ob)

{= true;= new double[2];[0] = Ob.FigureSizes[0];[1] = Ob.FigureSizes[1];

}Point(double x, double y)

{= true;= new double[2];[0] = x;[1] = y;

}

// Свойства:double koord_x

{

{FigureSizes[0];

{[0] = value;

}

}double koord_y

{

{FigureSizes[1];

}

{[1] = value;

}

}void Show()

{.WriteLine("x = {0:0.##} ,y = {1:0.##}",[0], FigureSizes[1]);

}void Input_Point()

{.Write("Координата x = ");[0] = Double.Parse(Console.ReadLine());.Write("Координата y = ");[1] = Double.Parse(Console.ReadLine());

}

}

}

Класс OtrezokSystem;System.Collections.Generic;System.Text;Планиметрия

{Otrezok:Point

{B = new Point();Otrezok()

{= false;

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

{(Ob1 != Ob2)= true;reality = false;= Ob2;

}Point Get_A

{{ return this; }

}Point Get_B

{{ return B; }

}

//Свойствоbool Is_Otrezok

{{ return reality; }

}override double Perimetr()

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

}static bool Intersection(Otrezok Otr_1, Otrezok Otr_2)

{flag = true;x1, y1, x2, y2, x3, y3, x4, y4;= Otr_1.Get_A.koord_x;= Otr_1.Get_A.koord_y;= Otr_1.Get_B.koord_x;= Otr_1.Get_B.koord_y;= Otr_2.Get_A.koord_x;= Otr_2.Get_A.koord_y;= Otr_2.Get_B.koord_x;= Otr_2.Get_B.koord_y;Z_1 = (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1);Z_2 = (x4 - x1) * (y2 - y1) - (y4 - y1) * (x2 - x1);(Z_1 * Z_2 > 0)= false;Z_3 = (x1 - x3) * (y4 - y3) - (y1 - y3) * (x4 - x3);Z_4 = (x2 - x3) * (y4 - y3) - (y2 - y3) * (x4 - x3);(Z_3 * Z_4 > 0)= false;(Z_1 == 0 && Z_2 == 0)

{= false;(y1 == y3 && y2 == y4)

{k_1 = Otrezok.min(x1, x2);k_2 = Otrezok.max(x1, x2);k_3 = Otrezok.min(x3, x4);k_4 = Otrezok.max(x3, x4);L_x = Otrezok.max(k_1, k_3);R_x = Otrezok.min(k_2, k_4);(L_x <= R_x)= true;

}

{k_5 = Otrezok.min(y1, y2);k_6 = Otrezok.max(y1, y2);k_7 = Otrezok.min(y3, y4);k_8 = Otrezok.max(y3, y4);L_y = Otrezok.max(k_5, k_7);R_y = Otrezok.min(k_6, k_8);(L_y <= R_y)= true;

}

}flag;

}static double min(double x, double y)

{x < y ? x : y;

}static double max(double x, double y)

{x > y ? x : y;

}

}

}

Класс FigureSystem;System.Collections.Generic;System.Text;Планиметрия

{class Figure

{double [] FigureSizes;bool reality;virtual double area()

{0.0;

}virtual double Perimetr()

{0.0;

}

}

}

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

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

В       B₁      С

A₁                           C₁

А              D₁            D

(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

(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).

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

B₁               C₁

B          C

A         D    A₁           D₁

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

B                        D₁

D                   

C₁

B                        D₁

D                   

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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