Задачи

1.   Построив дерево грамматического разбора, покажите, что ааЬЬа не является предложением языка, грамматика которого обсуждалась в разд. 12.2.

2.   Используя подход, основанный на стандартных точках притяжения, постройте грамматику, язык которой включает по крайней мере три различных контурных рисунка куба.

3.   Придумайте решающее правило для определения, связаны ли два произвольных неперекрывающихся объекта отношением слева/справа. Правило должно давать решения, соответствующие человеческому здравому смыслу, и не должно быть слишком простым, таким, например, что для выполнения отношения потребовалось бы, чтобы один объект находился полностью слева от другого. Придумайте другое решающее правило для определения, связаны ли объекты отношением сверху/снизу. Идентичны ли эти правила во всем, за исключением изменения в ориентации на 90°?

4.   Разработайте алгоритм для определения по картинке, связаны ли два многогранника отношением поддерживает/поддерживается.

5.   Найдите матрицу 5 размерностью 4X4, которая масштабирует каждую компоненту трехмерного вектора ѵ в произвольное число раз. (Мы полагаем, что вектор ѵ сначала преобразуется в однородную форму ѵ и что произведение Sv преобразуется снова в обычные координаты.) Покажите, как можно использовать матрицу S, чтобы единственная модель куба служила моделью произвольного прямоугольного параллелепипеда.

6.   Выведите формулы (1) и (2), дающие решение задачи подбора модели по минимуму среднеквадратичной ошибки.

7.   Постройте в общих чертах алгоритм для решения проблемы невидимых линий. Можно ли существенно упростить алгоритм, если он должен применяться только к картинкам многогранников? к изображениям прямоугольных тел?

8.   Начертите несколько трехгранных тел, чтобы продемонстрировать все типы вершин каталога рис. 12.9. Пометьте каждую вершину указателем ее типа

по каталогу и пометьте каждую линию плюсом, минусом или должным образом ориентированной стрелкой.

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

10.  Почему не может быть вершин типов 2, 4, 6 или 8?

11.  Начертите сцену, "которая изображает по крайней мере четыре многогранных объекта и содержит по крайней мере одну вершину типа «X» и по крайней мере одну пару согласованных вершин типа «7"». Объедините области сцены в объекты, используя эвристический метод, описанный в данной главе. (Используйте либо правило 1, либо правило 1' по вашему выбору.)

12.  Начертите сцену с многогранными объектами, для которой эвристические правила, обсуждавшиеся в этой главе, объединяют области в объекты неправдоподобно. Предложите модификации и дополнения к правилам, чтобы улучшить их действие. Вы должны рассматривать модификации как правил введения связей между областями, так и правил объединения областей.

13.  Нарисуйте дуальный граф многогранника рис. 12.10, г и проанализируйте его сливаемость. (Считайте, что объект представляет собой единый многогранник.)

14.  Начертите трехгранное тело, содержащее по крайней мере одно «отверстие». Проанализируйте его сливаемость. Постройте дерево поиска, необходимое для разметки вершин тела; и посмотрите, существует ли здесь более чем одна совместимая интерпретация:

15.  Можно ли распространить интерпретацию посредством дуального графа на многогранники степени большей чем 3, и если можно, то каким образом?