авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 5 | 6 ||

«министерство образования российской федерации московский государственный индустриальный университет кафедра информационные системы и технологии центр компьютерных ...»

-- [ Страница 7 ] --

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

public class Vertex extends R3Vector { public Vertex(double x, double y, double z) { super(x, y, z);

} } Ребра полиэдра будем представлять с помощью класса Edge, в каждом экземпляре которого содержатся две private-компоненты типа Vertex, соответствующие началу и концу ребра. В подобных ситуациях для обес печения возможности получения координат начала и конца ребра исполь зуют так называемые методы-селекторы getBegin и getEnd.

public class Edge { private Vertex begin;

private Vertex end;

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

this.end = end;

} public final Vertex getBegin() { return begin;

} public final Vertex getEnd() { return end;

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

public class Facet { private Vertex[] vertexes;

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

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

} public final Vertex getVertex(int i) { return vertexes[i];

} Полиэдр в целом, наконец, будем задавать с помощью класса Polyedr.

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

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

import java.util.*;

import java.io.*;

public class Polyedr { private Vertex[] vertexes;

private Edge[] edges;

private Facet[] facets;

public Polyedr(String file) throws Exception {...

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

} public final Vertex getVertex(int i) { return vertexes[i];

} public final int getEdgesQuantity() { return edges.length;

} §4. Проект Изображение полиэдра 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.awt) содержит среди множества других класс Frame, позволяющий создать фрейм и, используя простейшие графические примитивы, постро ить в нем требуемое изображение. Класс AwtDrawer будет являться расши рением класса Frame, а основным методом рисования проекции отрезков ребер будет метод draw, изображающий прямолинейный отрезок. Коор динаты точек при этом предполагаются нормированными и абсцисса и ордината должны быть заключены между нулем и единицей.

import java.awt.*;

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

private static final int YLEN = 500;

private static final int DELTA= 100;

private Image offScrImage;

private Graphics offScrGC;

private Graphics g;

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

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

setBackground(Color.white);

g = getGraphics();

show();

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

offScrGC = offScrImage.getGraphics();

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

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

offScrGC.setColor(Color.black);

} public final void draw(double xb, double yb, double xe, double ye) { 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 пакета AWT уже встречался нам при рассмотрении аплетов. Именно в нем определены все основные графические примитивы.

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

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

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

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

public class SimpleDrawer extends AwtDrawer { protected Polyedr p;

protected R3Vector pr;

private R3Vector x;

private R3Vector y;

private double xmin;

private double ymin;

private double size;

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

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

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

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

} public SimpleDrawer(Polyedr p, R3Vector pr, double angle) { this.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 { Глава III. Применение ООП к разработке программных проектов 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;

ip.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;

ip.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. Второй из векторов искомой тройки §4. Проект Изображение полиэдра строится с помощью уже найденного вектора нормали (нормированному вектору проектирования) по следующему правилу. Если (a, b, c) коор динаты вектора нормали, то векторы с координатами (b, a, 0) и (0, c, b) оба ему ортогональны, и при этом один из них заведомо не нулевой. Он то и выбирается в качестве второго из векторов базиса (в программной реализации ему соответствует компонента x класса SimpleDrawer).

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

Заключительным шагом является осуществление поворота на заданный угол angle в плоскости проекции. Как известно из аналитической геомет рии, поворот в плоскости Oxy на угол эквивалентен умножению вектора координат (x, y) на матрицу cos sin.

sin cos Для осуществления этих операций используются методы mul и plus клас са R3Vector, позволяющие умножить вектор на число и вычислить сумму двух векторов соответственно.

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

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

Наиболее содержательная часть исходной задачи учет затенения частей ребер гранями полиэдра будет решаться с помощью класса ShadowDrawer, обсуждению которого посвящена следующая секция пара графа. В ней выяснится, что для работы с тенями (точнее с просветами 260 Глава III. Применение ООП к разработке программных проектов Рис. 22. Иерархия классов проекта дополнениями теней) целесообразно создать еще два класса Segment и L1ListSegments.

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

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

3. Работа с тенями от граней. Так как плоское изображение полиэд ра состоит из проекций видимых частей ребер, а изображать проекцию любого набора отрезков мы уже научились, то осталось только правильно §4. Проект Изображение полиэдра ¤  ¦ ©§ §  §     Рис. 23. Тень от грани на ребре учесть влияние теней от граней. Напомним, что хотя в программной ре ализации используется произвольно заданный вектор проектирования, в теоретических рассуждениях мы считаем его направленным вертикально вверх. Плоскость, на которой изображается полиэдр, при этом оказыва ется горизонтальной.

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

Первые мы будем называть просветами, а вторые тенями. Рисунок иллюстрирует эти понятия.

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

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

Важным наблюдением, существенно упрощающим искомый алгоритм, является тот факт, что задача нахождения теней и просветов на конкрет ном ребре одномерная. Сопоставив началу ребра координату 0, а кон цу 1, мы можем установить взаимно однозначное соответствие между трехмерными координатами точек ребра и введенными одномерными ко ординатами. После этого каждый из просветов будет представлять собой отрезок, а реализовывать его будет класс Segment, в каждом экземпляре которого должны храниться одномерные координаты начала и конца об рабатываемого отрезка. Методы данного класса обязаны обеспечить все 262 Глава III. Применение ООП к разработке программных проектов необходимые действия с отрезками, которые понадобятся при определе нии множества просветов.

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 b. Пересечение двух отрезков всегда явля ется отрезком (возможно, вырожденным), который вычисляется в методе intersection, а разность двух отрезков всегда состоит из двух отрезков, каждый из которых может оказаться вырожденным. Левая и правая ком поненты разности вычисляются с помощью методов leftSub и rightSub соответственно.

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

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

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

public class ShadowDrawer extends SimpleDrawer { protected R3Vector begin;

protected R3Vector end;

private static final int MAXSIZE = 128;

private L1ListSegments list;

private static final double t0 = 0.;

private static final double t1 = 1.;

private R3Vector R3(double t) { return R3Vector.plus( R3Vector.mul((1.-t), begin), R3Vector.mul(t, end) );

} protected final void addShadow(Facet f) { try { Глава III. Применение ООП к разработке программных проектов 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;

jp.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());

§4. Проект Изображение полиэдра draw(xnProection(begin), ynProection(begin), xnProection(end), ynProection(end));

} } catch(Exception e) {;

} Xterm.print(".");

} } Метод drawEdge фиксирует обрабатываемое ребро, записывая его на чало и конец в компоненты begin и end, и инициализирует список просве тов list, помещая в него единственный элемент ребро целиком. Затем с помощью вызова метода addShadow производится учет теней от всех граней полиэдра и осуществляется изображение всего списка оставшихся просветов. Для изображения просвета необходимо вычисление трехмер ных координат точек ребра по известным их одномерным координатам.

Это действие выполняется с помощью метода R3 по известной из анали тической геометрии формуле.

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

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

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

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

Тень от грани на ребро при этом оказывается просто пересечением ре бра с этой призмой. Заметим, что призму следует считать открытой, т.е.

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

Естественно попытаться свести нахождение пересечения ребра с приз мой к каким-нибудь более элементарным операциям. Мы сделаем это, представив призму в виде пересечения открытых полупространств. На пример, треугольную призму можно представить в виде пересечения че тырех полупространств (см. рис. 25).

266 Глава III. Применение ООП к разработке программных проектов Рис. 25. Нахождение тени от грани Первое полупространство ограничено плоскостью, проходящей через грань полиэдра, и расположено со стороны, противоположной направле нию вектора проектирования. Это полупространство мы назовем гори зонтальным. Остальные полупространства (их число совпадает с количе ством ребер грани) ограничены вертикальными плоскостями, проходящи ми через ребра грани, и расположены так, что сама грань (или, что тоже самое ее центр) содержится в соответствующем полупространстве. Эти полупространства мы будем называть вертикальными.

Искомое пересечение ребра и призмы, представляющей собой тень, сводится теперь к последовательному нахождению пересечения ребра с полупространствами (сначала горизонтальным, а затем всеми верти кальными). Приведем реализацию всех необходимых для этого методов класса 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;

in;

i++) { a = b;

b = f.getVertex(i);

result.intersection(vCross(a, b, f.getCenter()));

if (result.degenerate()) return result;

} §4. Проект Изображение полиэдра 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 на ограничивающей его плос кости и вектором внешней нормали n к этой плоскости. Не разбираясь по ка в деталях реализации метода crossWith с указанными аргументами (в тексте программы это точка a и вектор нормали n), обсудим задачу нахо ждения одномерной тени, решаемую методами shadow, hCross и vCross.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

doc:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Makefile.

# -*- mode: makefile -*.PHONY : all doc clean veryclean cube ccc sticks tagl king dragon \ x29 apple glass4 torus pear vw bones beeth teapot cow babem 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 274 Глава III. Применение ООП к разработке программных проектов apple: $(CLASSFILES) java PolyedrTest data/apple_logo.geom glass4: $(CLASSFILES) java PolyedrTest data/glass4.geom torus: $(CLASSFILES) java PolyedrTest data/torus.geom pear: $(CLASSFILES) java PolyedrTest data/pear.geom 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. * Класс R3Vector, реализующий вектор (Vector) в пространстве (R3).

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

*/ private double x, y, z;

/** §4. Проект Изображение полиэдра * Конструктор вектора, заданного его координатами.

* @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);

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

* @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 Второй вектор.

§4. Проект Изображение полиэдра * @return Векторное произведение векторов.

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

} } Vertex.java.

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

*/ public class Vertex extends R3Vector { /** * Конструктор.

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

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

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

*/ public Vertex(double x, double y, double z) { super(x, y, z);

} } Edge.java.

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

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

*/ private Vertex begin;

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

*/ private Vertex end;

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

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

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

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

this.end = end;

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

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

*/ public final Vertex getBegin() { return begin;

} /** Глава III. Применение ООП к разработке программных проектов * Получить конец ребра.

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

*/ public final Vertex getEnd() { return end;

} } Facet.java.

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

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

*/ private Vertex[] vertexes;

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

*/ private R3Vector center;

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

*/ private R3Vector normal;

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

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

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

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

center = new R3Vector(0., 0., 0.);

for (int i=0;

ivertexes.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];

} §4. Проект Изображение полиэдра /** * Получить центр грани.

* @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. * Класс 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())];

Глава III. Применение ООП к разработке программных проектов facets = new Facet[Integer.parseInt(st.nextToken())];

edges = new Edge[Integer.parseInt(st.nextToken())];

for (int i=0;

ivertexes.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;

ifacets.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;

jsize;

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 Количество граней полиэдра.

§4. Проект Изображение полиэдра */ 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);


Глава III. Применение ООП к разработке программных проектов } /** * Найти пересечение с отрезком 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. * Класс L1ListSegments, реализующий односвязный список отрезков.

*/ public class L1ListSegments { /** * Массив отрезков.

*/ private Segment[] array;

/** * Массив ссылок.

*/ private int[] next;

/** * Нил списка.

*/ private int nilList;

/** * Нил свободного места.

*/ private int nilFree;

/** * Элемент до указателя.

*/ private int before;

/** * Элемент за указателем.

*/ §4. Проект Изображение полиэдра 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;

isize-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() { Глава III. Применение ООП к разработке программных проектов 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 Удаляемый элемент.

§4. Проект Изображение полиэдра * @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. * Класс 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);

Глава III. Применение ООП к разработке программных проектов 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. * Класс SimpleDrawer, обеспечивающий изображение проекции полиэдра.

*/ public class SimpleDrawer extends AwtDrawer { /** * Полиэдр.

*/ protected Polyedr p;

/** * Единичный вектор проектирования.

*/ protected R3Vector pr;

/** * Единичный X-вектор плоскости проектирования.

*/ private R3Vector x;

/** * Единичный Y-вектор плоскости проектирования.

*/ private R3Vector y;

/** * Минимальная X-координата проекции полиэдра.

*/ private double xmin;

§4. Проект Изображение полиэдра /** * Минимальная 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);

Глава III. Применение ООП к разработке программных проектов } 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;

ip.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;

ip.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. * Класс ShadowDrawer, обеспечивающий изображение проекции * полиэдра с удалением невидимых линий.


*/ public class ShadowDrawer extends SimpleDrawer { /** * Начало изображаемого ребра.

*/ protected R3Vector begin;

§4. Проект Изображение полиэдра /** * Конец изображаемого ребра.

*/ 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;

in;

i++) { a = b;

b = f.getVertex(i);

result.intersection(vCross(a, b, f.getCenter()));

if (result.degenerate()) return result;

} Глава III. Применение ООП к разработке программных проектов 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();

§4. Проект Изображение полиэдра } 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;

jp.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.

Глава III. Применение ООП к разработке программных проектов /** * @author Е.А. Роганов * @version 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;

iimax;

i++) { Facet f=p.getFacet(i);

k = f.getVertexesQuantity();

§4. Проект Изображение полиэдра double x0 = 1., y0 = 1., x1 = 0., y1 = 0.;

for (j=0;

jk;

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;

inmbFacets[j][k];

i++) addShadow(p.getFacet( hashFacets[j][k][i] ));

} } PolyedrTest.java.

import java.util.*;

import java.io.*;

/** * @author Е.А. Роганов * @version 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"+ 294 Глава III. Применение ООП к разработке программных проектов " с использованием хеширования - 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);

} } } § 5. Дополнительные задачи Задача 5.1. Создайте аплет, вводящий целые координаты двух пар точек на плоскости, рассматриваемых как пара противоположных вершин двух стандартных прямоугольников (прямоугольников со сторонами, па раллельными осям координат), изображающий границу объединения этих прямоугольников.

Задача 5.2. Напишите программу, печатающую площадь поверхно сти и объем двух n-мерных стандартных параллелепипедов. Стандартным параллелепипедом называется множество = {(x1, x2,..., xn ) R : i 1..n ai xi bi }.

Задача 5.3. Создайте аплет, изображающий график функции f (x) на заданном отрезке. Формулу, задающую функцию f (x), следует пред варительно откомпилировать с помощью одного из методов, изложенных в проекте Компилятор формул.

Задача 5.4. Напишите программу, вводящую последовательность це лых чисел и печатающую три ее таких (не обязательно различных) эле мента x, y и z, что xy = z, или No, если таких элементов нет.

§5. Дополнительные задачи Задача 5.5. Напишите программу, вводящую натуральное число x и печатающую наиболее близкую к x простую дробь вида m/n со знаме нателем n, не превосходящем 100.

Задача 5.6. Напишите программу, которая вводит с клавиатуры непустой массив целых чисел и печатает число локальных максимумов (элемент является локальным максимумом, если он не имеет соседей, больших, чем он сам).

Задача 5.7. Напишите программу, вводящую последовательность це лых чисел и печатающую Yes, если среди ее элементов с четными номе рами найдется равный некоторому элементу с нечетным номером, и No иначе.

Задача 5.8. Напишите программу, вводящую последовательность це лых чисел и печатающую их наибольший общий делитель.

Задача 5.9. Напишите программу, вводящую последовательность це лых чисел и печатающую их наименьшее общее кратное.

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

Задача 5.11. Напишите программу, вводящую последовательность целых чисел, которая считает их массами имеющихся в наличии предме тов и выясняет, можно ли выбрать из них какое-то количество предметов с суммарным весом 100.

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

Задача 5.13. Напишите программу, вводящую последовательность целых чисел, печатающую ее наиболее длинную невозрастающую подпо следовательность.

Задача 5.14. Напишите программу, вводящую последовательность целых чисел, печатающую ее наиболее длинную убывающую подпосле довательность.

Задача 5.15. Напишите программу, вводящую последовательность целых чисел, печатающую монотонный сегмент максимальной длины.

296 Глава III. Применение ООП к разработке программных проектов Задача 5.16. Напишите программу, вводящую последовательность целых чисел, печатающую два одинаковых ее сегмента максимальной дли ны.

Задача 5.17. Напишите программу, вводящую последовательность целых чисел, печатающую два зеркально симметричных ее сегмента мак симальной длины.

Задача 5.18. Напишите программу, вводящую последовательность целых чисел, печатающую такой ее элемент x, что количество элемен тов, меньших x, совпадает с количеством элементов больших x, или No, если такого элемента x не существует.

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

Задача 5.20. Напишите программу, вводящую натуральное число и печатающее его представление в виде суммы четырех квадратов целых чисел или No, если такого представления не существует.

Задача 5.21. Напишите программу, вводящую четное натуральное число и печатающее его представление в виде суммы двух простых чисел или No, если такого представления не существует.

Задача 5.22. Напишите программу, вводящую нечетное натуральное число и печатающее его представление в виде суммы трех простых чисел или No, если такого представления не существует.

Задача 5.23. Напишите программу, вводящую целые коэффициенты двух многочленов одной переменной и печатающую коэффициенты их произведения.

Задача 5.24. Напишите программу, вводящую целые коэффициенты многочлена и находящую все его рациональные корни.

Задача 5.25. Напишите программу, вводящую последовательность пар целых чисел, которая считает их координатами последовательных вершин ломаной на плоскости и определяет, является ли она самопересе кающейся.

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

Задача 5.27. Напишите программу, вводящую последовательность четверок (точнее пар пар) целых чисел, которая считает их координатами §5. Дополнительные задачи противоположных вершин последовательности стандартных прямоуголь ников и определяет, существуют ли среди них два непересекающихся.

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

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

Задача 5.30. Напишите программу, вводящую последовательность пар действительных чисел, которая считает их координатами точек на плоскости и определяет, образуют ли какие-либо четыре из них прямо угольник (не обязательно со сторонами, параллельными осям координат).

Задача 5.31. Напишите программу, вводящую последовательность пар действительных чисел, которая считает их координатами точек на плоскости и находит среди них такую, что сумма расстояний от нее до всех остальных точек минимальна.

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

Задача 5.33. Напишите программу, вводящую последовательность наборов (x1, y1, x2, y2 ) координат концов отрезков, и определяющую, образует ли этот набор отрезков многоугольник.

Задача 5.34. Напишите программу, вводящую последовательность наборов (x1, y1, x2, y2 ) координат концов отрезков, и определяющую, образует ли этот набор отрезков ломаную линию (не обязательно со зве ньями, следующими в порядке ввода).

Задача 5.35. Напишите программу, вводящую последовательность наборов (x1, y1, x2, y2 ) координат концов отрезков, и определяющую, образует ли этот набор отрезков множество многоугольников.

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

298 Глава III. Применение ООП к разработке программных проектов Задача 5.37. Напишите программу, вводящую последовательность пар действительных чисел, которая считает их координатами точек на плоскости и определяет наибольшее количество из них, не лежащих на одной прямой.

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

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

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

Задача 5.41. Напишите программу, вводящую последовательность наборов (x, y, z, r), которая рассматривает их в качестве координат цен тров сфер и их радиусов и определяет, вложены ли они друг в друга, как матрешки (не обязательно в порядке их ввода).

Задача 5.42. Создайте аплет, вводящий натуральное число n 3, находящий и изображающий какую-либо траекторию обхода конем шах матной доски размера n n.

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

Задача 5.44. Создайте аплет, изображающий дерево вывода задан ного предиката, который воодится с клавиатуры.

Литература [1] Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгорит мы. M.: Изд. дом Вильямс, 2000.

[2] Бадд Т. Объектно-ориентированное программирование в дей ствии. СПб.: Питер Паблишинг, 1997.

[3] Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир, 1985.

[4] Грис Д. Наука программирования. М.: Мир, 1984.

[5] Керниган Б., Ритчи Д. Язык программирования Си, 2-е изд. M.:

Финансы и статистика, 1992.

[6] Кнут Д. Искусство программирования, 3-е изд., Т.1. Основные алго ритмы. M.: Изд. дом Вильямс, 2000.

[7] Кнут Д. Искусство программирования, 3-е изд., Т.2. Получисленные алгоритмы. M.: Изд. дом Вильямс, 2000.

[8] Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и ана лиз. M.: МЦНМО, 2000.

[9] Кушниренко А.Г., Лебедев Г.В. Программирование для математи ков. М., Наука, 1988.

[10] Морган М. Java 2. Руководство разработчика. M.: Изд. дом Ви льямс, 2000.

[11] Нотон П., Шилдт Г. Полный справочник по Java. Киев: Диалекти ка, 1997.

[12] Страуструп Б. Язык программирования C++, 3-е изд. СПб.;

М.:

Невский диалект Издательство БИНОМ, 1999.

[13] Флэнэген Д. Java in a Nutshell. Полное руководство. Киев: BHV, 1998.

[14] Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995.



Pages:     | 1 |   ...   | 5 | 6 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.