Компьютерная геометрия (2013-2014)
Замечание: при выполнении каждой задачи необходимо подготовить:
1) теоретическую часть: описание алгоритма и структуры данных на рукописном листе (или в тетради) либо в текстовом файле;
2) работающую программу;
3) предусмотреть графическую визуализацию результата программы;
4) заготовить и продемонстрировать 2-3 контрольных примера исходных данных (если они не заданы в условии задачи), проверив «руками» (т.е. письменно аналитически) правильность работы программы.
1. («Пересечение прямой и многоугольника».) Пользователь задает: 1) плоский многоугольник, при помощи количества вершин n и списка вершин, перечисленных в порядке обхода ломаной линии, состоящей из ребер, против часовой стрелки (матрица n x 2). 2) прямую L при помощи неявного уравнения Ax+By+D=0. Программа должна определить пересекает ли прямая многоугольник.
2. («Тест на выпуклость многоугольника».) Пользователь задает многоугольник (см. задачу 1). Программа должна определить, является ли многоугольник выпуклым.
3. («Тест на самопересечение границ многоугольника».) Пользователь задает многоугольник (см. задачу 1). Программа должна определить, имеет ли самопересечение ломаная, задающая границу многоугольника.
4. («Ориентация точки относительно выпуклого многоугольника».) Пользователь задает: 1) выпуклый многоугольник P (см. задачу 1); 2) точку T на плоскости. Программа должна определить, принадлежит ли точка T многоугольнику P.
5. («Габаритный тест на ориентацию точки относительно многоугольника».) Пользователь задает: 1) многоугольник P (см. задачу 1); 2) точку T на плоскости. Программа должна определить, выполнено ли необходимое условие принадлежности точки многоугольнику.
6. («Угловой тест на принадлежность точки многоугольнику».) Пользователь задает: 1) многоугольник P (см. задачу 1); 2) точку T на плоскости. Программа должна определить, принадлежит ли точка T многоугольнику P, используя алгоритм суммирования направленных углов поворота.
7. («Лучевой тест на принадлежность точки многоугольнику».) Пользователь задает: 1) многоугольник P (см. задачу 1); 2) точку T на плоскости. Программа должна определить, принадлежит ли точка T многоугольнику P, используя «лучевой» алгоритм.
8. («Случайный многоугольник».) Генерировать случайный многоугольник по методу «розы ветров». Пользователь задает: 1) центр многоугольника – точку С; 2) параметры a,b – минимальное и максимальное расстояние вершин от центра; 3) минимальное и максимальное приращение полярного угла.
9. («Случайный многоугольник».) Генерировать случайный многоугольник по методу «скачущего кузнечика». Пользователь задает: 1) начальную точку; 2) параметры a,b – минимальное максимальное значение длины ребра; 3) минимальное и максимальное значение приращение полярного угла для вектора направления ребра.
10. («Пересечение плоскости с многогранником».) Пользователь задает многогранник P в 3-мерном пространстве: 1) количество вершин V, и список вершин (матрица V x 3). А также некоторую плоскость p её неявным уравнением. Программа должна определить, пересекает ли плоскость p многогранник P.
11. («Тест выпуклости многогранника».) Пользователь задает многогранник P в 3-мерном пространстве: 1) количество вершин V, и список вершин (матрица V x 3); 2) количество граней F, и список граней (массив длины F из подмножеств элементов {1..V}, либо матрица F x V с элементами 0,1). Программа должна определить, является ли многогранник P выпуклым.
12. («Тест принадлежности точки выпуклому многограннику») Пользователь задает выпуклый многогранник P (см. задачу 11) и точку T в пространстве. Программа должна определить, принадлежит ли точка T многограннику P.
13. («Пересечение луча с поверхностью 2-го порядка»). Пользователь задает: 1) луч в 3-мерном пространстве при помощи начальной точки Q и направляющего вектора v; 2) поверхность 2-го порядка при помощи неявного уравнения с 6 действительными коэффициентами. Программа должна определить пересекает ли луч поверхность и найти точку пересечения, если она существует.
14. («Пересечение луча с поверхностью, заданной неявным уравнением».) Из точки q = (10; 1; 0) выпущен луч p(t) = q + V t (t ? 0) в направлении, задаваемом вектором
V = (-2; -0.1; -0.2). Рассчитать (используя численные методы) пересечения луча с поверхностью, описываемой явным уравнением
с параметрами 
, 
, 
.
15. («Пересечение луча с поверхностью, заданной параметрически».) Рассчитать, используя численные методы, пересечение луча, выпущенного из точки 
в направлении вектора 
, с поверхностью, заданной параметрическим уравнением
,
где 
, 
.
16. («Луч, отраженный от зеркального эллипсоида».) Из точки 
воздушной среды выпущен луч в направлении вектора 
. Найти точку его пересечения с зеркальным эллипсоидом, имеющим полуоси 
и центр в точке 
. А также параметрическое уравнение отраженного луча. (Пользователь задает геометрические параметры 
.)
17. («Луч, преломленный в стеклянном эллипсоиде».) Из точки воздушной среды (с коэффициентом преломления 
) выпущен луч в направлении вектора . Найти точку его пересечения со стеклянным эллипсоидом ( 
), имеющим полуоси и центр в точке . А также параметрическое уравнение преломленного луча. (Пользователь задает геометрические параметры 
.)
18. Задача выполняется 2-мя студентами.
(«Тень пирамиды на плоскости».) Построить тень пирамиды с вершинами 
, 
, 
, 
на плоскость, заданную «в отрезках» (точками пересечения с осями координат) 
, 
, 
, от источника света, расположенного в точке 
. Направление на дальнего наблюдателя задается вектором 
(построить параллельную проекцию тени на плоскость, перпендикулярную вектору проекции S, которая и должна появиться на мониторе). Проанализировать изменение тени при удалении источника в бесконечность вдоль вектора 
.
19. Задача выполняется 2-мя студентами.
(«Отражение пирамиды от зеркальной криволинейной поверхности, удаленный наблюдатель».) Построить отражение пирамиды с вершинами , , , от криволинейной поверхности
с параметрами , , .
Направление на дальнего наблюдателя задается вектором 
(что соответствует параллельной проекции вдоль вектора S на перпендикулярную к нему плоскость монитора).
20. Задача выполняется 2-мя студентами.
(«Отражение пирамиды от плоского зеркала, близкий наблюдатель».) Построить отражение пирамиды с вершинами 
, 
, 
, от плоского зеркала в форме параллелограмма, три вершины которого находятся на осях координат, отсекая отрезки , 
, 
. Наблюдатель находится с точке 
(использовать центральную проекцию с центром 
объекта на плоскость монитора, параллельную 
, например, 
).
