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

program_field.jpg

Заданно множество прямых на плоскости ( коэффициентами своих уравнений).­ Подсчитать количество точек пересечения этих прямых.

Реализовано под Linux на Си с использованием библиотеки GTK.
Среда разработки: Code::Blocks 8.02 (Linux).
Содержание архива:
main.c - исходный код
lines.txt - текстовый файл содержащий количество прямых и коэффициенты их уравнений в виде "k b" (для уравнений вида y=kx+b)
result.txt - текстовый файл в который заносится вся информация о работе программы
a.out - исполнимый файл (создан с помощью консольной команды: gcc `pkg-config --cflags --libs gtk+-2.0` main.c) при простом запуске отсутствует консоль, что бы увидеть ее необходимо в командной строке написать ./a.out
lines.zip - архив содержащий весь проект Code::Blocks

Для решения данной задачи используем пользовательский тип данных - структуру - а именно "точка пересечения" и "список точек пересечения", после прочтения из файла всей необходимой информации путем перебора пар прямых находятся их точки пересечения (если таковые имеются) и производится их добавление в список (одни и те же точки повторно не добавляются) - число элементов в списке и есть аналитическим решением данной задачи. Все аналитические выкладки заносятся в файл с результатами. Графическое решение получаем путем изображения всех данных прямых и всех точек пересечения этих прямых. Область отображения подбирается таким образом что бы все точки попали в нее.

#include <stdio.h>
#include <stdlib.h>
#include <gtk/gtk.h>
 
//начальные области отображения
float min[2]={ 0.0, 0.0};//левый нижний угол
float max[2]={ 0.0, 0.0};//правый верхний угол
 
unsigned int N; //число прямых - считывается из файла
 
double **lines; //двумерный массив соответствующий коэфиициентам "k" и "b" уравнений y=kx+b
 
typedef struct cp cp; //структура типа: точка пересечения (cp от CrossPoint)
 
struct cp
{
	float x;
	float y;
	cp *next;
};
 
typedef struct cpl cpl; //структура типа: список точек пересечения (cpl от CrossPointsList)
 
struct cpl
{
	int count;
	cp *head, *tail;
};
 
void initlist(cpl * l) //функция инициализацнии списка
{
	l->count=0;
	l->head=l->tail=NULL;
}
 
void addcp(cpl * l,cp * p) //функция добавления новой точки в список
{
	if((l->count)==0)
	{
		l->head=l->tail=p;
		l->count=1;
		l->tail->next=NULL;
	}
	else
	{
		l->tail->next=p;
		l->tail=p;
		l->count++;
		l->tail->next=NULL;
	}
}
 
cp * find (cpl *l, float x, float y) //функция поиска вхождения точки в список точек по координатам
{
	cp *temp;
	temp=l->head;
	while((temp!=NULL)&&(temp->x!=x || temp->y!=y))
		temp=temp->next;
	return temp;
}
 
void dlist(cpl *l) //функция удаляющая список
{
    cp *temp1;
    cp *temp2;
    temp1=temp2=l->head;
    while (temp2!=NULL)
    {
        temp1=temp2;
        temp2=temp2->next;
        free(temp1);
    }
}
 
void calc(cpl *l) //основная расчетная функция
{
    //В данной функции происходит пстроение списка точек пересечения путем перебора пар прямых и нахождения их точек пересечения
    FILE *out; //файл содержащий полные описания выполнимых действий
	out = fopen("./result.txt", "wt");
	if(out == NULL)
	{
	    g_print("Error with openning output file, output only in concole");
    }
    //все g_print() использоваолись при отладке программы и выводят необходимую информациeю в консоль
	g_print("Calc start\n");
	g_print("Output zone cheak: from (%2.1f;%2.1f) to (%2.1f;%2.1f))\n",min[0],min[1],max[0],max[1]);
	//все fprintf() fиспользуются для записи в файл result.txt всех производимых действий и несут исключительно информативный характер
	fprintf(out, "Начальная область отображения:\n\t\t(%2.1f;%2.1f)\n\t\t(%2.1f;%2.1f)\n", min[0],min[1],max[0],max[1]);
	g_print("Initlist\n");
    fprintf(out,"Вычислительный цикл, перебор прямых с последющим нахождением точек пересечения\n");
	cp *p;
	int num=1;//переменная которая несёт информативный характер, показывая количество проверок - выводится в консоли
 
	int i,j;
	for(i=0;i<N-1;i++) //двойной цикл для перебода всех прямых
        {
        fprintf (out, "Прямая: y=(%2.1f)x+(%2.1f)\n",lines[i][0],lines[i][1]);
		for(j=1;j<N-i;j++)
		{
		    fprintf (out, "\tПроверка на пересечение  с прямой: y=(%2.1f)x+(%2.1f)\n",lines[i+j][0],lines[i+j][1]);
			g_print("Cheak %d:\t",num);
			if(lines[i][0]!=lines[i+j][0]) // проверка на не параллельность
			{
				g_print("Cheak finding\t");
				p=(cp*)malloc(sizeof(cp)); // выделение памяти для переменной p
 
				p->x=
				(lines[i][1]-lines[i+j][1])
				/
				(lines[i+j][0]-lines[i][0]);//вычисление координыты x=(b1-b2)/(k2-k1)
				p->y=
				(lines[i+j][0]*lines[i][1]-lines[i][0]*lines[i+j][1])
				/
				(lines[i+j][0]-lines[i][0]);//вычисление координыты y=(b1*k2-b2*k1)/(k2-k1)
				g_print("Cheak adding\t");
				fprintf(out, "\t\tПоиск точки пересечения и проверка на повторное добавление точки в список\n");
				if(find(l,p->x,p->y)==NULL)// проверка на то есть ли уже точка в списк или нет
				{
					addcp(l,p);//если ее нет то она соответственно добавляется
					g_print("CrossPoint %d: x=%2.2f; y=%2.2f",l->count,p->x,p->y);
					fprintf(out, "\t\t\tТочки еще нету в списке, она имеет координаты:\n\t\t\t\tx=%2.2f\n\t\t\t\ty=%2.2f\n",p->x,p->y);
					//если новая добавленая точка не попадает в зону отображения, то производится ее расширение
					if (p->x>max[0] || p->y>max[1]) {
						max[0]=p->x+1.0;
						max[1]=p->y+1.0;
					}
					if (p->x<min[0] || p->y<min[1]) {
						min[0]=p->x-1.0;
						min[1]=p->y-1.0;
					}
				} else {
				    fprintf(out,"\t\t\tДанная точка уже есть в списке точек пересечения\n");
				}
			} else {
				g_print("Parallel");
				fprintf(out,"\t\tПрямые параллельны или сливаются\n");
			}
			g_print("\n");
			num++;
		}
        }
	g_print("\nCount of cross points:%d\n",l->count);
	g_print("Output zone: from (%2.1f;%2.1f) to (%2.1f;%2.1f))\n",min[0],min[1],max[0],max[1]);
	fprintf(out,"\nЧисло точек пересечения:%d\n",l->count);
	fprintf(out,"Новая область отображения:\n\t\t(%2.1f;%2.1f)\n\t\t(%2.1f;%2.1f)\n", min[0],min[1],max[0],max[1]);
	fclose(out);
}
 
 
void draw_point( GdkDrawable *w, GdkGC * gc, int x0e, int y0e, int x1e, int y1e, float x0r, float y0r, float x1r, float y1r, float x, float y)
//функция рисованя точек пересечения - производится переход от реальных координат к экранным, точки изображаются красными окружностями
{
	int xe,ye;
	xe = x0e+(x1e-x0e)/(x1r-x0r)*(x-x0r);
	ye = y1e-(y1e-y0e)/(y1r-y0r)*(y-y0r);
	gdk_draw_arc( w, gc, TRUE, xe-3, ye-3, 6, 6, 0.0, 360*64);
}
 
 
gboolean draw_main (GtkWidget *widget, GdkEventExpose *event, gpointer data)
{
//функция рисования всех прямых которые храняться в файле lines.txt - прямые рисуютса по двум точкам
//дальнейшый вызов функции рисования точки для всех точек хранящихся в полученном списке
	cpl *l = (cpl*)data;
	GdkGC * gc = widget->style->fg_gc[GTK_WIDGET_STATE (widget)];
 
	GdkColor *clr = malloc(sizeof(GdkColor));
	clr->pixel = 0;
	clr->red   = 0x0000;
	clr->green = 0x0000;
	clr->blue  = 0x0000;
	gdk_gc_set_rgb_fg_color( gc, clr );
 
	int i;
	int x1,y1,x2,y2;
	x1 = 10+(widget->allocation.width-10-10)/(max[0]-min[0])*(min[0]-min[0]);
	x2 = 10+(widget->allocation.width-10-10)/(max[0]-min[0])*(max[0]-min[0]);
	for(i=0;i<N;i++)
	{
		y1 = widget->allocation.height-10 -(widget->allocation.height-10-10)/(max[1]-min[1])*(lines[i][0]*min[0]+lines[i][1]-min[1]);
		y2 = widget->allocation.height-10 -(widget->allocation.height-10-10)/(max[1]-min[1])*(lines[i][0]*max[0]+lines[i][1]-min[1]);
		gdk_draw_line(widget->window, gc, x1, y1, x2, y2);
	}
	cp *temp;
 
	free(clr);
	clr = malloc(sizeof(GdkColor));
	clr->pixel = 0;
	clr->red   = 0xffff;
	clr->green = 0x0000;
	clr->blue  = 0x0000;
	gdk_gc_set_rgb_fg_color( gc, clr );
 
	temp=l->head;
 
	while(temp!=NULL)
	{
		draw_point(widget->window, gc, 10,10, widget->allocation.width-10, widget->allocation.height-10, min[0], min[1], max[0], max[1], temp->x, temp->y);
		temp=temp->next;
	}
 
	free(clr);
	return TRUE;
}
 
 
 
int main ( int argc, char ** argv )
{
 
	FILE *f;//чтение из файла коэффициентов k и b (y=kx+b) и создание двумерного динамического массива
	int i;
	if (f = fopen("./lines.txt", "rt")) {
		fscanf(f, "%u", &N);
		lines = (double **)malloc(sizeof(double *)*N);
		for (i = 0; i<N; i++) {
			lines[i] = (double*)malloc(2*sizeof(double));
			fscanf(f, "%lf %lf", &lines[i][0], &lines[i][1]);
		}
	}
	fclose(f);
	cpl list;
	initlist(&list);//создание списка
	calc(&list);//функция вычислений
	gtk_init( &argc, &argv);//инициализация ГТК
	GtkWidget * window =  gtk_window_new (GTK_WINDOW_TOPLEVEL);//создание окна
	gtk_widget_set_size_request (window, 420, 420);//задание размеров окна
	g_signal_connect (G_OBJECT (window), "expose_event", G_CALLBACK (draw_main), (gpointer)&list);//прикрепление функции обратного вызова к сигналу для созданого окна
	g_signal_connect (G_OBJECT (window), "destroy", G_CALLBACK (gtk_main_quit), NULL);//pзавершение работы ГТК при закрытие программы (если убрать данную функцию то при закрытие программы она только исчезнит с экрана но не будет удалена из памяти)
	gtk_widget_show_all(window);
	gtk_main();
	dlist(&list);
	return 0;
}

Ключевые слова: 
точки пересечения, прямые на плоскости,
ВложениеРазмер
CG_lines.zip258.28 кб