Читайте также: |
|
polygon.dat (используется бинарный формат файла):
Размер блока (в байтах) | Число блоков | Наименование | Тип значения | Значение |
num | Целое | Число вершин многоугольника | ||
num | X | Вещественное | Массив координат вершин по X | |
num | Y | Вещественное | Массив координат вершин по Y |
points.dat (используется бинарный формат файла):
Размер блока (в байтах) | Число блоков | Наименование | Тип значения | Значение |
num | Целое | Число исходных точек | ||
num | X | Вещественное | Массив координат точек по X | |
num | Y | Вещественное | Массив координат точек по Y |
Выходные данные:
output.dat (используется бинарный формат файла):
Размер блока (в байтах) | Число блоков | Наименование | Тип значения | Значение |
num | Целое | Число точек, попадающих в заданный полигон | ||
num | IND | Целое | Индексы таких точек в исходных массивах X и Y |
Задание №2: Требуется написать класс (на C++), реализующий метод проекций в задаче регионального поиска (для k-мерного случая).
Реализовать два варианта метода:
[a] сортировка точек производится только по 1-й координате (поиск ведется с последовательным исключением);
[b] сортировка точек производится по каждой координате (поиск ведется с одновременным исключением);
Задание №3: Требуется определить набор ячеек прямоугольной сетки, покрывающих область, ограниченную двумя окружностями/сферами (для 2-D и 3-D случая).
Входные данные:
grid.dat (используется бинарный формат файла):
Размер блока (в байтах) | Число блоков | Наименование | Тип значения | Значение |
dim | Целое | Размерность пространства (принимает значения: 2, 3) | ||
dim | MIN | Вещественное | Нижняя граница прямоугольной области (по каждой координате) | |
dim | MAX | Вещественное | Верхняя граница прямоугольной области (по каждой координате) | |
dim | NUM | Целое | Число узлов сетки (по каждой координате) |
ring.dat (используется бинарный формат файла):
Размер блока (в байтах) | Число блоков | Наименование | Тип значения | Значение |
dim | Целое | Размерность пространства (принимает значения: 2, 3) | ||
dim | CENTER | Вещественное | Координаты центра области поиска | |
R1 | Вещественное | Внутренний радиус области поиска | ||
R2 | Вещественное | Внешний радиус области поиска |
Выходные данные:
output.dat (используется бинарный формат файла):
Размер блока (в байтах) | Число блоков | Наименование | Тип значения | Значение |
dim | Целое | Размерность пространства (принимает значения: 2, 3) | ||
num | Целое | Количество ячеек прямоугольной сетки, покрывающих область поиска | ||
dim * num | CELL | Целое | Массив индексов обнаруженных ячеек: {ix[1], iy[1], …}, {ix[2], iy[2], …}, … |
Задание №4: Требуется написать класс (на C++), реализующий метод сеток (ячеек) в задаче регионального поиска (для 2-D и 3-D случая).
Задание №5: Требуется написать класс (на C++), реализующий дерево квадрантов (Q-дерево).
Дерево строится сверху вниз, по мере добавления в него новых точек.
Корень дерева отождествляется со всей координатной плоскостью.
Разбиение каждой ячейки происходит по медиане множества входящих в нее точек.
Требования к выполнению заданий:
1) Язык реализации: C/C++. Компилятор GCC/MinGW.
2) Файл с основной программой должен называться main.c/main.cpp.
3) В именах файлов проекта должны отсутствовать пробелы.
4) Задания присылаются на почту в виде архива (*.7z, *.zip, *.rar).
ВАЖНО: В архив включаются только исходные тексты программ (*.c, *.cpp, *.h, *.hpp).
5) Имя архива должно соответствовать следующему шаблону:
<Номер_Задачи>.[<Группа>].<Фамилия>.<И>.<О>.
Пример: 1.[Б8303б].Фамилия.И.О.zip
6) К архиву также прилагается отчет (с именем “text”), выполненный в одном из следующих форматов: *.docx, *.doc, *.odt, *.pdf, *.ps
Список рекомендованной литературы:
[1] Препарата Ф., Шеймос М. Вычислительная геометрия: Введение.
[2] J.L. Bentley, J.H. Friedman. Data Structures for Range Searching.
[3] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry: Algorithms and Applications.
[4] Ласло М. Вычислительная геометрия и компьютерная графика на C++.
Дата добавления: 2015-01-12; просмотров: 9 | Поможем написать вашу работу | Нарушение авторских прав |
<== предыдущая лекция | | | следующая лекция ==> |
Конец ознакомительного фрагмента. | | | Глава I. ОБЩИЕ ПОЛОЖЕНИЯ |