Программирование и основы алгоритмизации

Составление математической модели для определения местоположения точки относительно многоугольника. Оформление процедуры расчета расстояния, выбора точек из массива, сортировки массива и вывода результатов в программе в форме функций пользователя.
Краткое сожержание материала:

Размещено на

Министерство образования и науки Российской Федерации

Санкт-Петербургский государственный электротехнический университет "ЛЭТИ"

Кафедра: КСУ

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

"Программирование и основы алгоритмизации"

Студент: Моисеева О.И.

Группа: 1491

Преподаватель: Ветчинкин А. С.

Санкт-Петербург, 2012 год



Постановка задачи и математическая модель задачи

математический модель программа пользователь

Постановка задачи:

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

2. Результаты расчета должны выводиться в виде таблиц на экран и в файл, сохраняясь на жёстком диске.

3. Процедуры расчета расстояния r, выбора точек из массива D1, сортировки массива и вывода результатов следует оформить в программе в форме функций пользователя.

Математическая модель:

Для определения местоположения точки относительно многоугольника проводим вертикальную линию параллельную оси ординат через заданную точку. Определяем точки пересечения со сторонами многоугольника. Если точка пересечения по координате х лежит между двумя соответствующими точками У на многоугольнике, то фиксируем это. Проделываем данную операцию и с остальными точками.

Если точек пересечения между двумя соответствующими вершинами менее 2 и заданная точка по координате y находится не между двумя другими точками, то точка находится вне многоугольника.

Kbc и Bbc - угловой коэффициент и свободный член уравнения прямой, проведенной через вершины многоугольника B и С.

Аналогично этому: Kcd и Bcd, Kad и Bad, Kab и Bab.

Во избежание деления на ноль используется число 0.0001.

На точность вычислений оно не влияет, т.к. очень мало.

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

Используется формула: Она путем преобразований получена из стандартной математической формулы для вычисления расстояний.

Для сортировки массива по убыванию используется метод простого перебора. Предполагается, что первое значение - максимальное. После чего сравниваются с соседними элементами. После одной итерации мы получаем действительно максимальное значение по всему массиву. Данное значение переносится в первую ячейку массива.

Аналогично максимальные значения из оставшихся значений переносятся в ячейку 2,3...n...

#include "stdafx.h"

#include<stdio.h>

#include<conio.h>

#include<math.h>

#include<string.h>

#include<stdlib.h>

#include<ctype.h>

FILE *file1;

FILE *file2;

int vnutri_ili_snaruji (float Ax, float Bx, float Cx, float Dx, float Ay, float By, float Cy, float Dy, float x, float y)

{

int vnutri=0, z=0;

float y1, y2, y3, y4;

float massiv[4];

float Kbc, Bbc, Kcd, Bcd, Kad, Bad, Kab, Bab;

Kbc=(By-Cy)/(Bx-Cx+0.0001); //коэффициенты в ур-ие прямой

Bbc=By-Kbc*Bx;

Kcd=(Dy-Cy)/(Dx-Cx+0.0001);

Bcd=Cy-Kcd*Cx;

Kad=(Dy-Ay)/(Dx-Ax+0.0001);

Bad=Ay-Kad*Ax;

Kab=(By-Ay)/(Bx-Ax+0.0001);

Bab=Ay-Kab*Ax;

y1=Kab*x+Bab; //Находим точки пересечения со сторонами многогранника

y2=Kbc*x+Bbc;

y3=Kcd*x+Bcd;

y4=Kad*x+Bad;

if ((y1>Ay && y1<By) || (y1<Ay && y1>By)) //Подсчёт точек пересечения параллельной прямой

{

massiv[z]=y1;

z++;

}

if ((y2>Cy && y2<By) || (y2<Cy && y2>By))

{

massiv[z]=y2;

z++;

}

if ((y3>Cy && y3<Dy) || (y3<Cy && y3>Dy))

{

massiv[z]=y3;

z++;

}

if ((y4>Ay && y4<Dy) || (y4<Ay && y4>Dy))

{

massiv[z]=y4;

z++;

}

if (z==2) //Проверка условия внутри многоугольника

{

if (y<massiv[0] && y>massiv[1]) vnutri=1;

if (y>massiv[0] && y<massiv[1]) vnutri=1;

}

return(vnutri);

}

float rasstoyanie (float x, float y, float k, float b)

{

float d;

d=(fabs(k*x-y+b)/sqrt(k*k+1)); //рассчёт расстояния от точки до прямой

return(d);

}

float sortirovka(float Sort[], float D3[250][6], int n)//Использование метода простого перебора

{

int i=0,k=0,nomer, j, j3=0, i3;

float max, perv;

float temp, temp1, temp2, temp3, temp4, temp5;

do //Сортировка значений r

{

max=Sort[i];

nomer=i;

do

{

if (Sort[i+1]>max) nomer=i+1;

if (Sort[i+1]>max) max=Sort[i+1];

i++;

}

while(i<n-1);

perv=Sort[k];

Sort[k]=max;

Sort[nomer]=perv;

k++;

i=k;

}

while(k<n-1);

for(j=0;j<n;j++) //Подстановка строк по значению r

{

for(i3=0;i3<n;i3++)

{

if (Sort[j]==D3[i3][j3+5])

{

temp=D3[j][j3];

temp1=D3[j][j3+1];

temp2=D3[j][j3+2];

temp3=D3[j][j3+3];

temp4=D3[j][j3+4];

temp5=D3[j][j3+5];

D3[j][j3]=D3[i3][j3];

D3[j][j3+1]=D3[i3][j3+1];

D3[j][j3+2]=D3[i3][j3+2];

D3[j][j3+3]=D3[i3][j3+3];

D3[j][j3+4]=D3[i3][j3+4];

D3[j][j3+5]=D3[i3][j3+5];

D3[i3][j3]=temp;

D3[i3][j3+1]=temp1;

D3[i3][j3+2]=temp2;

D3[i3][j3+3]=temp3;

D3[i3][j3+4]=temp4;

D3[i3][j3+5]=temp5;

break;

}

}

}

return(0);

}

void vyvod(float Massiv[250][6], int stroki, int stolbcy)

{

int i,j,k;

if(stolbcy==6)

{

k=1;

}

else

{

k=0;

}

for(i=0; i<stroki; i++)

{

if((i%20)==0)

{

getch();

}

for(j=k; j<stolbcy; j++)

{

switch(stolbcy)

{

case 6:

{

switch(j)

{

case 1:

printf("D2=");

break;

case 2:

printf("D1=");

break;

case 3:

printf("x=");

break;

case 4:

printf("y=");

break;

case 5:

printf("d=");

break;

}

break;

}

case 3:

{

switch(j)

{

case 0:

printf("D1=");

break;

case 1:

printf("x=");

break;

case 2:

printf("y=");

break;

}

break;

}

case 4:

{

switch(j)

{

case 0:

printf("D2=");

break;

case 1:

printf("D1=");

break;

case 2:

printf("x=");

break;

case 3:

printf("y=");

break;