Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Сейчас проверила нашла причину не запускания // Создание контекста воспроизведения OpenGL и привязка его к панели на форме OpenGLControl1:=TOpenGLControl.Create(Self); with OpenGLControl1 do begin Name:='OpenGLControl1'; //вот тут...
Ну..кажется что то пошло не так http://pp.usera...
Комментарии на английском переведите на русский. Дополните код комментариями, чтоб было понятно как работает алгоритм
Пример, к которому вы оставили комментарий строит именно то самое изображение на языке с#, которое вам необходимо. Отличается только цветовая палитра.

Счетчики и рейтинг

Рейтинг@Mail.ru
Скриншот к примеру
Среда программирования: 
Eclipse Mars.2(4.5.2)

Задача: определить, принадлежит ли точка многоугольнику.
Для запуска приложения на Linux достаточно открыть файл is_in_polygon(см. архив во вложении), предварительно сделав его исполняемым(chmod +x либо Свойства-Права-Разрешить исполнять как программу). После запуска появится белое окно, в заголовке которого отображаются координаты последнего нажатия левой кнопки мыши(начальные значения x = 0, y = 0). По щелчку левой кнопки мыши в произвольном месте окна на месте нажатия рисуется точка и проводится линия из предыдущей точки в новую(если указаны хотя бы 2 точки), таким образом можно построить любой многоугольник. При нажатии клавиши Enter завершается построение многоугольника(многоугольник нельзя будет больше изменить), последняя точка соединяется с первой.

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

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

Код программы: 

points.h

#ifndef POINTS_H
#define POINTS_H
#include <vector>
 
using namespace std;
 
struct Vertex { //вершина
    int x, y; //координаты вершины
    //конструктор по умолчанию
    Vertex ( int a = 0, int b = 0 ) : x(a), y(b) {}
};
 
//положение точки(внутри, снаружи, на границе)
typedef enum { in, out, border } point_position;
 
//векторное произведение
double cross_prod ( Vertex, Vertex, Vertex );
//скалярное произведение
double scalar_prod ( Vertex, Vertex, Vertex );
//лежит ли точка на ребре
bool is_point_on_edge ( Vertex, Vertex, Vertex );
//пересекается ли ребро с лучом
bool is_edge_cross ( Vertex, Vertex, Vertex, Vertex );
//выбор точки на луче
Vertex point_on_ray ( Vertex, int );
//расположение точки относительно многоугольника(внутри/снаружи/на границе)
point_position is_point_in_polygon ( vector <Vertex>, Vertex, int );
 
#endif /* POINTS_H*/

points.cpp

#include "points.h"
#include <vector>
using namespace std;
 
 
//[ {ab} x {ac} ]
double cross_prod ( Vertex a, Vertex b, Vertex c ) {
	double x1 = b.x - a.x, y1 = b.y - a.y,
		x2 = c.x - a.x, y2 = c.y - a.y;
	return ( x1 * y2 - x2 * y1 );
}
 
//( {ab}, {ac} )
double scalar_prod ( Vertex a, Vertex b, Vertex c ) {
	double x1 = b.x - a.x, y1 = b.y - a.y,
		x2 = c.x - a.x, y2 = c.y - a.y;
	return ( x1 * x2 + y1 * y2 );
}
 
//точка c лежит на ребре ab, если она лежит на одной прямой с ab(векторное произведение = 0),
//и c лежит между a и b(скалярное произведение <= 0; = 0, когда c совпадает с a или c b)
bool is_point_on_edge ( Vertex a, Vertex b, Vertex c ) {
	double prod1 = cross_prod ( a, b, c ),
		prod2 = scalar_prod ( c, a, b );
	return ( prod1 == 0 && prod2 <= 0 ) ? true : false;
}
 
//пересекаются ли отрезки ab и cd
bool is_edge_cross ( Vertex a, Vertex b, Vertex c, Vertex d ) {
	double prod1, prod2, prod3, prod4;
	prod1 = cross_prod ( a, b, c );
	prod2 = cross_prod ( a, b, d );
	prod3 = cross_prod ( d, c, a );
	prod4 = cross_prod ( d, c, b );
	//отрезки ab и cd пересекаются, если c и d лежат по разные стороны от ab,
	//a и b лежат по разные стороны от cd
	bool is_cross = (prod1 * prod2 < 0 && prod3 * prod4 < 0);
	//надо проверить, не принадлежат ли концы одного отрезка другому
	//в этом случае одно(или несколько) векторных произведений обратятся в ноль
	bool cond1, cond2, cond3, cond4, cond1_1, cond2_1, cond3_1, cond4_1, is_one_inside_other;
	cond1 = is_point_on_edge ( a, b, c );
	cond2 = is_point_on_edge ( a, b, d );
	cond3 = is_point_on_edge ( c, d, a );
	cond4 = is_point_on_edge ( c, d, b );
	//проверка, что только один конец одного из отрезков принадлежит другому
	//таким образом, из рассмотрения исключаюся ребра, лежащие на луче
	cond1_1 = ( cond1 && ! ( cond2 || cond3 || cond4 ) );
	cond2_1 = ( cond2 && ! ( cond1 || cond3 || cond4 ) );
	cond3_1 = ( cond3 && ! ( cond1 || cond2 || cond4 ) );
	cond4_1 = ( cond4 && ! ( cond1 || cond2 || cond3 ) );
	is_one_inside_other = ( cond1_1 || cond2_1 || cond3_1 || cond4_1 );
 
	return ( is_cross || is_one_inside_other) ? true : false;
}
 
//выбор точки на луче, проходящем через проверяемую точку point; в качестве такой точки
//выбрана крайняя точка окна, лежащая на одной горизонтальной прямой с point
Vertex point_on_ray ( Vertex point, int scr_width ) {
	Vertex ray ( scr_width, point.y );
	return ray;
}
 
//положение точки относительно многоугольника
point_position is_point_in_polygon ( vector <Vertex> polygon, Vertex begin, int scr_width ) {
	Vertex first, second; //вершины многоугольника
	//получение второй точки, лежащей на луче
	Vertex end = point_on_ray ( begin, scr_width );
	unsigned count = 0; //кол-во пересечений с лучом
	if ( polygon.empty() )
		return out; //не было передано ни одной вершины
	if ( polygon.size() == 1 ) //была передана одна вершина
		return ( ( polygon[0].x == begin.x && polygon[0].y == begin.y ) ? border : out );
	if ( polygon.size() == 2 ) { //был передан отрезок
		second.x = polygon[1].x; second.y = polygon[1].y;
		first.x = polygon[0].x; first.y = polygon[0].y;
		return ( is_point_on_edge ( first, second, begin ) ? border : out );
	}
	//был передан по крайней мере треугольник
	for ( unsigned i = 1; i <= polygon.size(); i++ ) {
		if ( i < polygon.size() ) {
			second.x = polygon[i].x; second.y = polygon[i].y;
			first.x = polygon[i - 1].x; first.y = polygon[i - 1].y;
		}
		else { //обрабатываем последнее ребро(последняя и первая вершины)
			second.x = polygon[0].x; second.y = polygon[0].y;
			first.x = polygon.back().x; first.y = polygon.back().y;
		}
		//принадлежит ли точка ребру
		if ( is_point_on_edge ( first, second, begin ) )
			return border; //точка на границе
		//пересекается ли ребро с лучом(при этом исключаются ребра, лежащие на луче)
		if ( is_edge_cross ( first, second, begin, end ) )
			//определяем нижнюю вершину по y
			//ребро не лежит на одной прямой с горизонтальным лучом (из предыдущего условия)
			//если выбрать не горизонтальный луч, надо дополнительно рассмотреть горизонтальные ребра
			if ( ( first.y > second.y && second.y < begin.y ) ||
					( first.y < second.y && first.y < begin.y ) )
					count++; //нижний конец ребра ниже луча
	}
	if ( count % 2 )
		return in; //нечетное кол-во пересечений с горизонтальным лучом
	return out;
}

main.cpp

#include <cstdio>
#include <cstdlib>
#include <vector>
#include "points.h"
#include <GL/glut.h>
#define width 800
#define height 640
#define ESC 27 //десятичный код клавиши Esc
#define ENTER 13 //десятичный код клавиши Enter
 
using namespace std;
 
int mouse_x = 0, mouse_y = 0; //координаты точки при последнем нажатии левой кнопки мыши
bool enter_flag = false; //была ли нажата клавиша Enter
vector <Vertex> polygon, points; //здесь будут сохраняться координаты
Vertex *ptr; //вспомогательный указатель
 
void draw_dot () {
	if ( !points.empty() ) { //прорисовка вершин многоугольника
		glPointSize ( 5 ); //размер точки в пикселях (5х5 пикселей)
		glBegin ( GL_POINTS ); //тип примитива(точка)
		glColor3ub ( 0, 0, 0 ); //установка цвета рисования(RGB, черный)
		//прорисовываем точками все вершины
		for ( auto now : points )
			glVertex2i ( now.x, now.y );
		glEnd ();
		//была нажата клавиша Enter, построение многоугольника завершено
		if ( enter_flag ) {
			Vertex point; //точка, проверяемая на принадлежность многоугольнику
			glPointSize ( 9 );
			//проверяем квадрат 9x9, т.к. размер точки 9х9 пикселей
			//координаты точки содержатся в mouse_x, mouse_y
			for ( int i = mouse_x - 4; i <= mouse_x + 4; i++ ) {
				for ( int j = mouse_y - 4; j <= mouse_y + 4; j++ ) {
					point.x = i; point.y = j;
					if ( is_point_in_polygon ( polygon, point, width ) == in ||
							is_point_in_polygon( polygon, point, width ) == border ) {
						//если точка внутри или на границе, меняем цвет рисования на красный
						glColor3ub ( 255, 0, 0 );
						i = mouse_x + 5; //для выхода из внешнего цикла
						break;
					}
				}
			}
			glBegin ( GL_POINTS );
			//рисуем точку на месте последнего щелчка мыши
			glVertex2i ( mouse_x, mouse_y );
			glEnd ();
		}
	}
}
 
void draw_line () {
	if ( !polygon.empty() ) {
		glColor3ub ( 18, 31, 154 ); //синий
		glLineWidth ( 2 ); //толщина линии
		glBegin ( GL_LINES ); //тип примитива-линия
		//соединяем по две соседние вершины
		for ( unsigned i = 1; i < polygon.size(); i++ ) {
			glVertex2i ( polygon[ i - 1].x, polygon[i - 1].y );
			glVertex2i ( polygon[i].x, polygon[i].y );
		}
		if ( enter_flag ) { //построение завершено, соединяем первую и последнюю вершины
			glVertex2i ( polygon[0].x, polygon[0].y );
			glVertex2i ( polygon.back().x, polygon.back().y );
		}
		glEnd ();
	}
}
 
void reshape ( int w, int h ) {
	glViewport ( 0, 0, width, height ); //область вывода
	glLoadIdentity (); //замена текущей матрицы на единичную
	gluOrtho2D ( 0, width,  0, height ); //плоскость отсечения
	glMatrixMode ( GL_MODELVIEW ); //матрица преобразований
	glFlush();
}
 
//создание заголовка окна с координатами точки
void generate_window_title () {
	char *str;
	str = new char [50]; //выделение памяти под строку
	//формирование заголовка
	sprintf ( str, "x = %d, y = %d", mouse_x, mouse_y );
	glutSetWindowTitle ( str ); //установка заголовка
	delete [] str;
}
 
void display () {
	generate_window_title(); //обновление заголовка
	glClear (GL_COLOR_BUFFER_BIT); //очистка текущего буфера цвета
	draw_dot (); //прорисовка вершин и точки
	draw_line(); //прорисовка ребер
	glFlush(); //вывод на экран
}
 
void mouse ( int button, int state, int x, int y ) {
	if ( state == GLUT_DOWN ) //нажата кнопка
		switch ( button ) {
			//если левая кнопка
			case GLUT_LEFT_BUTTON:
				mouse_x = x; mouse_y = height - y; //запоминаем новые координаты точки
				if ( !enter_flag ) { //добавляем новые координаты(если не был нажат Enter)
					ptr = new Vertex ( mouse_x, mouse_y );
					polygon.push_back(*ptr);
					points.push_back(*ptr);
					delete ptr;
				}
				break;
			//если правая кнопка
			case GLUT_RIGHT_BUTTON:
				//сбрасываем координаты
				mouse_x = 0; mouse_y = 0;
				//освобождаем память
				polygon.clear();
				points.clear();
				//сбрасываем флаг Enter
				enter_flag = false;
				break;
		}
	glutPostRedisplay (); //обратный вызов функции перерисовки окна
}
 
void keyboard ( unsigned char key, int x, int y ) {
	switch ( key ) {
		case ESC: //если был нажат esc, выходим из приложения
			exit (ESC);
			break;
		case ENTER: //если enter
			enter_flag = true; //устанавливаем флаг
			glutPostRedisplay (); //вызываем функцию перерисовки для отображения последнего ребра
			break;
	}
}
 
int main ( int argc, char** argv ) {
	glutInit( &argc, argv ); //инициализация OpenGL Utility Toolkit
	glutInitDisplayMode( GLUT_SINGLE | GLUT_RGB ); //режим окна(одиночный буфер и RGB-палитра)
	glutInitWindowSize ( width, height ); //установка размеров окна(ширина и высота в пикселях)
	glutInitWindowPosition ( 200, 30 );//положение окна относительно левого верхнего угла экрана
	glutCreateWindow ( "" ); //создание окна
	glutReshapeFunc ( reshape );  //перерисовка окна при измении его размеров или положения
	glutDisplayFunc ( display );//инициализация функции, отвечающей за рисование в окне
	glutMouseFunc ( mouse ); //обработка мыши
	glutKeyboardFunc ( keyboard ); //обработка клавиатуры
	glClearColor ( 1.0, 1.0, 1.0, 1.0 ); //цвет фона(RGBA, белый)
	glutMainLoop (); //вход в главный цикл
	return 0;
}

Прикрепленный файлРазмер
kolesnikova_ray_tracing_for_polygon.zip141.3 кб