Все выпуски  

RFpro.ru: Программирование на C / C++


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Академик
Рейтинг: 8743
∙ повысить рейтинг »
Коцюрбенко Алексей aka Жерар
Статус: Профессор
Рейтинг: 3110
∙ повысить рейтинг »
Boriss
Статус: Академик
Рейтинг: 2587
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++

Номер выпуска:1705
Дата выхода:06.12.2011, 02:00
Администратор рассылки:Киселёва Алёна aka Verena (Профессор)
Подписчиков / экспертов:280 / 164
Вопросов / ответов:1 / 1

Консультация # 184637: Уважаемые эксперты! Пожалуйста, ответьте на вопрос: Доброй ночи всем! Пожалуйста, прошу помощи. Помогите пожалуйста с программой. Задание программы находится ниже в вордовском документе. Заранее большое спасибо!...


Консультация # 184637:

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Доброй ночи всем! Пожалуйста, прошу помощи. Помогите пожалуйста с программой.
Задание программы находится ниже в вордовском документе. Заранее большое спасибо!

Дата отправки: 01.12.2011, 01:27
Вопрос задал: Посетитель - 349343 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »


Консультирует Лысков Игорь Витальевич (Старший модератор):

Здравствуйте, Посетитель - 349343!
Так как точки только в сетке с шагом 1, то для хранения точек используются целые числа,
кроме точек пересечения, где использованы вещественные.
Программа вводит обязательный файл points.txt с точками и формирует файл points.log с копией информации на экране.
В файле допустимы только целые числа из интервала [0,20]
Запрашивает координаты двух точки из области [0:20,0:20], через которую проходит прямая.
После чего находит точки пересечения прямой с четвероугольником.

Код :
/*
Координаты вершин многоугольника :  (1,1)  (12,1) (10,10) (1,15)
Точки, через которые проходит прямая: (0,15) (1,18)
Набор точек:
Узлы сетки с шагом 1(0<=X<=20 и 0<=Y<=20)
Ограничение (R ) на расстояние между точками из набора точек и прямой:  4,2
Задание:
1)	Занести информацию о наборе точек в (номер точки в наборе и ее координаты) массив D1.
2)	Выбрать из набора точек все точки, лежащие внутри многоугольника и поместить полученную информацию 
    (номер точки в наборе и ее координаты) в массив D2.
3)	Вычислить расстояние r от каждой точки, занесенной в D2 до прямой. Информацию о всех точках, 
    для которых выполняется соотношение  r<=Rпоместить в массив D3, включающий в себя номер точки в D2, 
	номер точки в D1, координаты точки, расстояние от точки до прямой.
4)	Упорядочить D3 в порядке убывания r.
5)	Вывести результаты расчетов (пп.1-3) в виде таблиц на экран и в файл.

Требование к программе: 
1)	Ввод данных должен осуществляться из файла данных(набор точек) и с клавиатуры(уравнение прямой).
2)	Результаты расчета должны выводиться в виде таблиц на экран и в файл.
3)	Процедуры расчета расстояния r, выбора точек из массива D1, сортировки массива и вывод результатов 
    следует оформить в программе в форме функций пользователя.
Дополнительно:
Добавить в программу:
1)	Функцию расчета периметра и площади многоугольника.
2)	Функцию определения координат пересечения многоугольника с прямой, заданной с клавиатуры.
*/

#include	<iostream>
#include	<stdlib.h>
#include	<stdio.h>
#include	<conio.h>
#include	<math.h>

using namespace std;

//структура для хранения точки пересечения прямой с фигурой
typedef struct _FLOAT_POINT
{
	double	x;
	double	y;
}FLOAT_POINT;	

//структура для хранения точки
typedef struct _POINT
{
	int		x;
	int		y;
}POINT;	

//структура для хранения точки в массиве D2 и ее номера в массиве D1
typedef struct _COORD1
{
	int		num1;
	POINT	point;
}COORD1;

//структура для хранения точки в массиве D3, ее номеров в массивах D1 и D2 
typedef struct _COORD2
{
	int		num2;
	COORD1	Coord;
	double	r;
}COORD2;

#define	N				20	//верхняя граница области, нижняя - 0
#define	COUNT			4	//число вершин фигуры

#define LeftOriented	0	//ориентации
#define RightOriented	1

const double	EPS = 1.e-6;//для сравнения вещественных чисел на равенство

// Проверяем ориентацию вектора точки относительно вектора обхода грани
bool CheckOrientation(POINT *first, POINT *second)
{
	return (first->x*second->y - first->y*second->x)>0;	//>0 RightOriented
}

// Проверяем коллинеарность векторов
bool CheckCollinear(POINT *first, POINT *second)
{
	return first->x*second->y == first->y*second->x;
}

// Вычисляем координаты вектора относительно новой системы координат
void VectorSubstruct(POINT *from, POINT *to, POINT *res)
{
	res->x = to->x - from->x;
	res->y = to->y - from->y;
}

// Проверяем где находится точка Х относительно многогранника A с числом вершин count
// Возвращает
//-1 - вне
// 0 - на грани
// 1 - внутри
int Check(POINT *A, int count, POINT *x)
{
	POINT	AA, AX;				//временные вектора
	int		i, orientSum = 0;	//сложим все ориентации
	
	for (i=0; i<count; i++)		//по всем
	{
								//строим вектор AA = A[i] - A[i+1]
		if (i != count-1)		//кроме последней - с последующей
			VectorSubstruct(&A[i],&A[i+1],&AA);
		else					//последняя вершина с первой
			VectorSubstruct(&A[i],&A[0],&AA);
		VectorSubstruct(&A[i],x,&AX);	//строим вектор AX = A[i] - x
		//Если вектора коллинеарны - значит точка принадлежит грани
		if (CheckCollinear(&AA,&AX))
			return 0;			//на границе
								//складываем ориентации
		orientSum += CheckOrientation(&AA,&AX);
	}

	// Если все 4 ориентации векторов одинаковы (все=1 или все=0) - значит точка внутри четвероугольника
	if ((orientSum == 0) || (orientSum == 4))
		return 1;				//внутри
	else
		return -1;				//снаружи
}

//Последующие несколько функций расчитывают коэффициенты прямой Ax + Bx + C = 0
//исходя их координат двух точек
int	CalcA(POINT *line)
{
	return (line[0].y - line[1].y);
}
int	CalcB(POINT *line)
{
	return (line[1].x - line[0].x);
}
int	CalcC(POINT *line)
{
	return (line[0].y * (line[0].x - line[1].x) + line[0].x * (line[1].y - line[0].y));
}

//Расчет растоояния от точки X(x,y) до прямой, заданной двумя точками line
//r = (Ax+By+C)/sqrt(A^2+B^2)
double Distance(POINT *line, POINT *x)
{
	int		A = CalcA(line);
	int		B = CalcB(line);
	int		C = CalcC(line);

	return fabs((A*x->x + B*x->y + C)/sqrt((double)(A*A+B*B)));
}

//сортировка массива D3 методом "пузырька"
void Sort(COORD2 *d, int count)
{
	int		i, j;
	COORD2	w;

	for (i=0; i<count-1; i++)
		for (j=i+1; j<count; j++)
		{
			if (d[i].r < d[j].r)
			{
				w = d[i];
				d[i] = d[j];
				d[j] = w;
			}
		}
}

//расчет длины отрезка, заданного двумя точками
double Lenght(POINT *p1, POINT *p2)
{
	POINT pp;
	
	VectorSubstruct(p1, p2, &pp);					//разность векторов
	return (sqrt((double)(pp.x*pp.x + pp.y*pp.y)));	//длина разности
}

//расчет периметра фигуры, заданной массивом вершин и их количеством
double Perimeter(POINT *point, int count)
{
	int		i;
	double	p=0;

	for (i=0; i<count; i++)		//складываем длины отрезков
		p += (i == count-1)?Lenght(&point[i],&point[0]):Lenght(&point[i],&point[i+1]);
	
	return p;
}

//расчет площади
//разбиваем фигуру на треугольники, считаем площадь каждого по формуле Герона
//S = sqrt(p(p-a)(p-b)(p-c)), p = (a+b+c)/2
double Square(POINT *point, int count)
{
	int		i;
	double	p;
	double	s = 0;
	POINT	tr[3];				//вершины треугольника

	tr[0] = point[0];			//первая вершина одинаковая для всех
	for (i=1; i<=count-2; i++)	//разбиваем на треугольники
	{
		tr[1] = point[i];		//заполняем
		tr[2] = point[i+1];
		p = Perimeter(tr, 3) / 2;	//полупериод
								//складываем площади
		s += sqrt(p*(p-Lenght(&tr[0],&tr[1]))*
					(p-Lenght(&tr[1],&tr[2]))*
					(p-Lenght(&tr[2],&tr[0])));
	}
	return s;					//площадь всей фигуры
}

//расчет определителя матрицы 2х2
int det(int a00, int a01, int a10, int a11) 
{
	return a00 * a11 - a01 * a10;
}
 
//расчет точек пересечения линии line с max-угольной фигурой figure
//Функция возвращает число точек, сами точки - в points
//Если прямая совпадает с гранью, то возвращает -1
int intersect(POINT *figure, int max, POINT *line, FLOAT_POINT *points)
{
	int		i, j, k, z, count = 0;
	int		A1, B1, C1;				//коэффициенты уравнения прямых сторон
	int		A2 = CalcA(line);		//коэффициенты уравнения заданной прямой
	int		B2 = CalcB(line);
	int		C2 = CalcC(line);
	POINT	line1[2];
	double	x1, y1;
	
	//по всем отрезкам
	for	(i=0; i<max; i++)
	{
		if (i!=max-1)
		{
			line1[0] = figure[i];
			line1[1] = figure[i+1];
		}
		else
		{
			line1[0] = figure[i];
			line1[1] = figure[0];
		}
		A1 = CalcA(line1);			//коэффициенты уравнения прямой стороны
		B1 = CalcB(line1);
		C1 = CalcC(line1);
	
		z = det(A1, B1, A2, B2);
		if (z)						//есть пересечение с прямой
		{
									//точка пересечения
			x1 = - (double)det(C1, B1, C2, B2) / (double)z;
			y1 = - (double)det(A1, C1, A2, C2) / (double)z;
			//сначала проверим, есть ли такая точка
			for (j=0; j<count; j++)
			{	//сравнение вещественных чисел на совпадение нужно делать только так
				if ((fabs(x1 - points[j].x) < EPS) && (fabs(y1 - points[j].y) < EPS))
					break;
			}
			if (j < count)
				continue;			//нашли такую, идем на следующий отрезок
			points[count].x = x1;	//сохраним точку
			points[count].y = y1;
			//проверим, на участке отрезка ли она
			k = 0;					//признак попадания на отрезок
			//проверим концы отрезка
			if (((fabs((double)line1[0].x - x1) < EPS) && (fabs((double)line1[0].y - y1) < EPS)) || 
				((fabs((double)line1[1].x - x1) < EPS) && (fabs((double)line1[1].y - y1) < EPS)))
			{
				count++;			//да, вершина
				continue;			//идем дальше
			}
			else if (line1[0].x < line1[1].x)	//учтем порядок точек
			{						//на отрезке?
				if (((double)line1[0].x < x1) && ((double)line1[1].x > x1))
					k = 1;
			}
			else if (((double)line1[0].x > x1) && ((double)line1[1].x < x1))
				k = 1;
									//вертикальный отрезок
			else if (fabs((double)line1[0].x - x1) < EPS)
				k = 1;
			
			if (k)					//если попали по абциссе, проверим ординату
			{						//аналогично
				k = 0;
				if (line1[0].y < line1[1].y)
				{
					if (((double)line1[0].y < y1) && ((double)line1[1].y > y1))
						k = 1;
				}
				else if (((double)line1[0].y > y1) && ((double)line1[1].y < y1))
					k = 1;
				else if (fabs((double)line1[0].y - y1) < EPS)
					k = 1;
			}
			count += k;				//складываем. Если на отрезке, добавим 1
		}
		else						//определитель, равный 0, говорит о том,
		{							//что либо параллельно отрезку, либо
									//совпадает. Определимся.
			if (!det(A1, C1, A1, C1) && !det(B1, C1, B1, C1))
				return -1;			//совпадает с гранью!
		}
	}
	return	count;					//вернем число точек
}

//вводим точки из файла
int	GetFile(char *fName, POINT *points)
{
	int		i, count = 0;
	POINT	p;
	FILE	*fp = fopen(fName, "r") ;
	
	if (fp)
	{
		//в каждой строке по два числа
		while (-1 != fscanf(fp, "%d %d\n", &p.x, &p.y))
		{
			//принимаем только от 0 до N=20
			if (p.x < 0 || p.x > N || p.y < 0 || p.y > N)
				continue;
			//дубликаты пропускаем
			for (i=0; i<count; i++)
				if ((p.x == points[i].x) && (p.y == points[i].y))
					break;
			if (i != count)
				continue;		//нашли, значит пропускаем
			points[count++] = p;//сохраняем
		}
		fclose(fp);
	}
	return count;				//вернем число точек
}

//запрос целого числа с отбрасыванием всего того, что  >1000 и <-1000
int GetNum(char* str)
{
	char	line[256];
	int		a;
	do
	{
		a = -1000;
		cout << str;
		cin.getline(line, 256);
		a = atoi(line);
	}while (a <= -1000 || a > 1000);
	return a;
}

int	main()
{
	//четвероугольник
	POINT	poligon[COUNT] = {{1,1},{12,1},{10,10},{1,15}};
	//линия для расчета ближайших точек
	POINT	line[2] = {{0,15},{1,18}};
	//линия для расчета точек пересечения
	POINT	line2[2];
	//массивы для хранения точек. Максимум = числу точек в области [0,N]
	POINT	D1[(N+1)*(N+1)];
	COORD1	D2[(N+1)*(N+1)];
	COORD2	D3[(N+1)*(N+1)];
	//точки пересечения с фигурой. Их максимум 2, но задали, как число вершин
	FLOAT_POINT	inter_points[COUNT];
	char	buffer[128];
	double	r, R = 4.2;
	int		i, count;
	int		countD1, countD2, countD3;	//количество элементов в массивах
	FILE	*fp = fopen("points.log", "w") ;	//открываем файл журнала
	
	if (0 == fp)				//если ошибка, то выходим
	{
		cout << "Create file points.log error!" << endl;
		return 1;
	}
								//открываем файл данных
	if (0 == (countD1 = GetFile("points.txt", D1)))
	{							//если ошибка, то выходим!
		fclose(fp);
		cout << "File points.txt not found!" << endl;
		return 2;
	}

	//проверяем, какие из точек попадают в фигуру
	for(countD2=i=0; i<=countD1; i++)
	{
		if (1 == Check(poligon, COUNT, &D1[i]))	//учитываем только внутренние
		{
			D2[countD2].num1 = i;				//сохраняем в массиве D2
			D2[countD2++].point = D1[i];
		}
	}
	//Ищем точки, близкие к прямой line
	for(countD3=i=0; i<countD2; i++)
	{
		if ((r=Distance(line, &D2[i].point))<=R)//r <= R
		{
			D3[countD3].num2 = i;				//сохраняем в массиве D3
			D3[countD3].Coord = D2[i];
			D3[countD3++].r = r;
		}
	}
	Sort(D3, countD3);							//сортируем массив D3 по расстоянию

//выводим все результаты и на экран, и в файл
	cout << "D1:" << endl;
	fputs("D1:\n", fp);
	for(i=0; i<countD1; i++)
	{
		sprintf(buffer, "x =%3d, y =%3d\n", D1[i].x, D1[i].y);
		cout << buffer;			//на экран
		fputs(buffer, fp);		//в файл
	}

	cout << "D2:" << endl;
	fputs("D2:\n", fp);
	for(i=0; i<countD2; i++)
	{
		sprintf(buffer, "D1[%3d], x =%3d, y =%3d\n", D2[i].num1, 
			D2[i].point.x, D2[i].point.y);
		cout << buffer;
		fputs(buffer, fp);
	}

	cout << "D3:" << endl;
	fputs("D3:\n", fp);
	for(i=0; i<countD3; i++)
	{
		sprintf(buffer, "D2[%3d], D1[%3d], x =%3d, y =%3d, r =%6.3f\n", D3[i].num2, 
			D3[i].Coord.num1, D3[i].Coord.point.x, D3[i].Coord.point.y, D3[i].r);
		cout << buffer;
		fputs(buffer, fp);
	}

//периметр
	sprintf(buffer, "\nPerimeter = %7.3f\nSquare    = %7.3f\n", 
		Perimeter(poligon, COUNT), Square(poligon, COUNT));
	cout << buffer;
	fputs(buffer, fp);

//площадь
//запросим координаты двух точек
	cout << endl << "Enter line for crossing search" << endl
		 << "Enter two points:" << endl;
	line2[0].x = GetNum("X1 = ");
	line2[0].y = GetNum("Y1 = ");
	line2[1].x = GetNum("X2 = ");
	line2[1].y = GetNum("Y2 = ");
//выводим точки введенной прямой
	sprintf(buffer, "Line (%d,%d)-(%d,%d)\n", 
		line2[0].x, line2[0].y, line2[1].x, line2[1].y);
	cout << buffer;
	fputs(buffer, fp);
//ищем точки пересечения
	count = intersect(poligon, COUNT, line2, inter_points);
//выводим результат
	if (count == -1)		//прямая совпадаем с одной из граней
	{
		printf("The line coincides with one of the parties of a figure\n");
		fputs("The line coincides with one of the parties of a figure\n", fp);
	}
	else if (count == 0)	//прямая не пересекает фигуру
	{
		cout << endl << "No crossings of a line with a figure" << endl;
		fputs("\nNo crossings of a line with a figure\n", fp);
	}
	else					//точки найдены
	{
		cout << "\nCrossing of a line with a figure are: ";
		fputs("\nCrossing of a line with a figure are: ", fp);
		for (i=0; i<count; i++)
		{
			sprintf(buffer,"(%7.3f, %7.3f) ", inter_points[i].x, inter_points[i].y);
			cout << buffer;
			fputs(buffer, fp);
		}
		cout << endl;
		fputs("\n", fp);
	}
	fclose(fp);
	cout << "Press any key" << endl;
	getch();
	return 0;
}

Примерный файл points.txt
Код :
2 4
20 2
1 2
0 15
6 7
14 20
5 10
1 12
2 13
0 14
1 12
2 11

Консультировал: Лысков Игорь Витальевич (Старший модератор)
Дата отправки: 02.12.2011, 13:12
Рейтинг ответа:

НЕ одобряю 0 одобряю!


Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!



В избранное