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

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

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

Физико-математический факультет Кафедра информатики и методики преподавания информатики Программирование решения задач о пересечении двух выпуклым многоугольником Допущена к защите Заведующий кафедрой_______Зенько С.И.

Курсовая работа студентки 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 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₁ = 0, count₂ = 0;

int j = 0;

for (int i = 0; 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₁++;

else

count₂++;

}

}

if (count₁ ≠ 0 && count₂ ≠ 0)

return false;

}

return true;

}

public static bool Intersection₁(Polygon Ob₁, Polygon Ob₂) // true — пересекаются, false — не пересекаются

{

int j = 0, n = 0;

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

{

j = i == Ob₁.size — 1? 0: i + 1;

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

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

{

n = k == Ob₂.size — 1? 0: k + 1;

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

return true;

}

}

return false;

}

public static Polygon Intersection (Polygon Ob₁, Polygon Ob₂)

{

List mas_T₁ = Polygon. Contains_T (Ob₁, Ob₂);

List mas_T₂ = Polygon. Intersection_T (Ob₁, Ob₂);

List mas_T₃ = Polygon. Contains_T (Ob₂, Ob₁);

var mas_T = mas_T₁.Concat (mas_T₂);

mas_T = mas_T.Concat (mas_T₃);

List 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₁, Polygon Ob₂)

{

List mas_T₁ = new List ();

List mas_T₂ = new List ();

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

mas_T₁.Add (Ob₁[i]);

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

mas_T₂.Add (Ob₂[i]);

List mas_T₃ = Polygon. Intersection_T (Ob₁, Ob₂);

var mas_T = mas_T₁.Concat (mas_T₂);

mas_T = mas_T.Concat (mas_T₃);

List mas_T_result = mas_T.ToList ();

List mas_remove₁ = Polygon. Contains_T (Ob₁, Ob₂);

List mas_remove₂ = Polygon. Contains_T (Ob₂, Ob₁);

var mas_remove = mas_remove₁.Concat (mas_remove₂);

List 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 Contains_T (Polygon Ob₁, Polygon Ob₂) // возвращает вершины многоугольника Ob₁, которые лежат в Ob₂

{

List mas_T = new List ();

int count_tmp = 0, k = 0;

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

{

count_tmp = 0;

double max_x = Polygon. max_abs (Ob₂).koord_x;

Point T₁ = Ob₁[i];

Point T₂;

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

{

k = j == Ob₂.size — 1? 0: j + 1;

Otrezok Otr₂ = new Otrezok (Ob₂[j], Ob₂[k]);

if (T₁.koord_y == Otr₂.Get_A.koord_y)

T₂ = new Point (max_x + 1, Otr₂.Get_A.koord_y — 1);

else

if (T₁.koord_y == Otr₂.Get_B.koord_y)

T₂ = new Point (max_x + 1, Otr₂.Get_B.koord_y — 1);

else

T₂ = new Point (max_x + 1, T₁.koord_y);

Otrezok Otr₁ = new Otrezok (T₁, T₂);

if (Otrezok.Intersection (Otr₁, Otr₂))

count_tmp++;

}

if (count_tmp % 2 ≠ 0)

mas_T.Add (T₁);

}

return mas_T;

}

public static List Intersection_T (Polygon Ob₁, Polygon Ob₂)

{

List mas_T = new List ();

int j = 0, n = 0;

double x, y;

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

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

{

j = i == Ob₁.size — 1? 0: i + 1;

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

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

{

n = k == Ob₂.size — 1? 0: k + 1;

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

{

Prjamaja Pr₁ = new Prjamaja (Otr.Get_A, Otr. Get_B);

Prjamaja Pr₂ = new Prjamaja (Ob₂[k], Ob₂[n]);

A1 = Pr₁.koef_a;

B1 = Pr₁.koef_b;

C1 = Pr₁.koef_c;

A2 = Pr₂.koef_a;

B2 = Pr₂.koef_b;

C2 = Pr₂.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₁, Polygon Ob₂) // true — Ob₁ содержится в Ob₂, false — Ob₁ не содержится в Ob₂

{

if (Polygon.Intersection₁(Ob₁, Ob₂))

return false;

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

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

{

count_tmp = 0;

double max_y = Polygon. max_abs (Ob₂).koord_y;

double max_x = Polygon. max_abs (Ob₂).koord_x;

Point T₁ = Ob₁[i];

Point T₂;

if (T₁.koord_y == max_y)

T₂ = new Point (max_x + 1, max_y — 1);

else

T₂ = new Point (max_x + 1, max_y);

Otrezok Otr₁ = new Otrezok (T₁, T₂);

for (int j = 0; j < Ob₂.size — 1; j++)

{

k = j + 1;

Otrezok Otr₂ = new Otrezok (Ob₂[j], Ob₂[k]);

if (Otrezok.Intersection (Otr₁, Otr₂))

count_tmp++;

}

if (count_tmp % 2 ≠ 0)

count++;

}

if (count == Ob₁.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 List_Unique (List temp_list)

{

List list = new List ();

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)

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₁, size₂;

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

size₁ = Convert. ToInt32(Console.ReadLine ());

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

size₂ = Convert. ToInt32(Console.ReadLine ());

Polygon P₁ = new Polygon (size₁);

Polygon P₂ = new Polygon (size₂);

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

P₁.Input_peaks ();

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

P₂.Input_peaks ();

Console.Clear ();

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

P₁.Show_peaks ();

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

P₂.Show_peaks ();

if (!Polygon.Is_convex (P₁) || !Polygon.Is_convex (P₂))

{

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

}

else

{

Polygon P_I = Polygon. Intersection (P₁, P₂);

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

P_I.Show_peaks ();

Polygon P_U = Polygon. Union (P₁, P₂);

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₁, Otrezok Otr₂)

{

bool flag = true;

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

x1 = Otr₁.Get_A.koord_x;

y1 = Otr₁.Get_A.koord_y;

x2 = Otr₁.Get_B.koord_x;

y2 = Otr₁.Get_B.koord_y;

x3 = Otr₂.Get_A.koord_x;

y3 = Otr₂.Get_A.koord_y;

x4 = Otr₂.Get_B.koord_x;

y4 = Otr₂.Get_B.koord_y;

double Z₁ = (x3 — x1) * (y2 — y1) — (y3 — y1) * (x2 — x1);

double Z₂ = (x4 — x1) * (y2 — y1) — (y4 — y1) * (x2 — x1);

if (Z₁ * Z₂ > 0)

flag = false;

double Z₃ = (x1 — x3) * (y4 — y3) — (y1 — y3) * (x4 — x3);

double Z₄ = (x2 — x3) * (y4 — y3) — (y2 — y3) * (x4 — x3);

if (Z₃ * Z₄ > 0)

flag = false;

if (Z₁ == 0 && Z₂ == 0)

{

flag = false;

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

{

double k₁ = Otrezok. min (x1, x2);

double k₂ = Otrezok. max (x1, x2);

double k₃ = Otrezok. min (x3, x4);

double k₄ = Otrezok. max (x3, x4);

double L_x = Otrezok. max (k₁, k₃);

double R_x = Otrezok. min (k₂, k₄);

if (L_x <= R_x)

flag = true;

}

else

{

double k₅ = Otrezok. min (y1, y2);

double k₆ = Otrezok. max (y1, y2);

double k₇ = Otrezok. min (y3, y4);

double k₈ = Otrezok. max (y3, y4);

double L_y = Otrezok. max (k₅, k₇);

double R_y = Otrezok. min (k₆, k₈);

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. Голицина О. Л., Попов И. И. Основы алгоритмизации и программирования: Учебное пособие.