«Е.А. Роганов Основы информатики и программирования Учебное пособие для студентов программистских специальностей Москва 2001 ББК 22.18 УДК 519.6 Р59 Е.А. Роганов. Основы информатики и программирования: Учебное пособие ...»

d) результатом его работы было дерево вывода исходной формулы.

Задача 3.12. Модифицируйте текст эталонного проекта Интерпретатор формул так, чтобы:

a) деление трактовалось, как левоассоциативная операция;

b) приоритеты операций сложения и вычитания были выше, чем у операций умножения и деления;

c) в качестве аргументов допускались произвольные целые неотрицательные числа;

d) для группировки в формулах можно было использовать не только круглые, но также квадратные и фигурные скобки;

e) вычислялись значения выражений, содержащих операцию % (остаток от деления), с приоритетом, равным операциям умножения и деления;

f) вычислялись значения выражений, содержащих пробелы и комментарии двух видов: /* */ и //;

g) вычислялись значения выражений, запись которых состоит из нескольких строк;

h) вычислялись значения выражений, содержащих унарные арифметические операции + и -;

i) вычислялись значения выражений, содержащих бинарные битовые операции | и &;

j) вычислялись значения выражений, содержащих унарную битовую операцию ^.

Задача 3.13. Модифицируйте текст эталонного проекта Интерпретатор формул так, чтобы:

a) вычислялись значения формул, содержащих только десятичные числа (до 3999), а результат печатался в виде восьмеричного числа;

b) вычислялись значения формул, содержащих только десятичные числа (до 3999), а результат печатался в виде шестнадцатеричного числа;

c) вычислялись значения формул, содержащих только десятичные числа (до 3999), а результат печатался в виде римского числа;

d) вычислялись значения формул, содержащих только восьмеричные числа (до 3999), а результат печатался в виде десятичного числа;

e) вычислялись значения формул, содержащих только восьмеричные числа (до 3999), а результат печатался в виде римского числа;

§3. Проект Компилятор формул f) вычислялись значения формул, содержащих только шестнадцатеричные числа (до 3999), а результат печатался в виде десятичного числа;

g) вычислялись значения формул, содержащих только шестнадцатеричные числа (до 3999), а результат печатался в виде римского числа;

h) вычислялись значения формул, содержащих только римские числа (до 3999), а результат печатался в виде десятичного числа;

i) вычислялись значения формул, содержащих только римские числа (до 3999), а результат печатался в виде восьмеричного числа;

j) вычислялись значения формул, содержащих только римские числа (до 3999), а результат печатался в виде шестнадцатеричного числа.

Задача 3.14. Модифицируйте текст эталонного проекта Интерпретатор формул так, чтобы:

a) вычислялись значения формул, содержащих операцию возведения в степень ^, которая правоассоциативна и имеет максимальный приоритет;

b) вычислялись значения формул, содержащих операцию возведения в степень **, которая правоассоциативна и имеет максимальный приоритет;

c) вычислялись значения формул, содержащие квадратные скобки [], обозначающие удвоение выражения, в них стоящего;

d) вычислялись значения формул, содержащие фигурные скобки {}, обозначающие возведение в квадрат выражения, в них стоящего.

Задача 3.15. Модифицируйте текст эталонного проекта Стековый компилятор формул, превратив его в аплет, который:

a) строит график функции y = f (x), где формула f (x) вводится с клавиатуры;

b) строит график функции, заданной в полярных координатах соотношением r = f (), где зависимость f () вводится с клавиатуры (для обозначения переменной при этом следует использовать идентификатор t);

c) строит график функции, заданной параметрически соотношениями x = x(t), y = y(t), где зависимости x(t) и y(t) вводятся с клавиатуры.

7. Тексты эталонных проектов. Сначала приведем все исходные тексты рекурсивного компилятора формул.

Makefile для рекурсивного компилятора формул.

# -*- mode: makefile -*PHONY : run clean # Запустить тест рекурсивного компилятора формул.

java RecursCompfTest # Откомпилировать текст рекурсивного компилятора формул.

Глава III. Применение ООП к разработке программных проектов RecursCompfTest.class: RecursCompfTest.java RecursCompf.java \ javac RecursCompfTest.java # Удалить лишние файлы.

clean:

rm -f *.class *.expand Рекурсивный компилятор формул.

// Рекурсивный компилятор формул.

public class RecursCompf { private static final int DEFSIZE = 255;

private char[] str;

private void compileF() { if (index >= str.length) return;

if (str[index] == ’+’){ if (str[index] == ’-’){ private void compileT() { if (index >= str.length) return;

if (str[index] == ’*’){ if (str[index] == ’/’){ private void compileM() { private void compileV() { Xterm.print("" + str[index++] + " ");

public void RecursCompf() { str = new char[DEFSIZE];

public void compile(char[] str) { Xterm.print("\n");

Тест для рекурсивного компилятора формул.

// Тест для рекурсивного компилятора формул.

public class RecursCompfTest { public static void main(String[] args) throws Exception { RecursCompf c = new RecursCompf();

c.compile(Xterm.inputChars("Введите формулу -> "));

Теперь приведем все исходные тексты, относящиеся к стековому компилятору формул и интерпретатору.

Makefile для стекового компилятора и интерпретатора формул.

# -*- mode: makefile -*PHONY : compf calc clean # Запустить тест стекового компилятора формул.

# Откомпилировать текст стекового компилятора формул.

CompfTest.class: CompfTest.java Compf.java Xterm.java javac CompfTest.java # Запустить тест калькулятора формул.

# Откомпилировать текст калькулятора формул.

CalcTest.class: CalcTest.java Calc.java Compf.java Xterm.java javac CalcTest.java # Удалить лишние файлы.

clean:

rm -f *.class *.expand Стековый компилятор формул.

// Непрерывная реализация стека символов.

class Stack { private static final int DEFSIZE = 16;

private char[] array;

public Stack() { Глава III. Применение ООП к разработке программных проектов array = new char[DEFSIZE];

public final void push(char c) { public final char pop() { return array[--head];

public final char top() { return array[head-1];

// Стековый компилятор формул.

public class Compf extends Stack { // Типы символов (скобки, знаки операции, иное).

protected final static int SYM_LEFT = 0, private int symType(char c) { case ’+’: case ’-’: case ’*’: case ’/’:

private void processSymbol(char c) { switch (symType(c)) { processSuspendedSymbols(c); pop(); break;

processSuspendedSymbols(c); push(c); break;

private void processSuspendedSymbols(char c) { while (precedes(top(), c)) private int priority(char c) { private boolean precedes(char a, char b) { if(symType(a) == SYM_LEFT) return false;

if(symType(b) == SYM_RIGHT) return true;

return priority(a) >= priority(b);

protected int symOther(char c) { Xterm.println("Недопустимый символ: " + c);

return SYM_OTHER;

protected void nextOper(char c) { protected void nextOther(char c) { public void compile(char[] str) { processSymbol(’(’);

for(int i = 0; i < str.length; i++) processSymbol(str[i]);

processSymbol(’)’);

Xterm.print("\n");

Тест для стекового компилятора формул.

// Тест для компилятора формул.

public class CompfTest { public static void main(String[] args) throws Exception { c.compile(Xterm.inputChars("Введите формулу -> "));

Интерпретатор формул.

// Непрерывная реализация стека целых чисел.

class StackInt { private static final int DEFSIZE = 16;

private int[] array;

private int head;

public StackInt() { array = new int[DEFSIZE];

public final void push(int val) { array[head++] = val;

public final int pop() { return array[--head];

public final int top() { return array[head-1];

// Калькулятор арифметических формул.

public class Calc extends Compf { private StackInt s;

private static int char2int(char c) { Глава III. Применение ООП к разработке программных проектов return (int)c - (int)’0’;

protected int symOther(char c) { Xterm.println("Недопустимый символ: " + c);

return SYM_OTHER;

protected void nextOper(char c) { s.push(first + second); break;

s.push(first - second); break;

s.push(first * second); break;

s.push(first / second); break;

protected void nextOther(char c) { s.push(char2int(c));

public Calc() { public final void compile(char[] str) { super.compile(str);

Xterm.println("" + s.top());

Тест для интерпретатора формул.

// Тест для калькулятора формул.

public class CalcTest { public static void main(String[] args) throws Exception { c.compile(Xterm.inputChars("Введите формулу -> "));

Этот параграф посвящен рассмотрению еще одного проекта, который позволит познакомиться с простейшими задачами вычислительной геометрии. Построение изображения полиэдра с удалением невидимых линий пример столь же классической задачи, как и рассмотренная в предыдущем параграфе задача компиляции. В процессе работы над проектом §4. Проект Изображение полиэдра происходит также знакомство с графической библиотекой (пакетом) AWT и системой документирования программ javadoc.

В книгах [9] и [8] содержится большое количество дополнительной информации, связанной с рассматриваемой задачей и ее различными обобщениями. Вопросы работы с пакетом AWT и системой документирования в языке Java более подробно могут быть изучены с помощью книг [11] и [10].

1. Постановка задачи. В настоящее время во многих областях науки и техники используются различные методы моделирования геометрических объектов в трехмерном пространстве. Один из способов моделирования состоит в том, чтобы аппроксимировать реальный объект набором выпуклых плоских многоугольников. Такой набор мы будем называть полиэдром, многоугольники гранями, а их стороны ребрами полиэдра.

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

250 Глава III. Применение ООП к разработке программных проектов При изображении полиэдра реально рисуются не сами многоугольники, а линии, их ограничивающие, то есть их ребра. Если, однако, изобразить все ребра полиэдра, то получится весьма запутанная, непривычная для человека картина. Для получения удобного для человека рисунка нужно при построении изображения учитывать, что некоторые ребра могут оказаться полностью или частично невидимыми, так как их могут загородить грани полиэдра. Таким образом, при построении изображения надо удалить (не рисовать) части ребер, которые не видны. По этой причине рассматриваемая задача в литературе часто называется задачей удаления невидимых линий.

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

В результате решения этой задачи полиэдр должен изображаться примерно так, как это показано на рисунке 20.

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

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

Рассматриваемая задача, таким образом, сводится к следующей: построить проекцию полиэдра с удалением невидимых линий на бесконечно высокую горизонтальную плоскость z = H. Требуемое плоское изображение при этом задано не однозначно, так как вращения вокруг вертикальной оси Oz приводят к поворотам итоговой картинки. Будем поэтому считать, что полная постановка задачи кроме самого полиэдра и вектора проектирования содержит также задание угла поворота в плоскости проекции.

Такую уточненную постановку задачи иллюстрирует рисунок 21.

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

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

Способ представления полиэдра, который будет использован нами при решении рассматриваемой задачи, несколько отличен от только что описанного. Он предусматривает указание числа и координат вершин полиэдра, а также количества граней и ребер с указанием для каждой из граней номеров всех ее вершин. По этой причине многие ребра оказываются указанными дважды или даже большее число раз (так как принадлежат нескольким граням), что является, безусловно, недостатком этого способа представления.

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

Информация, представляющая полиэдр, является достаточно объемной, и поэтому было бы весьма неудобно вводить ее, используя клавиатуру. Гораздо разумнее создать описание полиэдра в специальном файле, а программе передать его имя. Вот как будет выглядеть этот файл, представляющий поверхность единичного куба с центром в начале координат и гранями, параллельными координатным плоскостям:

252 Глава III. Применение ООП к разработке программных проектов Первая строка говорит о том, что у куба 8 вершин, 6 граней и 24 (!) ребра. Число 24, вдвое превышающее реальное количество ребер у куба, является результатом уже описанного выше эффекта, каждое из ребер куба принадлежит ровно двум граням.

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

Технические детали работы с файлами и чтения информации из них могут быть изучены заинтересованными читателями самостоятельно с использованием итогового текста проекта, приведенного в конце параграфа, и литературы, содержащей описание библиотек (пакетов) языка Java.

2. Проектирование основных классов. В данной секции будет построена иерархия классов, необходимых для реализации рассматриваемого проекта. Здесь же мы рассмотрим (в самых общих чертах) использование библиотеки AWT программами, не являющимися аплетами.

Класс R3Vector позволит задать произвольный вектор и обеспечит все необходимые манипуляции над векторами в трехмерном пространстве.

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

public class R3Vector { private double x, y, z;

public R3Vector(double x, double y, double z) { public R3Vector() throws Exception { §4. Проект Изображение полиэдра x = Xterm.inputDouble("X-коорд. вектора проектирования -> ");

y = Xterm.inputDouble("Y-коорд. вектора проектирования -> ");

z = Xterm.inputDouble("Z-коорд. вектора проектирования -> ");

Для представления вершин полиэдра можно использовать выведенный из класса R3Vector класс Vertex. Конструктор данного класса обязан явным образом (с помощью ключевого слова super) вызвать конструктор его базового класса R3Vector, так как иначе компилятор автоматически вставит вызов конструктора класса R3Vector без параметров.

public class Vertex extends R3Vector { public Vertex(double x, double y, double z) { Ребра полиэдра будем представлять с помощью класса Edge, в каждом экземпляре которого содержатся две private-компоненты типа Vertex, соответствующие началу и концу ребра. В подобных ситуациях для обеспечения возможности получения координат начала и конца ребра используют так называемые методы-селекторы getBegin и getEnd.

public class Edge { private Vertex begin;

private Vertex end;

public Edge(Vertex begin, Vertex end) { this.begin = begin; this.end = end;

public final Vertex getBegin() { public final Vertex getEnd() { Грани полиэдра будем описывать с помощью класса Facet. Так как грань задается последовательностью ее вершин, то в каждом экземпляре класса должен содержаться массив объектов типа Vertex, для получения количества и координат которых необходимо предусмотреть соответствующие методы.

public class Facet { private Vertex[] vertexes;

public Facet(Vertex[] vertexes) { Глава III. Применение ООП к разработке программных проектов this.vertexes = vertexes;

public final int getVertexesQuantity() { return vertexes.length;

public final Vertex getVertex(int i) { Полиэдр в целом, наконец, будем задавать с помощью класса Polyedr.

Каждый экземпляр этого класса будет хранить в массивах vertexes, edges и facets все вершины, ребра и грани полиэдра. При этом оказывается, что часть информации хранится продублированной, так как каждая из граней полиэдра уже содержит все ее вершины. Устранение этого дублирования является еще одной из задач, предлагаемых в конце параграфа.

При создании нового экземпляра класса Polyedr с помощью конструктора вся информация о полиэдре, хранящаяся в файле file в описанном выше формате, должна быть прочитана из него и размещена должным образом в компонентах создаваемого экземпляра. Для реализации этих действий необходимо использование пакетов java.util и java.io, что обуславливает необходимость наличия директив import в начале файла. Все технические детали осуществления чтения информации из файла оставляются читателю, а полный исходный текст проектируемого класса приведен для справки в последней секции параграфа.

import java.util.*;

import java.io.*;

public class Polyedr { private Vertex[] vertexes;

private Edge[] edges;

private Facet[] facets;

public Polyedr(String file) throws Exception { public final int getVertexesQuantity() { return vertexes.length;

public final Vertex getVertex(int i) { public final int getEdgesQuantity() { return edges.length;

§4. Проект Изображение полиэдра public final Edge getEdge(int i) { public final int getFacetsQuantity() { return facets.length;

public final Facet getFacet(int i) { return facets[i];

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

Задачу вывода плоского изображения в отдельном фрейме поручим осуществлять классу AwtDrawer. Графическая библиотека (пакет java.awt) содержит среди множества других класс Frame, позволяющий создать фрейм и, используя простейшие графические примитивы, построить в нем требуемое изображение. Класс AwtDrawer будет являться расширением класса Frame, а основным методом рисования проекции отрезков ребер будет метод draw, изображающий прямолинейный отрезок. Координаты точек при этом предполагаются нормированными и абсцисса и ордината должны быть заключены между нулем и единицей.

import java.awt.*;

public class AwtDrawer extends Frame { private static final int XLEN = 500;

private static final int YLEN = 500;

private static final int DELTA= 100;

private Image offScrImage;

private Graphics offScrGC;

private Graphics g;

public AwtDrawer() { super("Построение изображения полиэдра");

setSize(XLEN+2*DELTA, YLEN+2*DELTA);

setBackground(Color.white);

offScrImage = createImage(XLEN+2*DELTA, YLEN+2*DELTA);

offScrGC = offScrImage.getGraphics();

256 Глава III. Применение ООП к разработке программных проектов offScrGC.setColor(Color.white);

offScrGC.fillRect(0,0,XLEN+2*DELTA, YLEN+2*DELTA);

offScrGC.setColor(Color.black);

public final void draw(double xb, double yb, double xe, double ye) { offScrGC.drawLine(x0, y0, x1, y1);

public void update(Graphics g) { public void paint(Graphics g) { g.drawImage(offScrImage, 0, 0, this);

Поясним назначение некоторых констант, переменных и методов, которые встречаются в реализации класса AwtDrawer.

Первые три строки тела конструктора этого класса последовательно устанавливают заголовок создаваемого фрейма, его размер и цвет фона.

Вокруг области рисования размером XLENxYLEN предусмотрены поля шириной DELTA.

Класс Graphics пакета AWT уже встречался нам при рассмотрении аплетов. Именно в нем определены все основные графические примитивы.

По некоторым причинам, обсуждение которых выходит за рамки нашего курса, изображение сначала строится в так называемом внеэкранном буфере offScrImage, а во фрейм выводится с помощью метода drawImage при вызове методов paint и update. Метод draw, аргументами которого являются числа в диапазоне от 0 до 1, вычисляет соответствующие им координаты фрейма и с помощью метода drawLine рисует заданный отрезок.

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

В качестве первого шага в этом направлении полезно решить относительно простую задачу построения проекции всех ребер полиэдра целиком. Создадим для этих целей класс SimpleDrawer, который вполне логично сделать выведенным из класса AwtDrawer. В качестве компонент в этот класс включим сам полиэдр, ортонормированный базис, состоящий §4. Проект Изображение полиэдра из нормированного вектора проектирования и двух единичных ортогональных друг другу векторов в плоскости проекции, минимальные значения x и y координат проекции вершин полиэдра в плоскости проекции и длину минимальной стороны квадрата, в который целиком поместится вся проекция полиэдра.

Ряд методов класса SimpleDrawer предназначен для нахождения координат проекции произвольного трехмерного вектора, как реальных, так и нормализованных (в той системе координат на плоскости проекции, в которой изображаемой части фрейма соответствует квадрат 0 x 1). Вычисление реальных координат проекции, как это хорошо изy вестно из аналитической геометрии, сводится к вычислению скалярных произведений с помощью статического метода scalMul класса R3Vector, а их нормализация к линейному преобразованию (сдвигу и гомотетии).

public class SimpleDrawer extends AwtDrawer { protected Polyedr p;

protected R3Vector pr;

private R3Vector x;

private R3Vector y;

private double xmin;

private double ymin;

private double size;

private double xProection(R3Vector v) { return R3Vector.scalMul(v, x);

private double yProection(R3Vector v) { return R3Vector.scalMul(v, y);

protected double xnProection(R3Vector v) { return (xProection(v) - xmin)/size;

protected double ynProection(R3Vector v) { return (yProection(v) - ymin)/size;

public SimpleDrawer(Polyedr p, R3Vector pr, double angle) { this.pr = pr.normalize();

Глава III. Применение ООП к разработке программных проектов y = R3Vector.vectMul(x, pr);

R3Vector nx = R3Vector.plus(R3Vector.mul(Math.cos(angle), x), R3Vector ny = R3Vector.plus(R3Vector.mul(Math.sin(angle), x), xmin = ymin = Double.MAX_VALUE;

xmax = ymax = Double.MIN_VALUE;

public final void draw() { public final Segment leftSub(Segment s) { return new Segment(begin, Math.min(end, s.begin));

public final Segment rightSub(Segment s) { return new Segment(Math.max(begin, s.end), end);

public final Segment intersection(Segment s) { begin = Math.max(begin, s.begin);

end = Math.min(end, s.end);

public final double getBegin() { public final double getEnd() { Указанные действия включают в себя проверку вырожденности отрезка (метод degenerate), а также вычисление пересечения двух отрезков и определения обеих компонент разности двух отрезков. Отрезок [a, b] является вырожденным, если он представляет из себя точку или пустое множество, то есть если a b. Пересечение двух отрезков всегда является отрезком (возможно, вырожденным), который вычисляется в методе intersection, а разность двух отрезков всегда состоит из двух отрезков, каждый из которых может оказаться вырожденным. Левая и правая компоненты разности вычисляются с помощью методов leftSub и rightSub соответственно.

Совокупность всех просветов ребра целесообразно хранить в односвязном списке сегментов, для чего будем использовать изученную нами ранее §4. Проект Изображение полиэдра ссылочную реализацию (класс L1ListSegments). В самом начале обработки очередного ребра множество просветов состоит из одного элемента, совпадающего со всем ребром, отрезка [0, 1]. Последовательный учет теней от граней можно считать функцией на пространстве последовательности граней. Легко заметить, что эта функция индуктивна зная список просветов, который учитывает тени от нескольких граней, и тень от еще одной, новой грани, легко вычислить новый список просветов, учитывающий и тень от новой грани. Для этого достаточно для всех просветов вычислить их разности с отрезком тени от грани (см. рис. 24).

В зависимости от расположения отрезков, соответствующих просвету и тени, их разность может оказаться пустой (если просвет целиком попал в тень), состоящей из единственной точки, двух точек, одного отрезка, точки и отрезка, и двух отрезков. Как это уже обсуждалось ранее, мы не будем различать эти ситуации. Гораздо удобнее считать, что разность всегда состоит из двух отрезков, каждый из которых может быть вырожденным.

Приведем ту часть реализации класса ShadowDrawer, которая уже обсуждена нами.

public class ShadowDrawer extends SimpleDrawer { protected R3Vector begin;

protected R3Vector end;

private static final int MAXSIZE = 128;

private L1ListSegments list;

private static final double t0 = 0.;

private static final double t1 = 1.;

private R3Vector R3(double t) { return R3Vector.plus( R3Vector.mul((1.-t), begin), protected final void addShadow(Facet f) { Глава III. Применение ООП к разработке программных проектов Xterm.println("Слишком много видимых отрезков ребра.");

protected void addShadow() { for(int j=0; j= 0.) return new Segment(t1, t0);

if(f0 < 0. && f1 < 0. ) return new Segment(t0, t1);

if (f0 < 0.) return new Segment(t0, t);

return new Segment(t, t1);

Договоримся задавать полупространство, пересечения ребра с которым необходимо уметь вычислять, точкой A на ограничивающей его плоскости и вектором внешней нормали n к этой плоскости. Не разбираясь пока в деталях реализации метода crossWith с указанными аргументами (в тексте программы это точка a и вектор нормали n), обсудим задачу нахождения одномерной тени, решаемую методами shadow, hCross и vCross.

Для реализации метода hCross нахождения пересечения с горизонтальным полупространством нужно найти нормаль к грани (выбрав правильное направление) и вызвать метод crossWith. Ясно, что из соображений эффективности операцию вычисления нормали к грани лучше выполнить только один раз, что и делается в конструкторе класса Facet.

Направление нормали будет правильным при условии положительности скалярного произведения ее с вектором проектирования. Если это условие нарушено, то вектор n следует заменить на противоположный, умножив его на минус единицу.

Вычисление пересечения с вертикальным полупространством с помощью метода vCross удастся реализовать, зная соответствующее ребро грани (точки A и B) и центр грани C. Точку A при этом можно использовать в качестве аргумента для вызова метода crossWith непосредственно, Глава III. Применение ООП к разработке программных проектов а нормаль к вертикальной плоскости, проходящей через ребро AB, находится следующим образом. Сначала вычисляется векторное произведение вектора AB и вектора проектирования. Результат этой операции заведомо является нормалью, но может быть направлен не в ту сторону не наружу, а внутрь.

Так как все грани полиэдра по самому его определению являются выпуклыми многоугольниками, центр каждой из граней всегда находится внутри ее. По этой причине вектор AC всегда направлен внутрь вертикального полупространства, пересечение с которым мы ищем. Если точки A и B являются вершинами грани, следующими друг за другом в порядке против часовой стрелки, то положительность скалярного произведения векторов AC и вычисленного по указанному выше способу вектора нормали гарантирует нужное направление последнего. В противном случае необходимо его умножение на минус единицу. Вычисление центра грани также целесообразно производить единственный раз в конструкторе класса Facet.

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

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

Теперь нам осталось разобраться с последним из методов класса ShadowDrawer методом crossWith нахождения пересечения ребра P Q с полупространством, заданным точкой A и вектором внешней нормали n.

В одномерных координатах точкам P и Q соответствует ноль и единица, а результатом работы метода должны быть одномерные координаты отрезка пересечения.

Рассмотрим функцию f (x) =< n, AX >, где X точка на ребре P Q, x ее одномерная координата, а угловые скобки означают скалярное произведение двух векторов. Эта функция линейна и является знакопостоянной на отрезке [0, 1] в том случае, если ребро P Q целиком лежит вне или внутри полупространства. В случае пересечения ребра с плоскостью, ограничивающей полупространство, одномерная координата точки пересечения находится из уравнения f (x) = 0.

§4. Проект Изображение полиэдра Из вышесказанного следует, что задача нахождения пересечения ребра с полупространством может быть решена таким образом. Вычислим сначала значения функции f (x) в концах отрезка f (0) и f (1) (в программной реализации им соответствуют величины f0 и f1). Если обе эти величины неотрицательны, то пересечение пусто, если, наоборот, они обе отрицательны, то весь отрезок лежит в полупространстве.

Для определения одномерной координаты точки пересечения решим уравнение f (x) = 0. В силу линейности функции f (x) она имеет вид f (x) = + x. Так как f (0) =, а f (1) = +, то коэффициенты и легко определяются. После этого легко вычислить и корень указанного уравнения: = f (0), = f (1) f (0), x = f (0)/(f (1) f (0)).

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

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

4. Некоторые технологические вопросы и оптимизация. Рассматриваемый нами проект является достаточно объемным, а его исходные тексты размещены во многих файлах, что делает особенно полезным использование ряда технологических приемов при работе с ним.

Применение утилиты make значительно облегчает решение задач на модификацию. Используемый в проекте Makefile позволяет корректно откомпилировать текст программы и стартовать процесс построения изображения любого из более, чем 15 полиэдров, файлы с данными которых содержатся в директории data. Для построения изображения куба, например, достаточно выполнения команды make cube.

Бльшая часть возможностей утилиты make, используемых в данном проекте, уже была рассмотрена ранее. Обсудим лишь те действия, которые выполняются при построении цели doc. Вот соответствующий фрагмент из управляющего файла.

doc:

javadoc -d doc -version -author -private *.java Задание на построение цели doc сводится, как видно из этой записи, к вызову утилиты javadoc, являющейся частью исполняющей среды языка Java, с определенным набором параметров. Эта утилита предназначена 270 Глава III. Применение ООП к разработке программных проектов Рис. 26. Фрагмент результата работы утилиты javadoc для автоматической генерации документации, связанной с программным проектом.

При самом первом знакомстве с языком Java было отмечено, что в нем предусмотрены три вида комментариев, из которых до сих пор мы имели дело только с двумя. Многострочный комментарий, начинающийся с символов /** и завершающийся символами */ предназначен для размещения в тексте программы комментариев, которые могут быть впоследствии обработаны утилитой javadoc с целью построения полноценной документации о программе.

Правильное использование этой утилиты позволяет получить описание классов и пакетов в гипертекстовом формате (на языке HTML), что чрезвычайно удобно. Программист обязан, конечно, при написании программы размещать в ее тексте необходимые директивы, распознаваемые утилитой javadoc. Все они, впрочем, имеют очень простые синтаксис и семантику.

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

Как легко убедиться, построенная программа работает достаточно медленно при построении изображения сложного полиэдра, хотя мы и §4. Проект Изображение полиэдра пытались уже в процессе ее создания заботиться об эффективности. Сейчас будет предложен метод, носящий имя фильтрование граней, который позволяет заметно ускорить работу программы.

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

Хорошей идеей является попытка использования ограничивающих прямоугольников для проекций ребер и граней. Во-первых, ограничивающие прямоугольники легко быстро вычислить, а во-вторых, легко проверить, пересекаются ли два таких прямоугольника. Отсутствие пересечения прямоугольников при этом гарантирует отсутствие тени от грани на ребро.

Реализация описанной идеи позволяет заменить для большинства граней ресурсоемкую операцию нахождения тени от нее на определение пересечения ее ограничивающего прямоугольника (который должен вычисляться еще в конструкторе) с ограничивающим прямоугольником ребра (который тоже может быть вычислен заранее). Только в случае их пересечения необходимо будет вызывать метод вычисления тени.

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

Другим возможным способом оптимизации построения изображения является использование двумерного хеширования граней. Основной целью этого метода является полный отказ от рассмотрения далеких граней при построении изображения конкретного ребра.

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

Класс SmartDrawer, полный текст которого приведен ниже, реализует эту идею.

5. Задачи для самостоятельного решения.

Задача 4.2. Оптимизируйте текст эталонного проекта Изображение полиэдра так, чтобы:

a) устранить многократное изображение видимых частей ребер, связанное с особенностями задания полиэдра, описанными на странице 249;

b) реализовать идею фильтрования граней, базируясь на реализации класса ShadowDrawer;

c) минимизировать действия, выполняемые в классе ShadowDrawer, связанные с необходимостью обращения (умножения на минус единицу) нормалей к граням;

d) максимально исправить влияние ошибок округления при работе с числами, заданными в форме с плавающей точкой, которые приводят к тому, что отдельные видимые части ребер не изображаются и наоборот.

Задача 4.3. Модифицируйте текст эталонного проекта Изображение полиэдра так, чтобы:

a) невидимые части ребер изображались пунктиром;

b) грани, имеющие максимальную площадь среди полностью видимых граней, заштриховывалась;

c) изображалась только та часть полиэдра, которая попадает в полупространство, заданное с помощью точки на ограничивающей его плоскости и вектора внешней нормали (эта задача эквивалентна построению изображения предварительно усеченного полиэдра);

d) изображалось сечение полиэдра предварительно заданной плоскостью;

e) строились плоские изображения четырехмерных полиэдров.

Задача 4.4. Модифицируйте текст эталонного проекта Изображение полиэдра так, чтобы вычислялась и печаталась следующая величина:

a) количество видимых вершин;

b) количество полностью видимых ребер;

c) количество частично видимых ребер;

d) количество полностью видимых граней;

e) количество частично видимых граней;

§4. Проект Изображение полиэдра f) количество ребер, удаленных от начала координат не более, чем на единичное растояние;

g) количество граней, удаленных от начала координат не более, чем на единичное растояние;

h) количество граней полиэдра, пересекающихся с заданным отрезком;

i) количество ребер полиэдра, пересекающихся с заданным отрезком;

j) периметр проекции полиэдра;

k) площадь проекции полиэдра.

6. Полный текст проекта. Сначала приведем содержание управляющего файла для утилиты make.

Makefile.

# -*- mode: makefile -*PHONY : all doc clean veryclean cube ccc sticks tagl king dragon \ x29 apple glass4 torus pear vw bones beeth teapot cow babem JAVAFILES := Xterm.java R3Vector.java Vertex.java Edge.java Facet.java \ SmartDrawer.java PolyedrTest.java CLASSFILES := Xterm.class R3Vector.class Vertex.class Edge.class Facet.class \ AwtDrawer.class SimpleDrawer.class ShadowDrawer.class \ SmartDrawer.class PolyedrTest.class %.class: %.java cube: $(CLASSFILES) java PolyedrTest data/cube.geom ccc: $(CLASSFILES) java PolyedrTest data/ccc.geom sticks: $(CLASSFILES) java PolyedrTest data/sticks.geom tagl: $(CLASSFILES) java PolyedrTest data/tagl.geom king: $(CLASSFILES) java PolyedrTest data/king.geom dragon: $(CLASSFILES) java PolyedrTest data/dragon.geom x29: $(CLASSFILES) java PolyedrTest data/x29.geom 274 Глава III. Применение ООП к разработке программных проектов apple: $(CLASSFILES) java PolyedrTest data/apple_logo.geom glass4: $(CLASSFILES) java PolyedrTest data/glass4.geom torus: $(CLASSFILES) java PolyedrTest data/torus.geom pear: $(CLASSFILES) java PolyedrTest data/pear.geom java PolyedrTest data/vw.geom bones: $(CLASSFILES) java PolyedrTest data/foot_bones.geom beeth: $(CLASSFILES) java PolyedrTest data/beethoven.geom teapot: $(CLASSFILES) java PolyedrTest data/teapot.geom cow: $(CLASSFILES) java PolyedrTest data/cow.geom babem: $(CLASSFILES) java PolyedrTest data/babem.geom doc:

javadoc -d doc -version -author -private *.java expand:

for i in Makefile *.java; do expand $$i >$$i.expand; done clean:

veryclean:

rm -f *.class *.expand doc/*.html А вот как выглядят все остальные файлы проекта.

R3Vector.java.

/** * @author Е.А. Роганов * @version 1. * Класс R3Vector, реализующий вектор (Vector) в пространстве (R3).

public class R3Vector { * Координаты вектора.

private double x, y, z;

* Конструктор вектора, заданного его координатами.

* @param x X-координата вектора.

* @param y Y-координата вектора.

* @param z Z-координата вектора.

public R3Vector(double x, double y, double z) { * Конструктор вектора, координаты которого вводятся с клавиатуры.

* @exception Exception Исключительная ситуация, возникающая * при ошибках ввода координат с клавиатуры.

public R3Vector() throws Exception { x = Xterm.inputDouble("X-коорд. вектора проектирования -> ");

y = Xterm.inputDouble("Y-коорд. вектора проектирования -> ");

z = Xterm.inputDouble("Z-коорд. вектора проектирования -> ");

* Получить X-координату вектора.

* @return X-координата вектора.

public final double getX() { * Получить Y-координату вектора.

* @return Y-координата вектора.

public final double getY() { * Получить Z-координату вектора.

* @return Z-координата вектора.

public final double getZ() { * Нормировать ненулевой вектор.

public final R3Vector normalize() { double norm = Math.sqrt(x*x+y*y+z*z);

* Найти сумму двух векторов.

* @param a Первый вектор-слагаемое.

* @param b Второй вектор-слагаемое.

* @return Сумма векторов.

public static R3Vector plus(R3Vector a, R3Vector b) { return new R3Vector(a.x+b.x, a.y+b.y, a.z+b.z);

Глава III. Применение ООП к разработке программных проектов * Добавить заданный вектор.

* @param b Добавляемый вектор.

* @return Вектор-результат.

public final R3Vector plus(R3Vector b) { * Найти разность двух векторов.

* @param a Вектор-уменьшаемое.

* @param b Вектор-вычитаемое.

* @return Разность векторов.

public static R3Vector minus(R3Vector a, R3Vector b) { return new R3Vector(a.x-b.x, a.y-b.y, a.z-b.z);

* Вычесть заданный вектор.

* @param b Вычитаемый вектор.

* @return Вектор-результат.

public final R3Vector minus(R3Vector b) { * Найти произведение вектора на число.

* @param k Число, на которое умножается вектор.

* @param a Исходный вектор.

* @return Вектор-результат.

public static R3Vector mul(double k, R3Vector a) { return new R3Vector(k*a.x, k*a.y, k*a.z);

* Умножить вектор на заданное число.

* @param k Число, на которое умножается вектор.

* @return Вектор-результат.

public final R3Vector mul(double k) { * Найти скалярное произведение векторов.

* @param a Первый вектор.

* @param b Второй вектор.

* @return Скалярное произведение векторов.

public static double scalMul(R3Vector a, R3Vector b) { return a.x*b.x + a.y*b.y + a.z*b.z;

* Найти векторное произведение векторов.

* @param a Первый вектор.

* @param b Второй вектор.

* @return Векторное произведение векторов.

public static R3Vector vectMul(R3Vector a, R3Vector b) { return new R3Vector(a.y*b.z-a.z*b.y, a.z*b.x-a.x*b.z, a.x*b.y-a.y*b.x);

Vertex.java.

/** * @author Е.А. Роганов * @version 1. * Класс Vertex, реализующий вершину полиэдра.

public class Vertex extends R3Vector { * @param x X-координата вершины.

* @param y Y-координата вершины.

* @param z Z-координата вершины.

public Vertex(double x, double y, double z) { Edge.java.

/** * @author Е.А. Роганов * @version 1. * Класс Edge, реализующий ребро полиэдра.

public class Edge { * Начало ребра.

private Vertex begin;

* Конец ребра.

private Vertex end;

* Конструктор.

* @param begin Начало ребра.

* @param end Конец ребра.

public Edge(Vertex begin, Vertex end) { this.begin = begin; this.end = end;

* Получить начало ребра.

* @return Начало ребра.

public final Vertex getBegin() { Глава III. Применение ООП к разработке программных проектов * Получить конец ребра.

* @return Конец ребра.

public final Vertex getEnd() { Facet.java.

/** * @author Е.А. Роганов * @version 1. * Класс Facet, реализующий грань полиэдра.

public class Facet { * Массив вершин полиэдра, принадлежащих грани.

private Vertex[] vertexes;

* Центр грани.

private R3Vector center;

* Вектор нормали к грани.

private R3Vector normal;

* Конструктор.

* @param vertexes Вершины полиэдра, образующие грань.

public Facet(Vertex[] vertexes) { this.vertexes = vertexes;

normal = R3Vector.vectMul(R3Vector.minus(vertexes[1], vertexes[0]), center = new R3Vector(0., 0., 0.);