Этот параграф посвящен рассмотрению еще одного проекта, который позволит
познакомиться с простейшими задачами вычислительной геометрии.
Построение изображения
В книгах [9] и [8] содержится большое количество
дополнительной информации, связанной с рассматриваемой задачей и ее
различными обобщениями. Вопросы работы с пакетом
В настоящее время во многих областях науки и техники используются различные
методы моделирования геометрических объектов в трехмерном пространстве.
Один из способов моделирования состоит в том, чтобы аппроксимировать реальный
объект набором выпуклых плоских многоугольников. Такой набор мы будем называть
Примерами
(рис 13.1) Пример полиэдраПри изображении
Задача 13.1.
Напишите программу, которая строит изображение заданного
В результате решения этой задачи
Изображение
Рассматриваемая задача, таким образом, сводится к следующей: построить
проекцию
(рис 13.2) Изображение полиэдраТакую уточненную постановку задачи иллюстрирует рис. 13.2.
Способ задания
Достаточно часто при задании
Способ представления
Этот способ задания
Информация, представляющая
8 6 24
-0.5 -0.5 0.5
-0.5 0.5 0.5
0.5 0.5 0.5
0.5 -0.5 0.5
-0.5 -0.5 -0.5
-0.5 0.5 -0.5
0.5 0.5 -0.5
0.5 -0.5 -0.5
4 1 2 3 4
4 5 6 2 1
4 3 2 6 7
4 3 7 8 4
4 1 4 8 5
4 8 7 6 5
Первая строка говорит о том, что у куба 8 вершин, 6 граней и 24 (!) ребра. Число 24, вдвое превышающее реальное количество ребер у куба, является результатом уже описанного выше эффекта, — каждое из ребер куба принадлежит ровно двум граням.
Следующая часть файла содержит метрическую информацию — координаты всех
восьми вершин
Технические детали работы с файлами и чтения информации из них могут быть изучены заинтересованными читателями самостоятельно с использованием итогового текста проекта, приведенного в конце параграфа, и литературы, содержащей описание библиотек (пакетов) языка Java.
В данной секции будет построена иерархия классов, необходимых для реализации
рассматриваемого проекта. Здесь же мы рассмотрим (в самых общих чертах)
использование библиотеки
Класс R3Vector позволит задать произвольный вектор и обеспечит все
необходимые манипуляции над векторами в трехмерном пространстве. Полный набор
методов, которые должен реализовывать класс R3Vector,
выяснится в процессе дальнейшего решения задачи.
Пока же заметим, что R3Vector, должен вводиться с клавиатуры, и
предусмотрим дополнительный конструктор специально для этих целей.
public class R3Vector {
private double x, y, z;
public R3Vector(double x, double y, double z) {
this.x = x; this.y = y; this.z = z;
}
public R3Vector() throws Exception {
x = Xterm.inputDouble("X-коорд. вектора проектирования -> ");
y = Xterm.inputDouble("Y-коорд. вектора проектирования -> ");
z = Xterm.inputDouble("Z-коорд. вектора проектирования -> ");
}
}
Для представления вершин R3Vector класс super ) вызвать конструктор его
базового класса R3Vector, так как иначе компилятор автоматически вставит
вызов конструктора класса R3Vector без параметров.
public class Vertex extends R3Vector {
public Vertex(double x, double y, double z) {
super(x, y, z);
}
}
Ребра Edge, в каждом
экземпляре которого содержатся две private -компоненты типа 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() {
return begin;
}
public final Vertex getEnd() {
return end;
}
}
Грани
public class Facet {
private Vertex[] vertexes;
public Facet(Vertex[] vertexes) {
this.vertexes = vertexes;
public final int getVertexesQuantity() {
return vertexes.length;
}
public final Vertex getVertex(int i) {
return vertexes[i];
}
Polyedr.
Каждый экземпляр этого класса будет хранить в массивах edges и
При создании нового экземпляра класса 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) {
return vertexes[i];
}
public final int getEdgesQuantity() {
return edges.length;
}
public final Edge getEdge(int i) {
return edges[i];
}
public final int getFacetsQuantity() {
return facets.length;
}
public final Facet getFacet(int i) {
return facets[i];
}
}
Решаемая задача изображения проекции
Задачу вывода плоского изображения в отдельном фрейме поручим осуществлять
классу AwtDrawer. Графическая библиотека (пакет java. )
содержит среди множества других класс 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);
g = getGraphics();
show();
offScrImage = createImage(XLEN+2*DELTA, YLEN+2*DELTA);
offScrGC = offScrImage.getGraphics();
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) {
int x0 = DELTA + (int)(XLEN * xb);
int y0 = DELTA + (int)(YLEN * yb);
int x1 = DELTA + (int)(XLEN * xe);
int y1 = DELTA + (int)(YLEN * ye);
offScrGC.drawLine(x0, y0, x1, y1);
}
public void update(Graphics g) {
paint(g);
}
public void paint(Graphics g) {
g.drawImage(offScrImage, 0, 0, this);
}
}
Поясним назначение некоторых констант, переменных и методов, которые
встречаются в реализации класса AwtDrawer.
Первые три строки тела конструктора этого класса последовательно
устанавливают
заголовок создаваемого фрейма, его размер и цвет фона. Вокруг области рисования
размером XLENxYLEN предусмотрены поля шириной DELTA.
Класс Graphics пакета offScrImage,
а во фрейм выводится с помощью метода drawImage при вызове методов paint и update.
Метод draw, аргументами которого являются числа в диапазоне от 0 до 1,
вычисляет соответствующие им координаты фрейма и с помощью метода drawLine рисует заданный отрезок.
Вернемся теперь к задаче определения множества отрезков на плоскости, которые должны быть изображены.
В качестве первого шага в этом направлении полезно решить относительно
простую
задачу построения проекции всех ребер SimpleDrawer, который вполне логично сделать выведенным из
класса AwtDrawer. В качестве компонент в этот класс включим сам
Ряд методов класса SimpleDrawer предназначен для нахождения координат
проекции произвольного трехмерного вектора, как реальных, так и нормализованных
(в той системе координат на плоскости проекции, в которой изображаемой части
фрейма соответствует квадрат $$0 \leqslant x \leqslant 1 \land 0 \leqslant
y
\leqslant 1$$ ). Вычисление реальных координат проекции, как это хорошо
известно
из аналитической геометрии, сводится к вычислению скалярных произведений с
помощью статического метода 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.p = p;
this.pr = pr.normalize();
double a = pr.getX();
double b = pr.getY();
double c = pr.getZ();
if (a != 0. || b != 0.) {
x = new R3Vector(-b, a, 0.);
} else {
x = new R3Vector(0., c, -b);
}
y = R3Vector.vectMul(x, pr);
x.normalize();
y.normalize();
R3Vector nx = R3Vector.plus(R3Vector.mul(Math.cos(angle), x),
R3Vector.mul(-Math.sin(angle), y));
R3Vector ny = R3Vector.plus(R3Vector.mul(Math.sin(angle), x),
R3Vector.mul(Math.cos(angle), y));
x = nx;
y = ny;
xmin = ymin = Double.MAX_VALUE;
double xmax, ymax;
xmax = ymax = Double.MIN_VALUE;
for (int i=0; i<p.getVertexesQuantity(); i++) {
double xi = xProection(p.getVertex(i));
double yi = yProection(p.getVertex(i));
if (xi < xmin) xmin = xi;
if (yi < ymin) ymin = yi;
if (xi > xmax) xmax = xi;
if (yi > ymax) ymax = yi;
}
size = ymax - ymin;
if (xmax - xmin > size) size = xmax - xmin;
}
public final void draw() {
for (int i=0; i<p.getEdgesQuantity(); i++)
drawEdge(p.getEdge(i));
Xterm.print("\n");
}
public void drawEdge(Edge s) {
Vertex begin = s.getBegin();
Vertex end = s.getEnd();
draw(xnProection(begin), ynProection(begin),
xnProection(end), ynProection(end));
Xterm.print(".");
}
}
Всю основную подготовительную работу выполняет конструктор класса. Первой из
его задач является нахождение ортонормированного базиса, одним из векторов
которого является normalize класса R3Vector. Второй из векторов искомой тройки строится с помощью уже
найденного вектора нормали (нормированному x класса SimpleDrawer ).
Третий вектор базиса (компонента y ) находится с помощью вычисления
vectMul ) двух уже найденных. Заключительным шагом является
осуществление поворота на заданный угол angle в плоскости проекции.
Как известно из аналитической геометрии, поворот в плоскости $$Oxy$$
на угол $$\alpha$$ эквивалентен умножению вектора координат $$(x,y)$$ на матрицу$$\left(
\begin{array}{cc}
\cos\alpha -\sin\alpha\\
\sin\alpha \cos\alpha\\
\end{array}
\right).$$
Для осуществления этих операций используются методы mul и plus
класса R3Vector, позволяющие умножить вектор на число и вычислить сумму
двух векторов соответственно.
Вторая задача конструктора класса SimpleDrawer — определение
квадрата
наименьшего размера, в котором целиком поместится проекция всех ребер
Метод draw, который и должен построить проекцию drawEdge, последовательно вызываемого
для всех ребер. Последний из методов вычисляет нормализованные координаты
проекции обрабатываемого ребра и вызывает метод draw базового класса AwtDrawer для рисования требуемого отрезка. Так как для сложных
Наиболее содержательная часть исходной задачи — учет затенения частей
ребер
гранями ShadowDrawer,
обсуждению которого посвящена следующая секция параграфа. В ней выяснится,
что для работы с тенями (точнее с просветами — дополнениями теней)
целесообразно создать еще два класса — Segment и L1ListSegments.
Чуть позже будет
рассмотрен и один из возможных методов оптимизации, позволяющий ускорить
построение изображения сложных SmartDrawer.
(рис 13.3) Иерархия классов проектаМетод main, выполняющий ввод имени файла с описанием изображаемого
PolyedrTest, которым завершается построение иерархии классов,
используемых для решения исходной задачи. Все классы иерархии показаны на
рисунке рис. 13.3.
Так как плоское изображение
(рис 13.4) Тень от грани на ребреЕсли предположить, что бесконечно высоко расположен источник света, то
на каждом ребре образуются освещенные и затененные участки. Первые мы будем
называть
Для получения изображения видимой части ребра нужно учесть тени от всех
граней
Важным наблюдением, существенно упрощающим искомый алгоритм, является тот
факт,
что задача нахождения теней и просветов на конкретном ребре — одномерная. Сопоставив началу ребра координату 0, а концу — 1, мы
можем установить взаимно однозначное соответствие между трехмерными
координатами точек ребра и введенными одномерными координатами.
После этого каждый из просветов будет представлять собой отрезок, а
реализовывать его будет класс Segment, в каждом экземпляре которого
должны храниться
одномерные координаты начала и конца обрабатываемого отрезка. Методы данного
класса обязаны обеспечить все необходимые действия с отрезками, которые
понадобятся при определении множества просветов.
public class Segment {
private double begin, end;
public Segment(double begin, double end) {
this.begin = begin; this.end = end;
}
public final boolean degenerate() {
return begin >= end;
}
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);
return this;
}
public final double getBegin() {
return begin;
}
public final double getEnd() {
return end;
}
}
Указанные действия включают в себя проверку degenerate ), а также вычисление пересечения двух отрезков и определения
обеих компонент разности двух отрезков. Отрезок $$[a,b]$$ является
вырожденным,
если он представляет из себя точку или пустое множество, то есть если $$a \geqslant b$$. Пересечение двух отрезков всегда является отрезком
(возможно,
вырожденным), который вычисляется в методе intersection, а разность двух
отрезков всегда состоит из двух отрезков, каждый из которых может
оказаться вырожденным. Левая и правая компоненты разности вычисляются с
помощью методов leftSub и rightSub соответственно.
(рис 13.5) Разность просвета и тениСовокупность всех просветов ребра целесообразно хранить в односвязном списке
сегментов, для чего будем использовать изученную нами ранее ссылочную
реализацию (класс L1ListSegments ). В самом начале обработки очередного
ребра множество просветов состоит из одного элемента, совпадающего со
всем ребром, — отрезка $$[0,1]$$. Последовательный учет теней от
граней
можно считать функцией на пространстве последовательности граней. Легко
заметить, что эта функция индуктивна — зная список просветов, который
учитывает тени от нескольких граней, и тень от еще одной, новой грани,
легко вычислить новый список просветов, учитывающий и тень от новой грани.
Для этого достаточно для всех просветов вычислить их разности с отрезком
тени от грани (см. рис. 13.5).
В зависимости от расположения отрезков, соответствующих просвету и тени, их разность может оказаться пустой (если просвет целиком попал в тень), состоящей из единственной точки, двух точек, одного отрезка, точки и отрезка, и двух отрезков. Как это уже обсуждалось ранее, мы не будем различать эти ситуации. Гораздо удобнее считать, что разность всегда состоит из двух отрезков, каждый из которых может быть вырожденным.
Приведем ту часть реализации класса 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),
R3Vector.mul(t, end) );
}
protected final void addShadow(Facet f) {
try {
Segment s = shadow(f);
if (!s.degenerate()) {
list.toFront();
while (!list.end()) {
Segment next = list.erase();
Segment left = next.leftSub(s);
if (!left.degenerate()) {
list.insert(left);
list.forward();
}
Segment right = next.rightSub(s);
if (!right.degenerate()) {
list.insert(right);
list.forward();
}
}
}
} catch(Exception e) {
Xterm.println("Слишком много видимых отрезков ребра.");
System.exit(0);
}
}
protected void addShadow() {
for(int j=0; j<p.getFacetsQuantity(); j++)
addShadow(p.getFacet(j));
}
public ShadowDrawer(Polyedr p, R3Vector pr, double angle) {
super(p, pr, angle);
list = new L1ListSegments(MAXSIZE);
}
public final void drawEdge(Edge s) {
begin = s.getBegin();
end = s.getEnd();
list.clear();
try {
list.insert(new Segment(t0, t1));
} catch(Exception e) {;}
addShadow();
try {
for (list.toFront(); ! list.end(); list.forward()) {
Segment u = list.after();
R3Vector begin = R3(u.getBegin());
R3Vector end = R3(u.getEnd());
draw(xnProection(begin), ynProection(begin),
xnProection(end), ynProection(end));
}
} catch(Exception e) {;}
Xterm.print(".");
}
}
Метод drawEdge фиксирует обрабатываемое ребро, записывая его начало и
конец в компоненты begin и end, и инициализирует список просветов list, помещая в него единственный элемент — ребро целиком.
Затем с помощью вызова метода addShadow производится учет теней от всех
граней R3 по известной из аналитической геометрии формуле.
Учет тени от конкретной грани производится путем определения одномерной тени
на обрабатываемом ребре с помощью вызова метода shadow и
индуктивного перевычисления списка просветов по алгоритму, описанному выше.
Отметим дополнительно, что вырожденные отрезки в список просветов никогда не
включаются.
Заключительным этапом решения задачи является реализация метода shadow.
Этот метод должен определить отрезок на обрабатываемом ребре, который
представляет собой тень от фиксированной грани
Прежде всего следует разобраться с тем, что же такое тень от грани.
Сначала заметим, что вертикальные грани
дают пустую тень. Для остальных граней множество затеняемых ими точек
пространства образует
Тень от грани на ребро при этом оказывается просто пересечением ребра с этой призмой. Заметим, что призму следует считать открытой, т.е. считать, что граница призмы тени не принадлежит, так как в противном случае каждая грань будет затенять сама себя и изображение окажется пустым.
(рис 13.6) Нахождение тени от граниЕстественно попытаться свести нахождение пересечения ребра с призмой к каким-нибудь более элементарным операциям. Мы сделаем это, представив призму в виде пересечения открытых полупространств. Например, треугольную призму можно представить в виде пересечения четырех полупространств (см. рис. 13.6).
Первое полупространство ограничено плоскостью, проходящей через грань
Искомое пересечение ребра и призмы, представляющей собой тень, сводится
теперь к последовательному нахождению пересечения ребра с полупространствами
(сначала горизонтальным, а затем — всеми вертикальными). Приведем реализацию
всех необходимых для этого методов класса ShadowDrawer.
private static final double EPSILON = 1.e-12;
private Segment shadow(Facet f) {
if (f.vertical(pr))
return new Segment(t1, t0);
int n = f.getVertexesQuantity();
Vertex a = f.getVertex(n-1);
Vertex b = f.getVertex(0);
Segment result = hCross(f, a);
if (result.degenerate()) return result;
result.intersection(vCross(a, b, f.getCenter()));
if (result.degenerate()) return result;
for (int i=1; i<n; i++) {
a = b;
b = f.getVertex(i);
result.intersection(vCross(a, b, f.getCenter()));
if (result.degenerate()) return result;
}
return result;
}
private Segment hCross(Facet f, R3Vector a) {
R3Vector n = f.getNormal();
if (R3Vector.scalMul(n, pr) < 0.0) n.mul(-1);
return crossWith(a, n);
}
private Segment vCross(R3Vector a, R3Vector b, R3Vector c) {
R3Vector n = R3Vector.vectMul(R3Vector.minus(b,a), pr);
if (R3Vector.scalMul(n, R3Vector.minus(a,c)) < 0.0) n.mul(-1);
return crossWith(a, n);
}
private Segment crossWith(R3Vector a, R3Vector n) {
double f0 = R3Vector.scalMul(n, R3Vector.minus(begin, a));
double f1 = R3Vector.scalMul(n, R3Vector.minus(end, a));
if(Math.abs(f0) < EPSILON) f0 = 0.;
if(Math.abs(f1) < EPSILON) f1 = 0.;
if(f0 >= 0. f1 >= 0.) return new Segment(t1, t0);
if(f0 < 0. f1 < 0. ) return new Segment(t0, t1);
double t = - f0 / (f1 - f0);
if (f0 < 0.) return new Segment(t0, t);
return new Segment(t, t1);
}
Договоримся задавать полупространство, пересечения ребра с которым
необходимо уметь вычислять, точкой $$A$$ на ограничивающей его
плоскости и
вектором crossWith с указанными аргументами
(в тексте программы это точка a и вектор нормали n ),
обсудим задачу нахождения
одномерной тени, решаемую методами shadow, hCross и vCross.
Для реализации метода hCross нахождения пересечения с горизонтальным
полупространством нужно найти нормаль к грани (выбрав правильное
направление)
и вызвать метод crossWith. Ясно, что из соображений эффективности
операцию вычисления нормали к грани лучше выполнить только один раз, что и
делается в конструкторе класса
Вычисление пересечения с вертикальным полупространством с помощью метода vCross удастся реализовать, зная соответствующее ребро грани (точки $$A$$ и $$B$$ ) и центр грани $$C$$. Точку $$A$$ при этом можно использовать в
качестве аргумента для вызова метода crossWith непосредственно, а
нормаль к вертикальной плоскости, проходящей через ребро $$AB$$,
находится
следующим образом. Сначала вычисляется
Так как все грани
Вернемся теперь к методу shadow. Если грань, одномерную тень от
которой
мы ищем, вертикальна, то ее тень пуста. В этом случае возвращаемый отрезок
тени должен быть вырожден, что и реализуется в первых двух строках тела
метода.
Для невертикальной грани сначала вычисляется отрезок result,
являющийся
результатом пересечения ребра с result с вертикальными полупространствами,
соответствующими ребрам. При этом вычисления немедленно прекращаются, если
будет получен
Теперь нам осталось разобраться с последним из методов класса ShadowDrawer — методом crossWith нахождения пересечения ребра $$PQ$$ с полупространством, заданным точкой $$A$$ и вектором
внешней
нормали $$\vec n$$.
В одномерных координатах точкам $$P$$ и $$Q$$ соответствует
ноль и единица, а
результатом работы метода должны быть одномерные координаты отрезка
пересечения.
Рассмотрим функцию $$f(x) = <\vec n, \overrightarrow{AX}>$$, где $$X$$ — точка на ребре $$PQ$$, $$x$$ — ее одномерная координата, а угловые скобки означают скалярное произведение двух векторов. Эта функция линейна и является знакопостоянной на отрезке $$[0,1]$$ в том случае, если ребро $$PQ$$ целиком лежит вне или внутри полупространства. В случае пересечения ребра с плоскостью, ограничивающей полупространство, одномерная координата точки пересечения находится из уравнения $$f(x) = 0$$.
Из вышесказанного следует, что задача нахождения пересечения ребра с
полупространством может быть решена таким образом. Вычислим сначала значения
функции $$f(x)$$ в концах отрезка — $$f(0)$$ и $$f(1)$$ (в программной реализации
им соответствуют величины f0 и f1 ). Если обе эти величины
неотрицательны, то пересечение пусто, если, наоборот, они обе отрицательны,
то весь отрезок лежит в полупространстве.
Для определения одномерной координаты точки пересечения решим уравнение $$f(x) = 0$$. В силу линейности функции $$f(x)$$ она имеет вид $$f(x) = \alpha + \beta x$$. Так как $$f(0) = \alpha$$, а $$f(1) = \alpha + \beta$$, то коэффициенты $$\alpha$$ и $$\beta$$ легко определяются. После этого легко вычислить и корень указанного уравнения: $$\alpha = f(0)$$, $$\beta = f(1) - f(0)$$, $$x = -f(0)/(f(1) - f(0))$$.
Теперь остается выбрать только нужную часть отрезка, что и реализовано в
двух последних строках тела метода crossWith. В заключение обсудим
назначение третьей и четвертой строк, в которых используется малая по
абсолютной величине константа EPSILON. Их роль — попытка исправить
те ошибки в работе метода, которые обусловлены приближенными вычислениями
с числами типа double. В результате ошибок округления некоторые видимые
части ребер не изображаются и наоборот.
Добавление указанных операторов несколько улучшает ситуацию, не исправляя ее полностью. Одна из задач, предназначенных для самостоятельного решения, предлагает справиться с этой проблемой.
Рассматриваемый нами проект является достаточно объемным, а его исходные тексты размещены во многих файлах, что делает особенно полезным использование ряда технологических приемов при работе с ним.
Применение утилиты make значительно облегчает решение задач на
модификацию. Используемый в проекте Makefile позволяет корректно
откомпилировать текст программы и стартовать процесс построения изображения
любого из более, чем 15 data. Для построения изображения куба, например, достаточно
выполнения команды make .
Большая часть возможностей утилиты make, используемых в данном
проекте,
уже была рассмотрена ранее. Обсудим лишь те действия, которые выполняются при
построении цели doc. Вот соответствующий фрагмент из управляющего
файла.
doc:
javadoc -d doc -version -author -private *.java
Задание на построение цели doc сводится, как видно из этой записи, к
вызову утилиты
При самом первом знакомстве с языком Java было отмечено, что в нем
предусмотрены /** и завершающийся символами */ предназначен для размещения
в тексте программы комментариев, которые могут быть впоследствии обработаны
утилитой
Правильное использование этой утилиты позволяет получить описание классов и
пакетов в гипертекстовом формате (на языке HTML), что чрезвычайно удобно.
Программист обязан, конечно, при написании программы размещать в ее тексте
необходимые директивы, распознаваемые утилитой
(рис 13.7) Фрагмент результата работы утилитыПриведенный в последней секции параграфа полный текст проекта иллюстрирует
использование таких комментариев. Иерархия классов проекта "Изображение
Как легко убедиться, построенная программа работает достаточно медленно при
построении изображения сложного
Основное время в процессе нахождения плоского изображения
Хорошей идеей является попытка использования
Реализация описанной идеи позволяет заменить для большинства граней
ресурсоемкую операцию нахождения тени от нее на определение пересечения
ее
Поскольку для каждого конкретного ребра большая часть
граней является далекими, то скорость построения изображения
Другим возможным способом оптимизации построения изображения является
использование
Для реализации этой идеи вся прямоугольная область изображения разбивается
на
небольшие квадратные гнезда и при инициализации hashFacets, который
рассматривается как одномерный список граней, имеющих отношение к
конкретному гнезду, записываются все их номера. При построении же
изображения каждого из ребер необходимо будет искать тень только от тех граней,
которые находятся в гнездах, соответствующих ребру.
Класс SmartDrawer, полный текст которого приведен ниже, реализует эту
идею.
Задача 13.2.
Оптимизируйте текст эталонного проекта "Изображение
a) устранить многократное изображение видимых частей ребер, связанное с
особенностями задания
b) реализовать идею ShadowDrawer ;
c) минимизировать действия, выполняемые в классе ShadowDrawer,
связанные с необходимостью обращения (умножения на минус единицу) нормалей
к граням;
d) максимально исправить влияние ошибок округления при работе с числами, заданными в форме с плавающей точкой, которые приводят к тому, что отдельные видимые части ребер не изображаются и наоборот.
Задача 13.3.
Модифицируйте текст эталонного проекта "Изображение
a) невидимые части ребер изображались пунктиром;
b) грани, имеющие максимальную площадь среди полностью видимых граней, заштриховывалась;
c) изображалась только та часть
d) изображалось сечение
e) строились плоские изображения четырехмерных
Задача 13.4.
Модифицируйте текст эталонного проекта "Изображение
a) количество видимых вершин;
b) количество полностью видимых ребер;
c) количество частично видимых ребер;
d) количество полностью видимых граней;
e) количество частично видимых граней;
f) количество ребер, удаленных от начала координат не более, чем на единичное растояние;
g) количество граней, удаленных от начала координат не более, чем на единичное растояние;
h) количество граней
i) количество ребер
j) периметр проекции
k) площадь проекции
Сначала приведем содержание управляющего файла для утилиты 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
JAVAC = javac
JAVAFILES := Xterm.java R3Vector.java Vertex.java Edge.java Facet.java \
Polyedr.java Segment.java L1ListSegments.java \
AwtDrawer.java SimpleDrawer.java ShadowDrawer.java \
SmartDrawer.java PolyedrTest.java
CLASSFILES := Xterm.class R3Vector.class Vertex.class Edge.class Facet.class \
Polyedr.class Segment.class L1ListSegments.class \
AwtDrawer.class SimpleDrawer.class ShadowDrawer.class \
SmartDrawer.class PolyedrTest.class
%.class: %.java
$(JAVAC) $<
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
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
vw: $(CLASSFILES)
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:
rm -f *.class *.expand
veryclean:
rm -f *.class *.expand doc/*.html
А вот как выглядят все остальные файлы проекта.
R3Vector.java
/**
* @author Е.А. Роганов
* @version 1.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) {
this.x = x; this.y = y; this.z = 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() {
return x;
}
/**
* Получить Y-координату вектора.
* @return Y-координата вектора.
*/
public final double getY() {
return y;
}
/**
* Получить Z-координату вектора.
* @return Z-координата вектора.
*/
public final double getZ() {
return z;
}
/**
* Нормировать ненулевой вектор.
*/
public final R3Vector normalize() {
double norm = Math.sqrt(x*x+y*y+z*z);
x /= norm; y /= norm; z /= norm;
return this;
}
/**
* Найти сумму двух векторов.
* @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);
}
/**
* Добавить заданный вектор.
* @param b Добавляемый вектор.
* @return Вектор-результат.
*/
public final R3Vector plus(R3Vector b) {
x += b.x; y += b.y; z += b.z;
return this;
}
/**
* Найти разность двух векторов.
* @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) {
x -= b.x; y -= b.y; z -= b.z;
return this;
}
/**
* Найти произведение вектора на число.
* @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) {
x *= k; y *= k; z *= k;
return this;
}
/**
* Найти скалярное произведение векторов.
* @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.1
* Класс Vertex, реализующий вершину полиэдра.
*/
public class Vertex extends R3Vector {
/**
* Конструктор.
* @param x X-координата вершины.
* @param y Y-координата вершины.
* @param z Z-координата вершины.
*/
public Vertex(double x, double y, double z) {
super(x, y, z);
}
}
Edge.java
/**
* @author Е.А. Роганов
* @version 1.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() {
return begin;
}
/**
* Получить конец ребра.
* @return Конец ребра.
*/
public final Vertex getEnd() {
return end;
}
}
Facet.java
/**
* @author Е.А. Роганов
* @version 1.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]),
R3Vector.minus(vertexes[2], vertexes[0]));
center = new R3Vector(0., 0., 0.);
for (int i=0; i<vertexes.length; i++) {
center.plus(vertexes[i]);
}
center.mul(1./(double)vertexes.length);
}
/**
* Получить количество вершин.
* @return Количество вершин грани.
*/
public final int getVertexesQuantity() {
return vertexes.length;
}
/**
* Получить вершину.
* @param i Номер вершины.
* @return Вершина грани.
*/
public final Vertex getVertex(int i) {
return vertexes[i];
}
/**
* Получить центр грани.
* @return Центр грани.
*/
public final R3Vector getCenter() {
return center;
}
/**
* Получить нормаль к грани.
* @return Нормаль грани.
*/
public final R3Vector getNormal() {
return normal;
}
/**
* Является ли грань "вертикальной"?
* @param pr Вектор проектирования.
* @return Параллельна ли грань вектору проектирования?
*/
public final boolean vertical(R3Vector pr) {
return R3Vector.scalMul(normal, pr) == 0.;
}
}
Polyedr.java
import java.util.*;
import java.io.*;
/**
* @author Е.А. Роганов
* @version 1.1
* Класс Polyedr, реализующий полиэдр.
*/
public class Polyedr {
/**
* Массив вершин полиэдра.
*/
private Vertex[] vertexes;
/**
* Массив ребер полиэдра.
*/
private Edge[] edges;
/**
* Массив граней полиэдра.
*/
private Facet[] facets;
/**
* Конструктор класса.
* @param file Файл, содержащий описание полиэдра.
* @exception Exception Исключительная ситуация, возникающая при
* ошибках чтения или преобразования данных.
*/
public Polyedr(String file) throws Exception {
RandomAccessFile f = new RandomAccessFile(file, "r");
StringTokenizer st = new StringTokenizer(f.readLine());
vertexes = new Vertex[Integer.parseInt(st.nextToken())];
facets = new Facet[Integer.parseInt(st.nextToken())];
edges = new Edge[Integer.parseInt(st.nextToken())];
for (int i=0; i<vertexes.length; i++) {
st = new StringTokenizer(f.readLine());
double x = Double.valueOf(st.nextToken()).doubleValue();
double y = Double.valueOf(st.nextToken()).doubleValue();
double z = Double.valueOf(st.nextToken()).doubleValue();
vertexes[i] = new Vertex(x,y,z);
}
int k = 0;
for (int i=0; i<facets.length; i++) {
st = new StringTokenizer(f.readLine());
int size = Integer.parseInt(st.nextToken());
Vertex[] facet = new Vertex[size];
facet[0] = vertexes[Integer.parseInt(st.nextToken()) - 1];
for (int j=1; j<size; j+=1) {
facet[j] = vertexes[Integer.parseInt(st.nextToken()) - 1];
edges[k++] = new Edge(facet[j], facet[j-1]);
}
edges[k++] = new Edge(facet[size-1], facet[0]);
facets[i] = new Facet(facet);
}
}
/**
* Получить количество вершин.
* @return Количество вершин полиэдра.
*/
public final int getVertexesQuantity() {
return vertexes.length;
}
/**
* Получить вершину.
* @param i Номер вершины.
* @return Вершина полиэдра.
*/
public final Vertex getVertex(int i) {
return vertexes[i];
}
/**
* Получить количество ребер.
* @return Количество ребер полиэдра.
*/
public final int getEdgesQuantity() {
return edges.length;
}
/**
* Получить ребро.
* @param i Номер ребра.
* @return Ребро полиэдра.
*/
public final Edge getEdge(int i) {
return edges[i];
}
/**
* Получить количество граней.
* @return Количество граней полиэдра.
*/
public final int getFacetsQuantity() {
return facets.length;
}
/**
* Получить грань.
* @param i Номер грани.
* @return Грань полиэдра.
*/
public final Facet getFacet(int i) {
return facets[i];
}
}
Segment.java
/**
* @author Е.А. Роганов
* @version 1.q
* Класс Segment, реализующий одномерный отрезок.
*/
public class Segment {
/**
* Координаты начала и конца отрезка.
*/
private double begin, end;
/**
* Конструктор отрезка.
* @param begin Начало отрезка.
* @param end Начало отрезка.
*/
public Segment(double begin, double end) {
this.begin = begin; this.end = end;
}
/**
* Вырожден ли отрезок?
* @return Вырожден ли отрезок?
*/
public final boolean degenerate() {
return begin >= end;
}
/**
* Найти левый отрезок разности с отрезком s.
* @param s Вычитаемый отрезок.
* @return Левый отрезок разности.
*/
public final Segment leftSub(Segment s) {
return new Segment(begin, Math.min(end, s.begin));
}
/**
* Найти правый отрезок разности с отрезком s.
* @param s Вычитаемый отрезок.
* @return Правый отрезок разности.
*/
public final Segment rightSub(Segment s) {
return new Segment(Math.max(begin, s.end), end);
}
/**
* Найти пересечение с отрезком s.
* @param s Отрезок, с которым находится пересечение.
* @return Отрезок-пересечение.
*/
public final Segment intersection(Segment s) {
begin = Math.max(begin, s.begin);
end = Math.min(end, s.end);
return this;
}
/**
* Получить начало отрезка.
* @return Начало отрезка.
*/
public final double getBegin() {
return begin;
}
/**
* Получить конец отрезка.
* @return Конец отрезка.
*/
public final double getEnd() {
return end;
}
}
L1ListSegments.java
/**
* @author Е.А. Роганов
* @version 1.1
* Класс L1ListSegments, реализующий односвязный список отрезков.
*/
public class L1ListSegments {
/**
* Массив отрезков.
*/
private Segment[] array;
/**
* Массив ссылок.
*/
private int[] next;
/**
* Нил списка.
*/
private int nilList;
/**
* Нил свободного места.
*/
private int nilFree;
/**
* Элемент до указателя.
*/
private int before;
/**
* Элемент за указателем.
*/
private int after;
/**
* Связать два элемента.
* @param first Первый элемент.
* @param second Второй элемент.
*/
private void link(int first, int second) {
next[first] = second;
}
/**
* Захватить место.
* @return Индекс занимаемого элемента.
*/
private int mallocIndex() {
int index = next[nilFree];
link(nilFree, next[index]);
return index;
}
/**
* Освободить место.
* @param index Индекс освобождаемого элемента.
*/
private void freeIndex(int index) {
link(index, next[nilFree]);
link(nilFree, index);
}
/**
* Конструктор класса.
* @param size Максимальный размер списка.
*/
public L1ListSegments(int size) {
array = new Segment[size];
next = new int[size + 2];
nilList = size;
nilFree = size + 1;
link(nilList, nilList);
link(nilFree, 0);
for (int i=0; i<size-1; i++)
link(i, i+1);
link(size-1, nilFree);
before = after = nilList;
}
/**
* Пуст ли список?
* @return Пуст ли список?
*/
public final boolean empty() {
return next[nilList] == nilList;
}
/**
* Сделать список пустым.
*/
public final void clear() {
try {
toFront();
while(true)
erase();
} catch(Exception e) {
;
}
}
/**
* Передвинуть указатель в начало списка.
*/
public final void toFront() {
before = nilList;
after = next[nilList];
}
/**
* Указатель в конце списка?
* @return Указатель в конце списка?
*/
public final boolean end() {
return after == nilList;
}
/**
* Передвинуть указатель вперед.
* @exception Exception Исключительная ситуация, возникающая при
* попытке передвинуть вперед указатель, находящийся в конце списка.
*/
public final void forward() throws Exception {
if (after == nilList) throw new Exception();
before = after;
after = next[after];
}
/**
* Получить элемент за указателем.
* @return Элемент за указателем.
* @exception Exception Исключительная ситуация, возникающая при
* попытке получить элемент за указателем, находящимся в конце списка.
*/
public final Segment after() throws Exception {
return array[after];
}
/**
* Добавить элемент за указателем.
* @param val Включаемый отрезок (сегмент).
* @exception Exception Исключительная ситуация, возникающая при
* попытке добавить элемент в заполненный до конца список.
*/
public final void insert(Segment val) throws Exception {
int index = mallocIndex();
link(before, index);
link(index, after);
after = index;
array[index] = val;
}
/**
* Удалить элемент за указателем.
* @return Удаляемый элемент.
* @exception Exception Исключительная ситуация, возникающая при
* попытке удалить элемент из пустого списка.
*/
public final Segment erase() throws Exception {
Segment val = array[after];
int index = after;
after = next[index];
link(before, after);
freeIndex(index);
return val;
}
}
AwtDrawer.java
import java.awt.*;
/**
* @author Е.А. Роганов
* @version 1.1
* Класс AwtDrawer, обеспечивающий визуализацию
* плоского изображения.
*/
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);
g = getGraphics();
show();
offScrImage = createImage(XLEN+2*DELTA, YLEN+2*DELTA);
offScrGC = offScrImage.getGraphics();
offScrGC.setColor(Color.white);
offScrGC.fillRect(0,0,XLEN+2*DELTA, YLEN+2*DELTA);
offScrGC.setColor(Color.black);
}
/**
* Изобразить отрезок на плоскости, заданный его концами.
* @param xb X-координата начала отрезка ( 0 <= xb <= 1 ).
* @param yb Y-координата начала отрезка ( 0 <= yb <= 1 ).
* @param xe X-координата конца отрезка ( 0 <= xe <= 1 ).
* @param ye Y-координата конца отрезка ( 0 <= ye <= 1 ).
*/
public final void draw(double xb, double yb, double xe, double ye) {
int x0 = DELTA + (int)(XLEN * xb);
int y0 = DELTA + (int)(YLEN * yb);
int x1 = DELTA + (int)(XLEN * xe);
int y1 = DELTA + (int)(YLEN * ye);
offScrGC.drawLine(x0, y0, x1, y1);
}
/**
* Переизобразить содержимое фрейма.
*/
public void update(Graphics g) {
paint(g);
}
public void paint(Graphics g) {
g.drawImage(offScrImage, 0, 0, this);
}
}
SimpleDrawer.java
/**
* @author Е.А. Роганов
* @version 1.1
* Класс SimpleDrawer, обеспечивающий изображение проекции полиэдра.
*/
public class SimpleDrawer extends AwtDrawer {
/**
* Полиэдр.
*/
protected Polyedr p;
/**
* Единичный вектор проектирования.
*/
protected R3Vector pr;
/**
* Единичный X-вектор плоскости проектирования.
*/
private R3Vector x;
/**
* Единичный Y-вектор плоскости проектирования.
*/
private R3Vector y;
/**
* Минимальная X-координата проекции полиэдра.
*/
private double xmin;
/**
* Минимальная Y-координата проекции полиэдра.
*/
private double ymin;
/**
* Размер проекции полиэдра.
*/
private double size;
/**
* Вычислить X-координату проекции точки.
* @param v Трехмерный вектор.
* @return X-координата проекции этого вектора.
*/
private double xProection(R3Vector v) {
return R3Vector.scalMul(v, x);
}
/**
* Вычислить Y-координату проекции точки.
* @param v Трехмерный вектор.
* @return Y-координата проекции этого вектора.
*/
private double yProection(R3Vector v) {
return R3Vector.scalMul(v, y);
}
/**
* Вычислить нормализованную X-координату проекции точки.
* @param v Трехмерный вектор.
* @return Нормализованная X-координата проекции этого вектора.
*/
protected double xnProection(R3Vector v) {
return (xProection(v) - xmin)/size;
}
/**
* Вычислить нормализованную Y-координату проекции точки.
* @param v Трехмерный вектор.
* @return Нормализованная Y-координата проекции этого вектора.
*/
protected double ynProection(R3Vector v) {
return (yProection(v) - ymin)/size;
}
/**
* Конструктор класса.
* @param p Полиэдр.
* @param pr Вектор проектирования.
* @param angle Угол поворота в плоскости проекции.
*/
public SimpleDrawer(Polyedr p, R3Vector pr, double angle) {
this.p = p;
this.pr = pr.normalize();
double a = pr.getX();
double b = pr.getY();
double c = pr.getZ();
if (a != 0. || b != 0.) {
x = new R3Vector(-b, a, 0.);
} else {
x = new R3Vector(0., c, -b);
}
y = R3Vector.vectMul(x, pr);
x.normalize();
y.normalize();
R3Vector nx = R3Vector.plus( R3Vector.mul(Math.cos(angle), x),
R3Vector.mul(-Math.sin(angle), y) );
R3Vector ny = R3Vector.plus( R3Vector.mul(Math.sin(angle), x),
R3Vector.mul(Math.cos(angle), y) );
x = nx;
y = ny;
xmin = ymin = Double.MAX_VALUE;
double xmax, ymax;
xmax = ymax = Double.MIN_VALUE;
for (int i=0; i<p.getVertexesQuantity(); i++) {
double xi = xProection(p.getVertex(i));
double yi = yProection(p.getVertex(i));
if (xi < xmin) xmin = xi;
if (yi < ymin) ymin = yi;
if (xi > xmax) xmax = xi;
if (yi > ymax) ymax = yi;
}
size = ymax - ymin;
if (xmax - xmin < size) size = xmax - xmin;
}
/**
* Изобразить проекцию полиэдра.
*/
public final void draw() {
for (int i=0; i<p.getEdgesQuantity(); i++)
drawEdge(p.getEdge(i));
Xterm.print("\n");
}
/**
* Изобразить ребро полиэдра.
* @param s Обрабатываемое ребро полиэдра.
*/
public void drawEdge(Edge s) {
Vertex begin = s.getBegin();
Vertex end = s.getEnd();
draw(xnProection(begin), ynProection(begin),
xnProection(end), ynProection(end));
Xterm.print(".");
}
}
ShadowDrawer.java
/**
* @author Е.А. Роганов
* @version 1.1
* Класс 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 EPSILON = 1.e-12;
/**
* Одномерная координата начала обрабатываемого ребра.
*/
private static final double t0 = 0.;
/**
* Одномерная координата конца обрабатываемого ребра.
*/
private static final double t1 = 1.;
/**
* Вычислить пространственные координаты точки ребра,
* заданной одномерной координатой.
* @param t Одномерная координата точки на ребре.
* @return Трехмерная координата этой точки ребра.
*/
private R3Vector R3(double t) {
return R3Vector.plus( R3Vector.mul((1.-t), begin),
R3Vector.mul(t, end) );
}
/**
* Вычислить одномерный отрезок тени от грани.
* @param f Грань полиэдра.
* @return Отрезок тени от этой грани на ребре.
*/
private Segment shadow(Facet f) {
if (f.vertical(pr))
return new Segment(t1, t0);
int n = f.getVertexesQuantity();
Vertex a = f.getVertex(n-1);
Vertex b = f.getVertex(0);
Segment result = hCross(f, a);
if (result.degenerate()) return result;
result.intersection(vCross(a, b, f.getCenter()));
if (result.degenerate()) return result;
for (int i=1; i<n; i++) {
a = b;
b = f.getVertex(i);
result.intersection(vCross(a, b, f.getCenter()));
if (result.degenerate()) return result;
}
return result;
}
/**
* Вычислить пересечение с "горизонтальным" полупространством.
* @param f Грань полиэдра.
* @param a Точка (вектор) на грани.
* @return Отрезок пересечения ребра с "горизонтальным" полупространством.
*/
private Segment hCross(Facet f, R3Vector a) {
R3Vector n = f.getNormal();
if (R3Vector.scalMul(n, pr) < 0.0) n.mul(-1);
return crossWith(a, n);
}
/**
* Вычислить пересечение с "вертикальным" полупространством.
* @param a Точка (вектор) на грани.
* @param b Точка (вектор) на грани.
* @param c Точка (вектор) на грани.
* @return Отрезок пересечения ребра с "вертикальным" полупространством.
*/
private Segment vCross(R3Vector a, R3Vector b, R3Vector c) {
R3Vector n = R3Vector.vectMul(R3Vector.minus(b,a), pr);
if (R3Vector.scalMul(n, R3Vector.minus(a,c)) < 0.0) n.mul(-1);
return crossWith(a, n);
}
/**
* Вычислить пересечение отрезка с заданным полупространством.
* @param a Точка (вектор) на грани.
* @param n Вектор внешней нормали к полупространству.
* @return Отрезок пересечения ребра с полупространством.
*/
private Segment crossWith(R3Vector a, R3Vector n) {
double f0 = R3Vector.scalMul(n, R3Vector.minus(begin, a));
double f1 = R3Vector.scalMul(n, R3Vector.minus(end, a));
if(Math.abs(f0) < EPSILON) f0 = 0.;
if(Math.abs(f1) < EPSILON) f1 = 0.;
if(f0 >= 0. f1 >= 0.) return new Segment(t1, t0);
if(f0 < 0. f1 < 0. ) return new Segment(t0, t1);
double t = - f0 / (f1 - f0);
if (f0 < 0.) return new Segment(t0, t);
return new Segment(t, t1);
}
/**
* Учесть тень от одной грани.
* @param f Грань, тень от которой должна быть учтена.
*/
protected final void addShadow(Facet f) {
try {
Segment s = shadow(f);
if (!s.degenerate()) {
list.toFront();
while (!list.end()) {
Segment next = list.erase();
Segment left = next.leftSub(s);
if (!left.degenerate()) {
list.insert(left);
list.forward();
}
Segment right = next.rightSub(s);
if (!right.degenerate()) {
list.insert(right);
list.forward();
}
}
}
} catch(Exception e) {
Xterm.println("Слишком много видимых отрезков ребра.");
System.exit(0);
}
}
/**
* Учесть тень от всех граней.
*/
protected void addShadow() {
for(int j=0; j<p.getFacetsQuantity(); j++)
addShadow(p.getFacet(j));
}
/**
* Конструктор класса.
* @param p Полиэдр.
* @param pr Вектор проектирования.
* @param angle Угол поворота в плоскости проекции.
*/
public ShadowDrawer(Polyedr p, R3Vector pr, double angle) {
super(p, pr, angle);
list = new L1ListSegments(MAXSIZE);
}
/**
* Изобразить видимую часть ребра полиэдра.
* @param s Обрабатываемое ребро полиэдра.
*/
public final void drawEdge(Edge s) {
begin = s.getBegin();
end = s.getEnd();
list.clear();
try {
list.insert(new Segment(t0, t1));
} catch(Exception e) {;}
addShadow();
try {
for (list.toFront(); ! list.end(); list.forward()) {
Segment u = list.after();
R3Vector begin = R3(u.getBegin());
R3Vector end = R3(u.getEnd());
draw(xnProection(begin), ynProection(begin),
xnProection(end), ynProection(end));
}
} catch(Exception e) {;}
Xterm.print(".");
}
}
SmartDrawer.java
/**
* @author Е.А. Роганов
* @version 1.1
* Класс SmartDrawer, обеспечивающий изображение проекции полиэдра
* с использованием двумерного хеширования граней.
*/
public class SmartDrawer extends ShadowDrawer {
/**
* Количество гнезд сетки в строке и столбце.
*/
private final static int SIZE = 50;
/**
* Максимальное число граней в гнезде.
*/
private final static int MAXFACETS = 200;
/**
* Массив гнезд, в которые попадает обрабатываемое ребро.
*/
private boolean[][] sockets;
/**
* Массив количеств граней в гнездах.
*/
private int[][] nmbFacets;
/**
* Массив множеств номеров граней.
*/
private int[][][] hashFacets;
/**
* Найти последний индекс гнезда, соответствующий t.
* @param t Координата.
*/
private int lastVal(double t) {
return Math.min((int)(t*SIZE),SIZE-1);
}
/**
* Найти первый индекс гнезда, соответствующий t.
* @param t Координата.
*/
private int firstVal(double t) {
return (int)(t*SIZE);
}
/**
* Конструктор класса.
* @param p Полиэдр.
* @param pr Вектор проектирования.
* @param angle Угол поворота в плоскости проекции.
*/
public SmartDrawer(Polyedr p, R3Vector pr, double angle) {
super(p, pr, angle);
nmbFacets = new int[SIZE][SIZE];
hashFacets = new int[SIZE][SIZE][MAXFACETS];
int i,j,k;
int imax = p.getFacetsQuantity();
for (i=0; i<imax; i++) {
Facet f=p.getFacet(i);
k = f.getVertexesQuantity();
double x0 = 1., y0 = 1., x1 = 0., y1 = 0.;
for (j=0; j<k; j++) {
R3Vector v = f.getVertex(j);
double x = xnProection(v);
double y = ynProection(v);
if (x < x0) x0 = x;
if (y < y0) y0 = y;
if (x > x1) x1 = x;
if (y > y1) y1 = y;
}
int jm = lastVal(x1);
int km = lastVal(y1);
for (j=firstVal(x0); j<=jm; j++)
for (k=firstVal(y0); k<=km; k++)
hashFacets[ j ][ k ][ nmbFacets[j][k]++ ] = i;
}
}
/**
* Учесть тень от всех граней.
*/
protected void addShadow() {
int i,j,k;
double x0 = Math.min(xnProection(begin), xnProection(end));
double x1 = Math.max(xnProection(begin), xnProection(end));
double y0 = Math.min(ynProection(begin), ynProection(end));
double y1 = Math.max(ynProection(begin), ynProection(end));
int jm = lastVal(x1);
int km = lastVal(y1);
for (j=firstVal(x0); j<=jm; j++)
for (k=firstVal(y0); k<=km; k++)
for (i=0; i<nmbFacets[j][k]; i++)
addShadow(p.getFacet( hashFacets[j][k][i] ));
}
}
PolyedrTest.java
import java.util.*;
import java.io.*;
/**
* @author Е.А. Роганов
* @version 1.1
* Класс PolyedrTest, ...
*/
public class PolyedrTest {
/**
* Функция main.
* @param args Массив аргументов командной строки.
* @exception Exception Исключительная ситуация, возникающая
* при ошибках чтения или преобразования данных из файла.
*/
public static void main(String[] args) throws Exception {
Polyedr p = new Polyedr(args[0]);
int type = Xterm.inputInt("Возможные типы изображения полиэдра:\n"+
" без удаления невидимых линий - 0\n"+
" с удалением невидимых ребер - 1\n"+
" с использованием хеширования - 2\n"+
"Выберите тип изображения (от 0 до 2) -> " );
while (true) {
R3Vector pr = new R3Vector();
double angle = Xterm.inputDouble("Угол поворота в плоскости " +
"проекции (в градусах): ");
switch (type) {
case 0:
SimpleDrawer d = new SimpleDrawer(p, pr, Math.PI*angle/180.0);
d.draw();
break;
case 1:
ShadowDrawer sd = new ShadowDrawer(p, pr, Math.PI*angle/180.0);
sd.draw();
break;
case 2:
SmartDrawer smd = new SmartDrawer(p, pr, Math.PI*angle/180.0);
smd.draw();
break;
default:
Xterm.println("Неверный тип изображения");
}
Thread.currentThread().setPriority(Thread.MIN_PRIORITY);
}
}
}
Этот параграф посвящен рассмотрению еще одного проекта, который позволит
познакомиться с простейшими задачами вычислительной геометрии.
Построение изображения
В книгах [9] и [8] содержится большое количество
дополнительной информации, связанной с рассматриваемой задачей и ее
различными обобщениями. Вопросы работы с пакетом
В настоящее время во многих областях науки и техники используются различные
методы моделирования геометрических объектов в трехмерном пространстве.
Один из способов моделирования состоит в том, чтобы аппроксимировать реальный
объект набором выпуклых плоских многоугольников. Такой набор мы будем называть
Примерами
(рис 13.1) Пример полиэдраПри изображении
Задача 13.1.
Напишите программу, которая строит изображение заданного
В результате решения этой задачи
Изображение
Рассматриваемая задача, таким образом, сводится к следующей: построить
проекцию
(рис 13.2) Изображение полиэдраТакую уточненную постановку задачи иллюстрирует рис. 13.2.
Способ задания
Достаточно часто при задании
Способ представления
Этот способ задания
Информация, представляющая
8 6 24
-0.5 -0.5 0.5
-0.5 0.5 0.5
0.5 0.5 0.5
0.5 -0.5 0.5
-0.5 -0.5 -0.5
-0.5 0.5 -0.5
0.5 0.5 -0.5
0.5 -0.5 -0.5
4 1 2 3 4
4 5 6 2 1
4 3 2 6 7
4 3 7 8 4
4 1 4 8 5
4 8 7 6 5
Первая строка говорит о том, что у куба 8 вершин, 6 граней и 24 (!) ребра. Число 24, вдвое превышающее реальное количество ребер у куба, является результатом уже описанного выше эффекта, — каждое из ребер куба принадлежит ровно двум граням.
Следующая часть файла содержит метрическую информацию — координаты всех
восьми вершин
Технические детали работы с файлами и чтения информации из них могут быть изучены заинтересованными читателями самостоятельно с использованием итогового текста проекта, приведенного в конце параграфа, и литературы, содержащей описание библиотек (пакетов) языка Java.
В данной секции будет построена иерархия классов, необходимых для реализации
рассматриваемого проекта. Здесь же мы рассмотрим (в самых общих чертах)
использование библиотеки
Класс R3Vector позволит задать произвольный вектор и обеспечит все
необходимые манипуляции над векторами в трехмерном пространстве. Полный набор
методов, которые должен реализовывать класс R3Vector,
выяснится в процессе дальнейшего решения задачи.
Пока же заметим, что R3Vector, должен вводиться с клавиатуры, и
предусмотрим дополнительный конструктор специально для этих целей.
public class R3Vector {
private double x, y, z;
public R3Vector(double x, double y, double z) {
this.x = x; this.y = y; this.z = z;
}
public R3Vector() throws Exception {
x = Xterm.inputDouble("X-коорд. вектора проектирования -> ");
y = Xterm.inputDouble("Y-коорд. вектора проектирования -> ");
z = Xterm.inputDouble("Z-коорд. вектора проектирования -> ");
}
}
Для представления вершин R3Vector класс super ) вызвать конструктор его
базового класса R3Vector, так как иначе компилятор автоматически вставит
вызов конструктора класса R3Vector без параметров.
public class Vertex extends R3Vector {
public Vertex(double x, double y, double z) {
super(x, y, z);
}
}
Ребра Edge, в каждом
экземпляре которого содержатся две private -компоненты типа 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() {
return begin;
}
public final Vertex getEnd() {
return end;
}
}
Грани
public class Facet {
private Vertex[] vertexes;
public Facet(Vertex[] vertexes) {
this.vertexes = vertexes;
public final int getVertexesQuantity() {
return vertexes.length;
}
public final Vertex getVertex(int i) {
return vertexes[i];
}
Polyedr.
Каждый экземпляр этого класса будет хранить в массивах edges и
При создании нового экземпляра класса 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) {
return vertexes[i];
}
public final int getEdgesQuantity() {
return edges.length;
}
public final Edge getEdge(int i) {
return edges[i];
}
public final int getFacetsQuantity() {
return facets.length;
}
public final Facet getFacet(int i) {
return facets[i];
}
}
Решаемая задача изображения проекции
Задачу вывода плоского изображения в отдельном фрейме поручим осуществлять
классу AwtDrawer. Графическая библиотека (пакет java. )
содержит среди множества других класс 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);
g = getGraphics();
show();
offScrImage = createImage(XLEN+2*DELTA, YLEN+2*DELTA);
offScrGC = offScrImage.getGraphics();
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) {
int x0 = DELTA + (int)(XLEN * xb);
int y0 = DELTA + (int)(YLEN * yb);
int x1 = DELTA + (int)(XLEN * xe);
int y1 = DELTA + (int)(YLEN * ye);
offScrGC.drawLine(x0, y0, x1, y1);
}
public void update(Graphics g) {
paint(g);
}
public void paint(Graphics g) {
g.drawImage(offScrImage, 0, 0, this);
}
}
Поясним назначение некоторых констант, переменных и методов, которые
встречаются в реализации класса AwtDrawer.
Первые три строки тела конструктора этого класса последовательно
устанавливают
заголовок создаваемого фрейма, его размер и цвет фона. Вокруг области рисования
размером XLENxYLEN предусмотрены поля шириной DELTA.
Класс Graphics пакета offScrImage,
а во фрейм выводится с помощью метода drawImage при вызове методов paint и update.
Метод draw, аргументами которого являются числа в диапазоне от 0 до 1,
вычисляет соответствующие им координаты фрейма и с помощью метода drawLine рисует заданный отрезок.
Вернемся теперь к задаче определения множества отрезков на плоскости, которые должны быть изображены.
В качестве первого шага в этом направлении полезно решить относительно
простую
задачу построения проекции всех ребер SimpleDrawer, который вполне логично сделать выведенным из
класса AwtDrawer. В качестве компонент в этот класс включим сам
Ряд методов класса SimpleDrawer предназначен для нахождения координат
проекции произвольного трехмерного вектора, как реальных, так и нормализованных
(в той системе координат на плоскости проекции, в которой изображаемой части
фрейма соответствует квадрат $$0 \leqslant x \leqslant 1 \land 0 \leqslant
y
\leqslant 1$$ ). Вычисление реальных координат проекции, как это хорошо
известно
из аналитической геометрии, сводится к вычислению скалярных произведений с
помощью статического метода 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.p = p;
this.pr = pr.normalize();
double a = pr.getX();
double b = pr.getY();
double c = pr.getZ();
if (a != 0. || b != 0.) {
x = new R3Vector(-b, a, 0.);
} else {
x = new R3Vector(0., c, -b);
}
y = R3Vector.vectMul(x, pr);
x.normalize();
y.normalize();
R3Vector nx = R3Vector.plus(R3Vector.mul(Math.cos(angle), x),
R3Vector.mul(-Math.sin(angle), y));
R3Vector ny = R3Vector.plus(R3Vector.mul(Math.sin(angle), x),
R3Vector.mul(Math.cos(angle), y));
x = nx;
y = ny;
xmin = ymin = Double.MAX_VALUE;
double xmax, ymax;
xmax = ymax = Double.MIN_VALUE;
for (int i=0; i<p.getVertexesQuantity(); i++) {
double xi = xProection(p.getVertex(i));
double yi = yProection(p.getVertex(i));
if (xi < xmin) xmin = xi;
if (yi < ymin) ymin = yi;
if (xi > xmax) xmax = xi;
if (yi > ymax) ymax = yi;
}
size = ymax - ymin;
if (xmax - xmin > size) size = xmax - xmin;
}
public final void draw() {
for (int i=0; i<p.getEdgesQuantity(); i++)
drawEdge(p.getEdge(i));
Xterm.print("\n");
}
public void drawEdge(Edge s) {
Vertex begin = s.getBegin();
Vertex end = s.getEnd();
draw(xnProection(begin), ynProection(begin),
xnProection(end), ynProection(end));
Xterm.print(".");
}
}
Всю основную подготовительную работу выполняет конструктор класса. Первой из
его задач является нахождение ортонормированного базиса, одним из векторов
которого является normalize класса R3Vector. Второй из векторов искомой тройки строится с помощью уже
найденного вектора нормали (нормированному x класса SimpleDrawer ).
Третий вектор базиса (компонента y ) находится с помощью вычисления
vectMul ) двух уже найденных. Заключительным шагом является
осуществление поворота на заданный угол angle в плоскости проекции.
Как известно из аналитической геометрии, поворот в плоскости $$Oxy$$
на угол $$\alpha$$ эквивалентен умножению вектора координат $$(x,y)$$ на матрицу$$\left(
\begin{array}{cc}
\cos\alpha -\sin\alpha\\
\sin\alpha \cos\alpha\\
\end{array}
\right).$$
Для осуществления этих операций используются методы mul и plus
класса R3Vector, позволяющие умножить вектор на число и вычислить сумму
двух векторов соответственно.
Вторая задача конструктора класса SimpleDrawer — определение
квадрата
наименьшего размера, в котором целиком поместится проекция всех ребер
Метод draw, который и должен построить проекцию drawEdge, последовательно вызываемого
для всех ребер. Последний из методов вычисляет нормализованные координаты
проекции обрабатываемого ребра и вызывает метод draw базового класса AwtDrawer для рисования требуемого отрезка. Так как для сложных
Наиболее содержательная часть исходной задачи — учет затенения частей
ребер
гранями ShadowDrawer,
обсуждению которого посвящена следующая секция параграфа. В ней выяснится,
что для работы с тенями (точнее с просветами — дополнениями теней)
целесообразно создать еще два класса — Segment и L1ListSegments.
Чуть позже будет
рассмотрен и один из возможных методов оптимизации, позволяющий ускорить
построение изображения сложных SmartDrawer.
(рис 13.3) Иерархия классов проектаМетод main, выполняющий ввод имени файла с описанием изображаемого
PolyedrTest, которым завершается построение иерархии классов,
используемых для решения исходной задачи. Все классы иерархии показаны на
рисунке рис. 13.3.
Так как плоское изображение
(рис 13.4) Тень от грани на ребреЕсли предположить, что бесконечно высоко расположен источник света, то
на каждом ребре образуются освещенные и затененные участки. Первые мы будем
называть
Для получения изображения видимой части ребра нужно учесть тени от всех
граней
Важным наблюдением, существенно упрощающим искомый алгоритм, является тот
факт,
что задача нахождения теней и просветов на конкретном ребре — одномерная. Сопоставив началу ребра координату 0, а концу — 1, мы
можем установить взаимно однозначное соответствие между трехмерными
координатами точек ребра и введенными одномерными координатами.
После этого каждый из просветов будет представлять собой отрезок, а
реализовывать его будет класс Segment, в каждом экземпляре которого
должны храниться
одномерные координаты начала и конца обрабатываемого отрезка. Методы данного
класса обязаны обеспечить все необходимые действия с отрезками, которые
понадобятся при определении множества просветов.
public class Segment {
private double begin, end;
public Segment(double begin, double end) {
this.begin = begin; this.end = end;
}
public final boolean degenerate() {
return begin >= end;
}
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);
return this;
}
public final double getBegin() {
return begin;
}
public final double getEnd() {
return end;
}
}
Указанные действия включают в себя проверку degenerate ), а также вычисление пересечения двух отрезков и определения
обеих компонент разности двух отрезков. Отрезок $$[a,b]$$ является
вырожденным,
если он представляет из себя точку или пустое множество, то есть если $$a \geqslant b$$. Пересечение двух отрезков всегда является отрезком
(возможно,
вырожденным), который вычисляется в методе intersection, а разность двух
отрезков всегда состоит из двух отрезков, каждый из которых может
оказаться вырожденным. Левая и правая компоненты разности вычисляются с
помощью методов leftSub и rightSub соответственно.
(рис 13.5) Разность просвета и тениСовокупность всех просветов ребра целесообразно хранить в односвязном списке
сегментов, для чего будем использовать изученную нами ранее ссылочную
реализацию (класс L1ListSegments ). В самом начале обработки очередного
ребра множество просветов состоит из одного элемента, совпадающего со
всем ребром, — отрезка $$[0,1]$$. Последовательный учет теней от
граней
можно считать функцией на пространстве последовательности граней. Легко
заметить, что эта функция индуктивна — зная список просветов, который
учитывает тени от нескольких граней, и тень от еще одной, новой грани,
легко вычислить новый список просветов, учитывающий и тень от новой грани.
Для этого достаточно для всех просветов вычислить их разности с отрезком
тени от грани (см. рис. 13.5).
В зависимости от расположения отрезков, соответствующих просвету и тени, их разность может оказаться пустой (если просвет целиком попал в тень), состоящей из единственной точки, двух точек, одного отрезка, точки и отрезка, и двух отрезков. Как это уже обсуждалось ранее, мы не будем различать эти ситуации. Гораздо удобнее считать, что разность всегда состоит из двух отрезков, каждый из которых может быть вырожденным.
Приведем ту часть реализации класса 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),
R3Vector.mul(t, end) );
}
protected final void addShadow(Facet f) {
try {
Segment s = shadow(f);
if (!s.degenerate()) {
list.toFront();
while (!list.end()) {
Segment next = list.erase();
Segment left = next.leftSub(s);
if (!left.degenerate()) {
list.insert(left);
list.forward();
}
Segment right = next.rightSub(s);
if (!right.degenerate()) {
list.insert(right);
list.forward();
}
}
}
} catch(Exception e) {
Xterm.println("Слишком много видимых отрезков ребра.");
System.exit(0);
}
}
protected void addShadow() {
for(int j=0; j<p.getFacetsQuantity(); j++)
addShadow(p.getFacet(j));
}
public ShadowDrawer(Polyedr p, R3Vector pr, double angle) {
super(p, pr, angle);
list = new L1ListSegments(MAXSIZE);
}
public final void drawEdge(Edge s) {
begin = s.getBegin();
end = s.getEnd();
list.clear();
try {
list.insert(new Segment(t0, t1));
} catch(Exception e) {;}
addShadow();
try {
for (list.toFront(); ! list.end(); list.forward()) {
Segment u = list.after();
R3Vector begin = R3(u.getBegin());
R3Vector end = R3(u.getEnd());
draw(xnProection(begin), ynProection(begin),
xnProection(end), ynProection(end));
}
} catch(Exception e) {;}
Xterm.print(".");
}
}
Метод drawEdge фиксирует обрабатываемое ребро, записывая его начало и
конец в компоненты begin и end, и инициализирует список просветов list, помещая в него единственный элемент — ребро целиком.
Затем с помощью вызова метода addShadow производится учет теней от всех
граней R3 по известной из аналитической геометрии формуле.
Учет тени от конкретной грани производится путем определения одномерной тени
на обрабатываемом ребре с помощью вызова метода shadow и
индуктивного перевычисления списка просветов по алгоритму, описанному выше.
Отметим дополнительно, что вырожденные отрезки в список просветов никогда не
включаются.
Заключительным этапом решения задачи является реализация метода shadow.
Этот метод должен определить отрезок на обрабатываемом ребре, который
представляет собой тень от фиксированной грани
Прежде всего следует разобраться с тем, что же такое тень от грани.
Сначала заметим, что вертикальные грани
дают пустую тень. Для остальных граней множество затеняемых ими точек
пространства образует
Тень от грани на ребро при этом оказывается просто пересечением ребра с этой призмой. Заметим, что призму следует считать открытой, т.е. считать, что граница призмы тени не принадлежит, так как в противном случае каждая грань будет затенять сама себя и изображение окажется пустым.
(рис 13.6) Нахождение тени от граниЕстественно попытаться свести нахождение пересечения ребра с призмой к каким-нибудь более элементарным операциям. Мы сделаем это, представив призму в виде пересечения открытых полупространств. Например, треугольную призму можно представить в виде пересечения четырех полупространств (см. рис. 13.6).
Первое полупространство ограничено плоскостью, проходящей через грань
Искомое пересечение ребра и призмы, представляющей собой тень, сводится
теперь к последовательному нахождению пересечения ребра с полупространствами
(сначала горизонтальным, а затем — всеми вертикальными). Приведем реализацию
всех необходимых для этого методов класса ShadowDrawer.
private static final double EPSILON = 1.e-12;
private Segment shadow(Facet f) {
if (f.vertical(pr))
return new Segment(t1, t0);
int n = f.getVertexesQuantity();
Vertex a = f.getVertex(n-1);
Vertex b = f.getVertex(0);
Segment result = hCross(f, a);
if (result.degenerate()) return result;
result.intersection(vCross(a, b, f.getCenter()));
if (result.degenerate()) return result;
for (int i=1; i<n; i++) {
a = b;
b = f.getVertex(i);
result.intersection(vCross(a, b, f.getCenter()));
if (result.degenerate()) return result;
}
return result;
}
private Segment hCross(Facet f, R3Vector a) {
R3Vector n = f.getNormal();
if (R3Vector.scalMul(n, pr) < 0.0) n.mul(-1);
return crossWith(a, n);
}
private Segment vCross(R3Vector a, R3Vector b, R3Vector c) {
R3Vector n = R3Vector.vectMul(R3Vector.minus(b,a), pr);
if (R3Vector.scalMul(n, R3Vector.minus(a,c)) < 0.0) n.mul(-1);
return crossWith(a, n);
}
private Segment crossWith(R3Vector a, R3Vector n) {
double f0 = R3Vector.scalMul(n, R3Vector.minus(begin, a));
double f1 = R3Vector.scalMul(n, R3Vector.minus(end, a));
if(Math.abs(f0) < EPSILON) f0 = 0.;
if(Math.abs(f1) < EPSILON) f1 = 0.;
if(f0 >= 0. f1 >= 0.) return new Segment(t1, t0);
if(f0 < 0. f1 < 0. ) return new Segment(t0, t1);
double t = - f0 / (f1 - f0);
if (f0 < 0.) return new Segment(t0, t);
return new Segment(t, t1);
}
Договоримся задавать полупространство, пересечения ребра с которым
необходимо уметь вычислять, точкой $$A$$ на ограничивающей его
плоскости и
вектором crossWith с указанными аргументами
(в тексте программы это точка a и вектор нормали n ),
обсудим задачу нахождения
одномерной тени, решаемую методами shadow, hCross и vCross.
Для реализации метода hCross нахождения пересечения с горизонтальным
полупространством нужно найти нормаль к грани (выбрав правильное
направление)
и вызвать метод crossWith. Ясно, что из соображений эффективности
операцию вычисления нормали к грани лучше выполнить только один раз, что и
делается в конструкторе класса
Вычисление пересечения с вертикальным полупространством с помощью метода vCross удастся реализовать, зная соответствующее ребро грани (точки $$A$$ и $$B$$ ) и центр грани $$C$$. Точку $$A$$ при этом можно использовать в
качестве аргумента для вызова метода crossWith непосредственно, а
нормаль к вертикальной плоскости, проходящей через ребро $$AB$$,
находится
следующим образом. Сначала вычисляется
Так как все грани
Вернемся теперь к методу shadow. Если грань, одномерную тень от
которой
мы ищем, вертикальна, то ее тень пуста. В этом случае возвращаемый отрезок
тени должен быть вырожден, что и реализуется в первых двух строках тела
метода.
Для невертикальной грани сначала вычисляется отрезок result,
являющийся
результатом пересечения ребра с result с вертикальными полупространствами,
соответствующими ребрам. При этом вычисления немедленно прекращаются, если
будет получен
Теперь нам осталось разобраться с последним из методов класса ShadowDrawer — методом crossWith нахождения пересечения ребра $$PQ$$ с полупространством, заданным точкой $$A$$ и вектором
внешней
нормали $$\vec n$$.
В одномерных координатах точкам $$P$$ и $$Q$$ соответствует
ноль и единица, а
результатом работы метода должны быть одномерные координаты отрезка
пересечения.
Рассмотрим функцию $$f(x) = <\vec n, \overrightarrow{AX}>$$, где $$X$$ — точка на ребре $$PQ$$, $$x$$ — ее одномерная координата, а угловые скобки означают скалярное произведение двух векторов. Эта функция линейна и является знакопостоянной на отрезке $$[0,1]$$ в том случае, если ребро $$PQ$$ целиком лежит вне или внутри полупространства. В случае пересечения ребра с плоскостью, ограничивающей полупространство, одномерная координата точки пересечения находится из уравнения $$f(x) = 0$$.
Из вышесказанного следует, что задача нахождения пересечения ребра с
полупространством может быть решена таким образом. Вычислим сначала значения
функции $$f(x)$$ в концах отрезка — $$f(0)$$ и $$f(1)$$ (в программной реализации
им соответствуют величины f0 и f1 ). Если обе эти величины
неотрицательны, то пересечение пусто, если, наоборот, они обе отрицательны,
то весь отрезок лежит в полупространстве.
Для определения одномерной координаты точки пересечения решим уравнение $$f(x) = 0$$. В силу линейности функции $$f(x)$$ она имеет вид $$f(x) = \alpha + \beta x$$. Так как $$f(0) = \alpha$$, а $$f(1) = \alpha + \beta$$, то коэффициенты $$\alpha$$ и $$\beta$$ легко определяются. После этого легко вычислить и корень указанного уравнения: $$\alpha = f(0)$$, $$\beta = f(1) - f(0)$$, $$x = -f(0)/(f(1) - f(0))$$.
Теперь остается выбрать только нужную часть отрезка, что и реализовано в
двух последних строках тела метода crossWith. В заключение обсудим
назначение третьей и четвертой строк, в которых используется малая по
абсолютной величине константа EPSILON. Их роль — попытка исправить
те ошибки в работе метода, которые обусловлены приближенными вычислениями
с числами типа double. В результате ошибок округления некоторые видимые
части ребер не изображаются и наоборот.
Добавление указанных операторов несколько улучшает ситуацию, не исправляя ее полностью. Одна из задач, предназначенных для самостоятельного решения, предлагает справиться с этой проблемой.
Рассматриваемый нами проект является достаточно объемным, а его исходные тексты размещены во многих файлах, что делает особенно полезным использование ряда технологических приемов при работе с ним.
Применение утилиты make значительно облегчает решение задач на
модификацию. Используемый в проекте Makefile позволяет корректно
откомпилировать текст программы и стартовать процесс построения изображения
любого из более, чем 15 data. Для построения изображения куба, например, достаточно
выполнения команды make .
Большая часть возможностей утилиты make, используемых в данном
проекте,
уже была рассмотрена ранее. Обсудим лишь те действия, которые выполняются при
построении цели doc. Вот соответствующий фрагмент из управляющего
файла.
doc:
javadoc -d doc -version -author -private *.java
Задание на построение цели doc сводится, как видно из этой записи, к
вызову утилиты
При самом первом знакомстве с языком Java было отмечено, что в нем
предусмотрены /** и завершающийся символами */ предназначен для размещения
в тексте программы комментариев, которые могут быть впоследствии обработаны
утилитой
Правильное использование этой утилиты позволяет получить описание классов и
пакетов в гипертекстовом формате (на языке HTML), что чрезвычайно удобно.
Программист обязан, конечно, при написании программы размещать в ее тексте
необходимые директивы, распознаваемые утилитой
(рис 13.7) Фрагмент результата работы утилитыПриведенный в последней секции параграфа полный текст проекта иллюстрирует
использование таких комментариев. Иерархия классов проекта "Изображение
Как легко убедиться, построенная программа работает достаточно медленно при
построении изображения сложного
Основное время в процессе нахождения плоского изображения
Хорошей идеей является попытка использования
Реализация описанной идеи позволяет заменить для большинства граней
ресурсоемкую операцию нахождения тени от нее на определение пересечения
ее
Поскольку для каждого конкретного ребра большая часть
граней является далекими, то скорость построения изображения
Другим возможным способом оптимизации построения изображения является
использование
Для реализации этой идеи вся прямоугольная область изображения разбивается
на
небольшие квадратные гнезда и при инициализации hashFacets, который
рассматривается как одномерный список граней, имеющих отношение к
конкретному гнезду, записываются все их номера. При построении же
изображения каждого из ребер необходимо будет искать тень только от тех граней,
которые находятся в гнездах, соответствующих ребру.
Класс SmartDrawer, полный текст которого приведен ниже, реализует эту
идею.
Задача 13.2.
Оптимизируйте текст эталонного проекта "Изображение
a) устранить многократное изображение видимых частей ребер, связанное с
особенностями задания
b) реализовать идею ShadowDrawer ;
c) минимизировать действия, выполняемые в классе ShadowDrawer,
связанные с необходимостью обращения (умножения на минус единицу) нормалей
к граням;
d) максимально исправить влияние ошибок округления при работе с числами, заданными в форме с плавающей точкой, которые приводят к тому, что отдельные видимые части ребер не изображаются и наоборот.
Задача 13.3.
Модифицируйте текст эталонного проекта "Изображение
a) невидимые части ребер изображались пунктиром;
b) грани, имеющие максимальную площадь среди полностью видимых граней, заштриховывалась;
c) изображалась только та часть
d) изображалось сечение
e) строились плоские изображения четырехмерных
Задача 13.4.
Модифицируйте текст эталонного проекта "Изображение
a) количество видимых вершин;
b) количество полностью видимых ребер;
c) количество частично видимых ребер;
d) количество полностью видимых граней;
e) количество частично видимых граней;
f) количество ребер, удаленных от начала координат не более, чем на единичное растояние;
g) количество граней, удаленных от начала координат не более, чем на единичное растояние;
h) количество граней
i) количество ребер
j) периметр проекции
k) площадь проекции
Сначала приведем содержание управляющего файла для утилиты 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
JAVAC = javac
JAVAFILES := Xterm.java R3Vector.java Vertex.java Edge.java Facet.java \
Polyedr.java Segment.java L1ListSegments.java \
AwtDrawer.java SimpleDrawer.java ShadowDrawer.java \
SmartDrawer.java PolyedrTest.java
CLASSFILES := Xterm.class R3Vector.class Vertex.class Edge.class Facet.class \
Polyedr.class Segment.class L1ListSegments.class \
AwtDrawer.class SimpleDrawer.class ShadowDrawer.class \
SmartDrawer.class PolyedrTest.class
%.class: %.java
$(JAVAC) $<
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
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
vw: $(CLASSFILES)
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:
rm -f *.class *.expand
veryclean:
rm -f *.class *.expand doc/*.html
А вот как выглядят все остальные файлы проекта.
R3Vector.java
/**
* @author Е.А. Роганов
* @version 1.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) {
this.x = x; this.y = y; this.z = 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() {
return x;
}
/**
* Получить Y-координату вектора.
* @return Y-координата вектора.
*/
public final double getY() {
return y;
}
/**
* Получить Z-координату вектора.
* @return Z-координата вектора.
*/
public final double getZ() {
return z;
}
/**
* Нормировать ненулевой вектор.
*/
public final R3Vector normalize() {
double norm = Math.sqrt(x*x+y*y+z*z);
x /= norm; y /= norm; z /= norm;
return this;
}
/**
* Найти сумму двух векторов.
* @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);
}
/**
* Добавить заданный вектор.
* @param b Добавляемый вектор.
* @return Вектор-результат.
*/
public final R3Vector plus(R3Vector b) {
x += b.x; y += b.y; z += b.z;
return this;
}
/**
* Найти разность двух векторов.
* @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) {
x -= b.x; y -= b.y; z -= b.z;
return this;
}
/**
* Найти произведение вектора на число.
* @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) {
x *= k; y *= k; z *= k;
return this;
}
/**
* Найти скалярное произведение векторов.
* @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.1
* Класс Vertex, реализующий вершину полиэдра.
*/
public class Vertex extends R3Vector {
/**
* Конструктор.
* @param x X-координата вершины.
* @param y Y-координата вершины.
* @param z Z-координата вершины.
*/
public Vertex(double x, double y, double z) {
super(x, y, z);
}
}
Edge.java
/**
* @author Е.А. Роганов
* @version 1.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() {
return begin;
}
/**
* Получить конец ребра.
* @return Конец ребра.
*/
public final Vertex getEnd() {
return end;
}
}
Facet.java
/**
* @author Е.А. Роганов
* @version 1.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]),
R3Vector.minus(vertexes[2], vertexes[0]));
center = new R3Vector(0., 0., 0.);
for (int i=0; i<vertexes.length; i++) {
center.plus(vertexes[i]);
}
center.mul(1./(double)vertexes.length);
}
/**
* Получить количество вершин.
* @return Количество вершин грани.
*/
public final int getVertexesQuantity() {
return vertexes.length;
}
/**
* Получить вершину.
* @param i Номер вершины.
* @return Вершина грани.
*/
public final Vertex getVertex(int i) {
return vertexes[i];
}
/**
* Получить центр грани.
* @return Центр грани.
*/
public final R3Vector getCenter() {
return center;
}
/**
* Получить нормаль к грани.
* @return Нормаль грани.
*/
public final R3Vector getNormal() {
return normal;
}
/**
* Является ли грань "вертикальной"?
* @param pr Вектор проектирования.
* @return Параллельна ли грань вектору проектирования?
*/
public final boolean vertical(R3Vector pr) {
return R3Vector.scalMul(normal, pr) == 0.;
}
}
Polyedr.java
import java.util.*;
import java.io.*;
/**
* @author Е.А. Роганов
* @version 1.1
* Класс Polyedr, реализующий полиэдр.
*/
public class Polyedr {
/**
* Массив вершин полиэдра.
*/
private Vertex[] vertexes;
/**
* Массив ребер полиэдра.
*/
private Edge[] edges;
/**
* Массив граней полиэдра.
*/
private Facet[] facets;
/**
* Конструктор класса.
* @param file Файл, содержащий описание полиэдра.
* @exception Exception Исключительная ситуация, возникающая при
* ошибках чтения или преобразования данных.
*/
public Polyedr(String file) throws Exception {
RandomAccessFile f = new RandomAccessFile(file, "r");
StringTokenizer st = new StringTokenizer(f.readLine());
vertexes = new Vertex[Integer.parseInt(st.nextToken())];
facets = new Facet[Integer.parseInt(st.nextToken())];
edges = new Edge[Integer.parseInt(st.nextToken())];
for (int i=0; i<vertexes.length; i++) {
st = new StringTokenizer(f.readLine());
double x = Double.valueOf(st.nextToken()).doubleValue();
double y = Double.valueOf(st.nextToken()).doubleValue();
double z = Double.valueOf(st.nextToken()).doubleValue();
vertexes[i] = new Vertex(x,y,z);
}
int k = 0;
for (int i=0; i<facets.length; i++) {
st = new StringTokenizer(f.readLine());
int size = Integer.parseInt(st.nextToken());
Vertex[] facet = new Vertex[size];
facet[0] = vertexes[Integer.parseInt(st.nextToken()) - 1];
for (int j=1; j<size; j+=1) {
facet[j] = vertexes[Integer.parseInt(st.nextToken()) - 1];
edges[k++] = new Edge(facet[j], facet[j-1]);
}
edges[k++] = new Edge(facet[size-1], facet[0]);
facets[i] = new Facet(facet);
}
}
/**
* Получить количество вершин.
* @return Количество вершин полиэдра.
*/
public final int getVertexesQuantity() {
return vertexes.length;
}
/**
* Получить вершину.
* @param i Номер вершины.
* @return Вершина полиэдра.
*/
public final Vertex getVertex(int i) {
return vertexes[i];
}
/**
* Получить количество ребер.
* @return Количество ребер полиэдра.
*/
public final int getEdgesQuantity() {
return edges.length;
}
/**
* Получить ребро.
* @param i Номер ребра.
* @return Ребро полиэдра.
*/
public final Edge getEdge(int i) {
return edges[i];
}
/**
* Получить количество граней.
* @return Количество граней полиэдра.
*/
public final int getFacetsQuantity() {
return facets.length;
}
/**
* Получить грань.
* @param i Номер грани.
* @return Грань полиэдра.
*/
public final Facet getFacet(int i) {
return facets[i];
}
}
Segment.java
/**
* @author Е.А. Роганов
* @version 1.q
* Класс Segment, реализующий одномерный отрезок.
*/
public class Segment {
/**
* Координаты начала и конца отрезка.
*/
private double begin, end;
/**
* Конструктор отрезка.
* @param begin Начало отрезка.
* @param end Начало отрезка.
*/
public Segment(double begin, double end) {
this.begin = begin; this.end = end;
}
/**
* Вырожден ли отрезок?
* @return Вырожден ли отрезок?
*/
public final boolean degenerate() {
return begin >= end;
}
/**
* Найти левый отрезок разности с отрезком s.
* @param s Вычитаемый отрезок.
* @return Левый отрезок разности.
*/
public final Segment leftSub(Segment s) {
return new Segment(begin, Math.min(end, s.begin));
}
/**
* Найти правый отрезок разности с отрезком s.
* @param s Вычитаемый отрезок.
* @return Правый отрезок разности.
*/
public final Segment rightSub(Segment s) {
return new Segment(Math.max(begin, s.end), end);
}
/**
* Найти пересечение с отрезком s.
* @param s Отрезок, с которым находится пересечение.
* @return Отрезок-пересечение.
*/
public final Segment intersection(Segment s) {
begin = Math.max(begin, s.begin);
end = Math.min(end, s.end);
return this;
}
/**
* Получить начало отрезка.
* @return Начало отрезка.
*/
public final double getBegin() {
return begin;
}
/**
* Получить конец отрезка.
* @return Конец отрезка.
*/
public final double getEnd() {
return end;
}
}
L1ListSegments.java
/**
* @author Е.А. Роганов
* @version 1.1
* Класс L1ListSegments, реализующий односвязный список отрезков.
*/
public class L1ListSegments {
/**
* Массив отрезков.
*/
private Segment[] array;
/**
* Массив ссылок.
*/
private int[] next;
/**
* Нил списка.
*/
private int nilList;
/**
* Нил свободного места.
*/
private int nilFree;
/**
* Элемент до указателя.
*/
private int before;
/**
* Элемент за указателем.
*/
private int after;
/**
* Связать два элемента.
* @param first Первый элемент.
* @param second Второй элемент.
*/
private void link(int first, int second) {
next[first] = second;
}
/**
* Захватить место.
* @return Индекс занимаемого элемента.
*/
private int mallocIndex() {
int index = next[nilFree];
link(nilFree, next[index]);
return index;
}
/**
* Освободить место.
* @param index Индекс освобождаемого элемента.
*/
private void freeIndex(int index) {
link(index, next[nilFree]);
link(nilFree, index);
}
/**
* Конструктор класса.
* @param size Максимальный размер списка.
*/
public L1ListSegments(int size) {
array = new Segment[size];
next = new int[size + 2];
nilList = size;
nilFree = size + 1;
link(nilList, nilList);
link(nilFree, 0);
for (int i=0; i<size-1; i++)
link(i, i+1);
link(size-1, nilFree);
before = after = nilList;
}
/**
* Пуст ли список?
* @return Пуст ли список?
*/
public final boolean empty() {
return next[nilList] == nilList;
}
/**
* Сделать список пустым.
*/
public final void clear() {
try {
toFront();
while(true)
erase();
} catch(Exception e) {
;
}
}
/**
* Передвинуть указатель в начало списка.
*/
public final void toFront() {
before = nilList;
after = next[nilList];
}
/**
* Указатель в конце списка?
* @return Указатель в конце списка?
*/
public final boolean end() {
return after == nilList;
}
/**
* Передвинуть указатель вперед.
* @exception Exception Исключительная ситуация, возникающая при
* попытке передвинуть вперед указатель, находящийся в конце списка.
*/
public final void forward() throws Exception {
if (after == nilList) throw new Exception();
before = after;
after = next[after];
}
/**
* Получить элемент за указателем.
* @return Элемент за указателем.
* @exception Exception Исключительная ситуация, возникающая при
* попытке получить элемент за указателем, находящимся в конце списка.
*/
public final Segment after() throws Exception {
return array[after];
}
/**
* Добавить элемент за указателем.
* @param val Включаемый отрезок (сегмент).
* @exception Exception Исключительная ситуация, возникающая при
* попытке добавить элемент в заполненный до конца список.
*/
public final void insert(Segment val) throws Exception {
int index = mallocIndex();
link(before, index);
link(index, after);
after = index;
array[index] = val;
}
/**
* Удалить элемент за указателем.
* @return Удаляемый элемент.
* @exception Exception Исключительная ситуация, возникающая при
* попытке удалить элемент из пустого списка.
*/
public final Segment erase() throws Exception {
Segment val = array[after];
int index = after;
after = next[index];
link(before, after);
freeIndex(index);
return val;
}
}
AwtDrawer.java
import java.awt.*;
/**
* @author Е.А. Роганов
* @version 1.1
* Класс AwtDrawer, обеспечивающий визуализацию
* плоского изображения.
*/
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);
g = getGraphics();
show();
offScrImage = createImage(XLEN+2*DELTA, YLEN+2*DELTA);
offScrGC = offScrImage.getGraphics();
offScrGC.setColor(Color.white);
offScrGC.fillRect(0,0,XLEN+2*DELTA, YLEN+2*DELTA);
offScrGC.setColor(Color.black);
}
/**
* Изобразить отрезок на плоскости, заданный его концами.
* @param xb X-координата начала отрезка ( 0 <= xb <= 1 ).
* @param yb Y-координата начала отрезка ( 0 <= yb <= 1 ).
* @param xe X-координата конца отрезка ( 0 <= xe <= 1 ).
* @param ye Y-координата конца отрезка ( 0 <= ye <= 1 ).
*/
public final void draw(double xb, double yb, double xe, double ye) {
int x0 = DELTA + (int)(XLEN * xb);
int y0 = DELTA + (int)(YLEN * yb);
int x1 = DELTA + (int)(XLEN * xe);
int y1 = DELTA + (int)(YLEN * ye);
offScrGC.drawLine(x0, y0, x1, y1);
}
/**
* Переизобразить содержимое фрейма.
*/
public void update(Graphics g) {
paint(g);
}
public void paint(Graphics g) {
g.drawImage(offScrImage, 0, 0, this);
}
}
SimpleDrawer.java
/**
* @author Е.А. Роганов
* @version 1.1
* Класс SimpleDrawer, обеспечивающий изображение проекции полиэдра.
*/
public class SimpleDrawer extends AwtDrawer {
/**
* Полиэдр.
*/
protected Polyedr p;
/**
* Единичный вектор проектирования.
*/
protected R3Vector pr;
/**
* Единичный X-вектор плоскости проектирования.
*/
private R3Vector x;
/**
* Единичный Y-вектор плоскости проектирования.
*/
private R3Vector y;
/**
* Минимальная X-координата проекции полиэдра.
*/
private double xmin;
/**
* Минимальная Y-координата проекции полиэдра.
*/
private double ymin;
/**
* Размер проекции полиэдра.
*/
private double size;
/**
* Вычислить X-координату проекции точки.
* @param v Трехмерный вектор.
* @return X-координата проекции этого вектора.
*/
private double xProection(R3Vector v) {
return R3Vector.scalMul(v, x);
}
/**
* Вычислить Y-координату проекции точки.
* @param v Трехмерный вектор.
* @return Y-координата проекции этого вектора.
*/
private double yProection(R3Vector v) {
return R3Vector.scalMul(v, y);
}
/**
* Вычислить нормализованную X-координату проекции точки.
* @param v Трехмерный вектор.
* @return Нормализованная X-координата проекции этого вектора.
*/
protected double xnProection(R3Vector v) {
return (xProection(v) - xmin)/size;
}
/**
* Вычислить нормализованную Y-координату проекции точки.
* @param v Трехмерный вектор.
* @return Нормализованная Y-координата проекции этого вектора.
*/
protected double ynProection(R3Vector v) {
return (yProection(v) - ymin)/size;
}
/**
* Конструктор класса.
* @param p Полиэдр.
* @param pr Вектор проектирования.
* @param angle Угол поворота в плоскости проекции.
*/
public SimpleDrawer(Polyedr p, R3Vector pr, double angle) {
this.p = p;
this.pr = pr.normalize();
double a = pr.getX();
double b = pr.getY();
double c = pr.getZ();
if (a != 0. || b != 0.) {
x = new R3Vector(-b, a, 0.);
} else {
x = new R3Vector(0., c, -b);
}
y = R3Vector.vectMul(x, pr);
x.normalize();
y.normalize();
R3Vector nx = R3Vector.plus( R3Vector.mul(Math.cos(angle), x),
R3Vector.mul(-Math.sin(angle), y) );
R3Vector ny = R3Vector.plus( R3Vector.mul(Math.sin(angle), x),
R3Vector.mul(Math.cos(angle), y) );
x = nx;
y = ny;
xmin = ymin = Double.MAX_VALUE;
double xmax, ymax;
xmax = ymax = Double.MIN_VALUE;
for (int i=0; i<p.getVertexesQuantity(); i++) {
double xi = xProection(p.getVertex(i));
double yi = yProection(p.getVertex(i));
if (xi < xmin) xmin = xi;
if (yi < ymin) ymin = yi;
if (xi > xmax) xmax = xi;
if (yi > ymax) ymax = yi;
}
size = ymax - ymin;
if (xmax - xmin < size) size = xmax - xmin;
}
/**
* Изобразить проекцию полиэдра.
*/
public final void draw() {
for (int i=0; i<p.getEdgesQuantity(); i++)
drawEdge(p.getEdge(i));
Xterm.print("\n");
}
/**
* Изобразить ребро полиэдра.
* @param s Обрабатываемое ребро полиэдра.
*/
public void drawEdge(Edge s) {
Vertex begin = s.getBegin();
Vertex end = s.getEnd();
draw(xnProection(begin), ynProection(begin),
xnProection(end), ynProection(end));
Xterm.print(".");
}
}
ShadowDrawer.java
/**
* @author Е.А. Роганов
* @version 1.1
* Класс 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 EPSILON = 1.e-12;
/**
* Одномерная координата начала обрабатываемого ребра.
*/
private static final double t0 = 0.;
/**
* Одномерная координата конца обрабатываемого ребра.
*/
private static final double t1 = 1.;
/**
* Вычислить пространственные координаты точки ребра,
* заданной одномерной координатой.
* @param t Одномерная координата точки на ребре.
* @return Трехмерная координата этой точки ребра.
*/
private R3Vector R3(double t) {
return R3Vector.plus( R3Vector.mul((1.-t), begin),
R3Vector.mul(t, end) );
}
/**
* Вычислить одномерный отрезок тени от грани.
* @param f Грань полиэдра.
* @return Отрезок тени от этой грани на ребре.
*/
private Segment shadow(Facet f) {
if (f.vertical(pr))
return new Segment(t1, t0);
int n = f.getVertexesQuantity();
Vertex a = f.getVertex(n-1);
Vertex b = f.getVertex(0);
Segment result = hCross(f, a);
if (result.degenerate()) return result;
result.intersection(vCross(a, b, f.getCenter()));
if (result.degenerate()) return result;
for (int i=1; i<n; i++) {
a = b;
b = f.getVertex(i);
result.intersection(vCross(a, b, f.getCenter()));
if (result.degenerate()) return result;
}
return result;
}
/**
* Вычислить пересечение с "горизонтальным" полупространством.
* @param f Грань полиэдра.
* @param a Точка (вектор) на грани.
* @return Отрезок пересечения ребра с "горизонтальным" полупространством.
*/
private Segment hCross(Facet f, R3Vector a) {
R3Vector n = f.getNormal();
if (R3Vector.scalMul(n, pr) < 0.0) n.mul(-1);
return crossWith(a, n);
}
/**
* Вычислить пересечение с "вертикальным" полупространством.
* @param a Точка (вектор) на грани.
* @param b Точка (вектор) на грани.
* @param c Точка (вектор) на грани.
* @return Отрезок пересечения ребра с "вертикальным" полупространством.
*/
private Segment vCross(R3Vector a, R3Vector b, R3Vector c) {
R3Vector n = R3Vector.vectMul(R3Vector.minus(b,a), pr);
if (R3Vector.scalMul(n, R3Vector.minus(a,c)) < 0.0) n.mul(-1);
return crossWith(a, n);
}
/**
* Вычислить пересечение отрезка с заданным полупространством.
* @param a Точка (вектор) на грани.
* @param n Вектор внешней нормали к полупространству.
* @return Отрезок пересечения ребра с полупространством.
*/
private Segment crossWith(R3Vector a, R3Vector n) {
double f0 = R3Vector.scalMul(n, R3Vector.minus(begin, a));
double f1 = R3Vector.scalMul(n, R3Vector.minus(end, a));
if(Math.abs(f0) < EPSILON) f0 = 0.;
if(Math.abs(f1) < EPSILON) f1 = 0.;
if(f0 >= 0. f1 >= 0.) return new Segment(t1, t0);
if(f0 < 0. f1 < 0. ) return new Segment(t0, t1);
double t = - f0 / (f1 - f0);
if (f0 < 0.) return new Segment(t0, t);
return new Segment(t, t1);
}
/**
* Учесть тень от одной грани.
* @param f Грань, тень от которой должна быть учтена.
*/
protected final void addShadow(Facet f) {
try {
Segment s = shadow(f);
if (!s.degenerate()) {
list.toFront();
while (!list.end()) {
Segment next = list.erase();
Segment left = next.leftSub(s);
if (!left.degenerate()) {
list.insert(left);
list.forward();
}
Segment right = next.rightSub(s);
if (!right.degenerate()) {
list.insert(right);
list.forward();
}
}
}
} catch(Exception e) {
Xterm.println("Слишком много видимых отрезков ребра.");
System.exit(0);
}
}
/**
* Учесть тень от всех граней.
*/
protected void addShadow() {
for(int j=0; j<p.getFacetsQuantity(); j++)
addShadow(p.getFacet(j));
}
/**
* Конструктор класса.
* @param p Полиэдр.
* @param pr Вектор проектирования.
* @param angle Угол поворота в плоскости проекции.
*/
public ShadowDrawer(Polyedr p, R3Vector pr, double angle) {
super(p, pr, angle);
list = new L1ListSegments(MAXSIZE);
}
/**
* Изобразить видимую часть ребра полиэдра.
* @param s Обрабатываемое ребро полиэдра.
*/
public final void drawEdge(Edge s) {
begin = s.getBegin();
end = s.getEnd();
list.clear();
try {
list.insert(new Segment(t0, t1));
} catch(Exception e) {;}
addShadow();
try {
for (list.toFront(); ! list.end(); list.forward()) {
Segment u = list.after();
R3Vector begin = R3(u.getBegin());
R3Vector end = R3(u.getEnd());
draw(xnProection(begin), ynProection(begin),
xnProection(end), ynProection(end));
}
} catch(Exception e) {;}
Xterm.print(".");
}
}
SmartDrawer.java
/**
* @author Е.А. Роганов
* @version 1.1
* Класс SmartDrawer, обеспечивающий изображение проекции полиэдра
* с использованием двумерного хеширования граней.
*/
public class SmartDrawer extends ShadowDrawer {
/**
* Количество гнезд сетки в строке и столбце.
*/
private final static int SIZE = 50;
/**
* Максимальное число граней в гнезде.
*/
private final static int MAXFACETS = 200;
/**
* Массив гнезд, в которые попадает обрабатываемое ребро.
*/
private boolean[][] sockets;
/**
* Массив количеств граней в гнездах.
*/
private int[][] nmbFacets;
/**
* Массив множеств номеров граней.
*/
private int[][][] hashFacets;
/**
* Найти последний индекс гнезда, соответствующий t.
* @param t Координата.
*/
private int lastVal(double t) {
return Math.min((int)(t*SIZE),SIZE-1);
}
/**
* Найти первый индекс гнезда, соответствующий t.
* @param t Координата.
*/
private int firstVal(double t) {
return (int)(t*SIZE);
}
/**
* Конструктор класса.
* @param p Полиэдр.
* @param pr Вектор проектирования.
* @param angle Угол поворота в плоскости проекции.
*/
public SmartDrawer(Polyedr p, R3Vector pr, double angle) {
super(p, pr, angle);
nmbFacets = new int[SIZE][SIZE];
hashFacets = new int[SIZE][SIZE][MAXFACETS];
int i,j,k;
int imax = p.getFacetsQuantity();
for (i=0; i<imax; i++) {
Facet f=p.getFacet(i);
k = f.getVertexesQuantity();
double x0 = 1., y0 = 1., x1 = 0., y1 = 0.;
for (j=0; j<k; j++) {
R3Vector v = f.getVertex(j);
double x = xnProection(v);
double y = ynProection(v);
if (x < x0) x0 = x;
if (y < y0) y0 = y;
if (x > x1) x1 = x;
if (y > y1) y1 = y;
}
int jm = lastVal(x1);
int km = lastVal(y1);
for (j=firstVal(x0); j<=jm; j++)
for (k=firstVal(y0); k<=km; k++)
hashFacets[ j ][ k ][ nmbFacets[j][k]++ ] = i;
}
}
/**
* Учесть тень от всех граней.
*/
protected void addShadow() {
int i,j,k;
double x0 = Math.min(xnProection(begin), xnProection(end));
double x1 = Math.max(xnProection(begin), xnProection(end));
double y0 = Math.min(ynProection(begin), ynProection(end));
double y1 = Math.max(ynProection(begin), ynProection(end));
int jm = lastVal(x1);
int km = lastVal(y1);
for (j=firstVal(x0); j<=jm; j++)
for (k=firstVal(y0); k<=km; k++)
for (i=0; i<nmbFacets[j][k]; i++)
addShadow(p.getFacet( hashFacets[j][k][i] ));
}
}
PolyedrTest.java
import java.util.*;
import java.io.*;
/**
* @author Е.А. Роганов
* @version 1.1
* Класс PolyedrTest, ...
*/
public class PolyedrTest {
/**
* Функция main.
* @param args Массив аргументов командной строки.
* @exception Exception Исключительная ситуация, возникающая
* при ошибках чтения или преобразования данных из файла.
*/
public static void main(String[] args) throws Exception {
Polyedr p = new Polyedr(args[0]);
int type = Xterm.inputInt("Возможные типы изображения полиэдра:\n"+
" без удаления невидимых линий - 0\n"+
" с удалением невидимых ребер - 1\n"+
" с использованием хеширования - 2\n"+
"Выберите тип изображения (от 0 до 2) -> " );
while (true) {
R3Vector pr = new R3Vector();
double angle = Xterm.inputDouble("Угол поворота в плоскости " +
"проекции (в градусах): ");
switch (type) {
case 0:
SimpleDrawer d = new SimpleDrawer(p, pr, Math.PI*angle/180.0);
d.draw();
break;
case 1:
ShadowDrawer sd = new ShadowDrawer(p, pr, Math.PI*angle/180.0);
sd.draw();
break;
case 2:
SmartDrawer smd = new SmartDrawer(p, pr, Math.PI*angle/180.0);
smd.draw();
break;
default:
Xterm.println("Неверный тип изображения");
}
Thread.currentThread().setPriority(Thread.MIN_PRIORITY);
}
}
}
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.