Проект Выпуклая оболочка

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

В нем также рассматриваются аплеты, которые используются в качестве основы для создания простейшего графического интерфейса (GUI — graphics user interface), что дает возможность решать задачи на изображение графиков функций и различных графических объектов. Вопросы создания аплетов обсуждаются практически во всех изданиях, посвященных языку Java, в том числе и в книгах [10], [11] и [13].

Постановка задачи

Напомним сначала два определения, связанные с важнейшим математическим понятием — свойством выпуклости множеств.

Определение 11.1. Множество $$M$$ называется выпуклым, если для любых двух его точек весь отрезок прямой, соединяющий эти точки, принадлежит множеству: $$M\ \text{выпукло} \Longleftrightarrow (\forall x_1, x_2 \in M\ [x_1,x_2]\in M)$$.

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

Определение 11.2. Выпуклой оболочкой $$conv(M)$$ множества $$M$$ называется наименьшее выпуклое множество, содержащее $$M$$.

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

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

Теперь можно сформулировать основную задачу.

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

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

Мы будем трактовать поставленную задачу следующим образом: реализовать класс Convex с методами

Договоримся придерживаться стратегии вычисления всех характеристик оболочки сразу при добавлении новой точки (в методе add ); выполнение методов perimeter и area при этом будет сводиться просто к выдаче уже вычисленных ранее значений.

Если обозначить множество $$\mathbb{R}^2$$ точек плоскости через $$X$$, а совокупность всех выпуклых фигур на плоскости через $$\mathcal{P}$$, то тройка функций $$f\colon X^* \rightarrow \mathcal{P}$$ выпуклая оболочка последовательности точек, $$g\colon X^* \rightarrow \mathbb{R}$$ ее периметр и $$h\colon X^* \rightarrow \mathbb{R}$$ ее площадь в совокупности задает индуктивную функцию $$F\colon X^* \rightarrow \mathcal{P} \times \mathbb{R} \times \mathbb{R}$$, $$F = (f,g,h)$$.

Функцию перевычисления $$G$$ для нее более точно мы опишем чуть позже, а пока ограничимся следующим предварительным рассуждением. Пусть для некоторой последовательности точек плоскости выпуклая оболочка, а также ее периметр и площадь, уже известны. После добавления новой точки $$x\in X$$ возможны две ситуации: либо точка $$x$$ попадает внутрь оболочки, либо вне ее.

В первом случае выпуклая оболочка (а также ее периметр и площадь) не изменяются. Во втором — изменения происходят, но информации, хранящейся в функции $$F$$ (выпуклой оболочки, ее периметра и площади) вместе с координатами точки $$x$$ явно достаточно для определения новой выпуклой оболочки и ее изменившихся характеристик.

Хорошей моделью для описания изменяющейся оболочки является следующая: предположим, что во вновь добавляемой точке $$x$$ расположена лампочка, освещающая часть ребер старой оболочки, которые мы так и будем называть — освещенными. Для получения новой оболочки необходимо, как это хорошо видно из рис. 11.2, удалить все освещенные ребра, а концы оставшейся ломаной соединить двумя новыми ребрами с добавляемой точкой $$x$$.

Если добавляемая точка лежит на продолжении одного из ребер, то оболочка должна измениться так, как показано на рис. 11.3. Поэтому ребро, на продолжении которого лежит точка $$x$$, мы также будем считать освещенным.

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

Проектирование сверху вниз

Для разработки необходимой иерархии классов в данном случае достаточно воспользоваться давно известным методом — проектированием сверху вниз. Уточненная постановка задачи требует создания класса Convex, необходим еще и класс, содержащий метод main с тестирующей программой. Можно, конечно, добавить этот метод в класс Convex, но мы для этих целей создадим отдельный класс ConvexTest.

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

Интерфейс Figure должен содержать общие для всех возможных случаев выпуклой оболочки методы add, perimeter и area, а его реализациями будут являться классы "нульугольник" ( Void ), "одноугольник" ( Point ), "двуугольник" ( Segment ) и многоугольник ( Polygon ). Каждый из этих классов обязан обеспечивать реализацию всех методов интерфейса Figure, при этом метод add должен в качестве аргумента получать добавляемую точку, а возвращать выпуклую оболочку, перевычисленную с ее учетом.

Следовательно, необходим класс, который мы назовем R2Point, представляющий точку на плоскости и обеспечивающий все необходимые действия над объектами этого типа. Его вполне достаточно для реализации классов Void, Point и Segment, ибо в первом случае никакой информации в фигуре хранить вообще не нужно, а в двух последних нужно хранить только один (для "одноугольника") или два (для "двуугольника") экземпляра класса R2Point, представляющие соответственно единственную или две концевых точки этих выпуклых оболочек.

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

Итак, класс Deq будет представлять собой непрерывную реализацию дека объектов типа R2Point, а класс Polygon можно просто сделать выведенным (дочерним) для него. При этом класс Polygon оказывается одновременно реализующим ( implements ) интерфейс Figure и расширяющим ( extends ) класс Deq.

Это завершает проектирование иерархии классов, необходимой для решения поставленной задачи. Результат представлен на рис. 11.4.

В заключение данной секции разберемся с тем, как должны быть устроены реализации классов Void, Point и Segment. Для "нульугольника" все очевидно — методы perimeter и area возвращают нулевые значения, а возвращаемым значением метода add должен быть объект типа Point.

Класс "одноугольник" уже должен иметь конструктор с аргументом типа R2Point, сохраняющий эту точку в своей private -компоненте. Периметр и площадь здесь также являются нулевыми, а метод add может возвратить как объект типа Segment, так и неизмененный объект Point. Последнее должно иметь место в случае совпадения вновь добавляемой точки с уже имеющейся. Таким образом, реализация класса Point требует наличия в классе R2Point метода equal, позволяющего сравнивать точки плоскости на равенство. Напомним, что оператор == для объектов ссылочных типов возвращает true только в случае равенства ссылок, а не внутреннего содержания объектов.

Класс "двуугольник" обязан иметь две компоненты типа R2Point, в которые конструктором класса заносятся его концевые точки. Площадь любого "двуугольника" нулевая, а периметром естественно считать удвоенную длину отрезка (сравните "двуугольник" с треугольником). Добавление точки в данном случае может привести к трем различным ситуациям: "двуугольник" может превратиться в треугольник, он может остаться "двуугольником", но изменить одну из своих концевых точек, и, наконец, он может совсем не измениться. Класс R2Point должен обеспечивать методы, которые позволят различать эти ситуации, а итоговый вариант реализации классов Void, Point и Segment приведен в конце лекции.

Аналитическая геометрия и программирование

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

Ряд фактов из аналитической геометрии и векторной алгебры являются необходимой базой для решения сформулированных задач, однако только знание элементов вычислительной геометрии позволяет получить достаточно эффективные решения. Простейшим примером может служить задача вычисления площади треугольника по известным координатам его вершин. Известная из средней школы формула Герона$$S = \sqrt{p (p-a) (p-b) (p-c)}$$ требует большого числа умножений и четырех относительно медленно выполняемых операций извлечения квадратного корня. Основанная на связи площади с векторным произведением формула$$S = \frac{1}{2} |\vec a \times \vec b|$$ использует всего три умножения, одно из которых на самом деле сводится к сдвигу, что позволяет найти площадь треугольника значительно быстрее.

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

Расстояние $$d$$ между двумя точками на плоскости можно посчитать по известной формуле $$d = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2}$$, которая и используется в реализации метода dist. Два объекта типа R2Point соответствуют совпадающим точкам плоскости тогда и только тогда, когда попарно равны их координаты, что позволяет реализовать метод equal.

public static double dist(R2Point a, R2Point b) {
        return Math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    public static boolean equal(R2Point a, R2Point b) {
        return a.x==b.x  a.y==b.y;
    }
    public static double area(R2Point a, R2Point b, R2Point c) {
        return 0.5*((a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x));
    }

Для вычисления площади треугольника в методе area применена уже цитированная выше формула, основанная на следующем факте из векторной алгебры: модуль векторного произведения двух векторов равен площади параллелограмма, натянутого на эти вектора. Напомним, что векторным произведением $$\vec a \times \vec b$$ двух векторов $$\vec a$$ и $$\vec b$$ называется вектор $$\vec c$$, перпендикулярный векторам $$\vec a$$ и $$\vec b$$, такой, что $$|\vec c|=|\vec a| |\vec b| \sin \alpha$$, где $$\alpha$$ — угол между векторами $$\vec a$$ и $$\vec b$$. Одно из двух возможных направлений вектора $$\vec c$$ при этом определяется по правилу буравчика (при повороте ручки по направлению от $$\vec a$$ к $$\vec b$$ буравчик перемещается по направлению вектора $$\vec c$$ ).

Часто полезно использовать запись этого определения в координатах. Если $$\vec a = (a_x, a_y, a_z)$$, а $$\vec b = (b_x, b_y, b_z)$$, то координаты вектора $$\vec c$$ находятся по формуле$$\vec c = \left| \begin{array}{ccc} \vec i \vec j \vec k\\ a_x a_y a_z \\ b_x b_y b_z \end{array} \right| = (a_y b_z - a_z b_y) \vec i + (a_z b_x - a_x b_z) \vec j + (a_x b_y - a_y b_x) \vec k.$$

В том случае, когда вектора $$\vec a$$ и $$\vec b$$ расположены на плоскости, их векторное произведение имеет единственную не нулевую компоненту, вычисление которой и реализовано в методе area. Обратите внимание на то, что так вычисленная площадь является ориентированной, то есть может быть отрицательной.

Выяснение того факта, лежат ли три точки на одной прямой, сводится к вычислению площади треугольника и сравнению ее с нулем, а для того, чтобы точка $$t$$ прямой располагалась на отрезке $$[a,b]$$ этой же прямой, необходимо и достаточно принадлежности проекций этой точки проекциям на оси координат отрезка $$[a,b]$$. Вот как выглядит программная реализация этих идей.

public static boolean isTriangle(R2Point a, R2Point b, R2Point c) {
        return area(a, b, c) != 0.0;
    }
    public boolean inside(R2Point a, R2Point b) {
        return (a.x <= x  x <= b.x || a.x >= x  x >= b.x) 
            (a.y <= y  y <= b.y || a.y >= y  y >= b.y);
    }

Перед тем, как реализовать метод light, позволяющий выяснить, освещено ли ребро $$[a,b]$$ выпуклой оболочки из точки $$t$$, дадим строгое определение освещенности.

Определение 11.3. Ребро $$[a,b]$$ называется освещенным из точки $$t$$, если ориентированная площадь треугольника, образованного точками $$a$$, $$b$$ и $$t$$ отрицательна, либо если точка $$t$$ расположена на прямой, проходящей через точки $$a$$ и $$b$$, вне отрезка $$[a,b]$$.

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

public boolean light(R2Point a, R2Point b) {
        double s = area(a, b, this);
        return s < 0.0 || ( s == 0.0  ! inside(a, b));
    }

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

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

Пусть координаты граничных точек первого отрезка $$\overrightarrow{P_1 P_2}$$ равны $$(x_1, y_1)$$ и $$(x_2, y_2)$$, а второго $$\overrightarrow{P_3 P_4}$$ — $$(x_3, y_3)$$ и $$(x_4, y_4)$$. Тогда координаты левого нижнего угла ограничивающего прямоугольника первого отрезка будут равны $$(\widehat x_1, \widehat y_1)$$, а правого верхнего угла — $$(\widehat x_2, \widehat y_2)$$, где $$\widehat x_1 = \min(x_1, x_2)$$, $$\widehat y_1 = \min(y_1, y_2)$$, $$\widehat x_2 = \max(x_1, x_2)$$ и $$\widehat y_2 = \max(y_1, y_2)$$. Аналогично определяются координаты $$(\widehat x_3, \widehat y_3)$$ и $$(\widehat x_4, \widehat y_4)$$ левого нижнего и правого верхнего углов ограничивающего прямоугольника второго отрезка.

Ограничивающие прямоугольники пересекаются тогда и только тогда, когда пересекаются их проекции на каждую из двух осей, что сводится к истинности следующего предиката $$\widehat x_2 \geqslant \widehat x_3 \land \widehat x_4 \geqslant \widehat x_1 \land \widehat y_2 \geqslant \widehat y_3 \land \widehat y_4 \geqslant \widehat y_1$$.

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

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

Проверка факта пересечения отрезка с прямой осуществляется с помощью векторных произведений следующим образом. Точки $$P_3$$ и $$P_4$$ лежат по разные стороны от прямой $$P_1 P_2$$, если векторы $$\overrightarrow{P_1 P_3}$$ и $$\overrightarrow{P_1 P_4}$$ имеют различную ориентацию относительно вектора $$\overrightarrow{P_1 P_2}$$, то есть, если знаки векторных произведений $$\overrightarrow{P_1 P_3} \times \overrightarrow{P_1 P_2}$$ и $$\overrightarrow{P_1 P_4} \times \overrightarrow{P_1 P_2}$$ различны.

Таким образом, отрезки $$\overrightarrow{P_1 P_2}$$ и $$\overrightarrow{P_3 P_4}$$ пересекаются тогда и только тогда, когда одновременно выполняются следующие три условия:

1) пересекаются ограничивающие их прямоугольники;

2) $$(\overrightarrow{P_1 P_3} \times \overrightarrow{P_1 P_2}) \cdot (\overrightarrow{P_1 P_4} \times \overrightarrow{P_1 P_2}) \leqslant 0;$$

3) $$(\overrightarrow{P_3 P_1} \times \overrightarrow{P_3 P_4}) \cdot (\overrightarrow{P_3 P_2} \times \overrightarrow{P_3 P_4}) \leqslant 0$$.

Более подробное изложение решения этой и ряда других подобных задач может быть найдено в разделе "Вычислительная геометрия" книги [8].

Реализация класса Polygon

Нам осталось реализовать методы perimeter, area и add класса Polygon. Как это уже отмечалось при уточнении постановки задачи, вся работа по модификации выпуклой оболочки и перевычислению ее площади и периметра должна проводиться при добавлении новой точки, а действие методов perimeter и area будет сводиться просто к выдаче уже вычисленных ранее значений, хранящихся в private -компонентах.

class Polygon extends Deq implements Figure {
        private double s, p;
        public double perimeter() {
            return p;
        }
        public double area() {
            return s;
        }
        ...
    }

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

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

public Polygon(R2Point a, R2Point b, R2Point c) {
        pushFront(b);
        if (b.light(a, c)) {
            pushFront(a); pushBack(c);
        } else {
            pushFront(c); pushBack(a);
        }
        p = R2Point.dist(a, b) + R2Point.dist(b, c)
            + R2Point.dist(c, a);
        s = Math.abs(R2Point.area(a, b, c));
    }

Назовем ребро $$AB$$ (см. рис. рис. 11.6), соединяющее конец дека с его началом, текущим. Так как в деке в каждый момент времени доступны только два элемента — начало и конец, то и работать можно только с текущем ребром многоугольника. Текущее ребро многоугольника, впрочем, легко сменить: если переместить один элемент из начала дека в конец, то многоугольник не изменится, а текущем ребром станет ребро $$BC$$ (следующее за $$AB$$ в порядке против часовой стрелки). Если переместить из начала дека в конец еще один элемент, то текущим станет ребро $$CD$$ и т.д.

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

При реализации метода add в этом случае необходимо для всех освещенных ребер выпуклой оболочки выполнить следующие действия: удалить это ребро, уменьшить периметр $$p$$ оболочки на его длину и увеличить площадь $$s$$ оболочки на величину, равную площади треугольника, образованного удаляемым ребром и добавляемой точкой. После этого необходимо добавить к оболочке два новых ребра, а к ее периметру — сумму их длин (см. рис. рис. 11.6).

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

private void grow(R2Point a, R2Point b, R2Point t) {
        p -= R2Point.dist(a, b);
        s += Math.abs(R2Point.area(a, b, t));
    }

Полный текст построенной программы приведен ниже, в последней секции текущего параграфа.

Аплеты и работа с ними

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

Наилучший способ для этих целей — использование аплетов (applets). Аплеты значительно отличаются от обычных программ на языке Java, которые мы рассматривали до сих пор. Одним из важнейших отличий является то, что аплет не содержит метода main и не может быть запущен самостоятельно.

Аплеты запускаются с помощью браузера или специализированной программы для просмотра аплетов appletviewer, а для создания аплетов необходимо реализовывать подкласс класса Applet, определенного в пакете java.applet, являющимся составной частью библиотеки AWT.

Для целей вывода графической информации достаточно в классе, выведенном из класса Applet, переопределить метод paint. Мы познакомимся только с несколькими простейшими графическими примитивами:

В качестве первого примера рассмотрим решение следующей задачи.

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

Вот одно из возможных решений этой задачи.

Текст аплета

import java.awt.*;
import java.applet.*;
public class Primitives extends Applet {
    public void paint (Graphics g) {
        g.fillRect(20, 20, 40, 60);
        g.setColor(Color.red);
        g.drawLine(2, 2, 80, 80);
        g.drawOval(120, 120, 30, 40);
        g.drawRect(170, 170, 10, 15);
        g.setColor(Color.blue);
        g.fillOval(20, 150, 30, 30);
    }
}

Операторы import обеспечивают подключение необходимых классов библиотеки AWT для компиляции этой программы, выполняемой обычным образом. После того, как компилятором будет создан файл Primitives.class, аплет можно запустить только создав дополнительно еще один файл — Primitives.html. Именно он должен быть указан в качестве аргумента программе appletviewer или браузеру. Содержимое этого файла может быть примерно таким.

HTML-файл

<HTML><BODY>
<APPLET code="Primitives.class" width=200 height=200></APPLET>
</BODY></HTML>

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

appletviewer Primitives.html

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

Рассмотрим более интересную задачу на построение графика функции.

Задача 11.3. Создайте аплет,изображающий в окне размером 200х200 оси координат и график функции y=x2-x на промежутке [-2,2].

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

Текст аплета

import java.awt.*;
import java.applet.*;
public class FuncGraph extends Applet {
    private static final int SIZE = 200;
    private static final double k = 50.;

    private int f(double x) {
        return SIZE/2 - (int)(k * (x*(x*x-1)));
    }

    public void paint (Graphics g) {
        g.drawLine(0, SIZE/2, SIZE-1, SIZE/2);
        g.drawLine(SIZE/2, 0, SIZE/2, SIZE-1);

        g.setColor(Color.red);
        for (int i=0; i<SIZE; i++) {
            double x = (i - SIZE/2) / k;
            g.drawOval(i, f(x), 1, 1);
        }
    }
}

Файл для запуска аплета вполне аналогичен предыдущему случаю:

HTML-файл

<HTML><BODY>
<APPLET code="FuncGraph.class" width=200 height=200></APPLET>
</BODY></HTML>

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

Задача 11.4. Создайте аплет,изображающий в окне размером 200х200 график функции, задаваемой в полярных координатах $$(r,\varphi)$$ соотношением $$r = \sin 3\varphi$$

Для решения задачи нужно знать, что константа $$\pi$$ доступна программам на языке Java, как величина Math.PI, а функции $$\sin$$ и $$\cos$$ — как методы Math.sin и Math.cos соответственно. На сей раз будем рисовать график, изображая отрезки прямых, соединяющие последовательно вычисляемые точки графика.

Текст аплета

import java.awt.*;
import java.applet.*;
public class FuncPolGraph extends Applet {
    private static final int SIZE = 200;
    private static final double k = 95.;

    private int x(double fi) {
        return SIZE/2 + (int)(k * Math.sin(3.*fi) * Math.cos(fi));
    }
    private int y(double fi) {
        return SIZE/2 - (int)(k * Math.sin(3.*fi) * Math.sin(fi));
    }
    public void paint (Graphics g) {
	setBackground(Color.white);
        g.setColor(Color.blue);
        int xp = x(0.), yp = y(0.);
        for (double fi=0.; fi<2.*Math.PI; fi+=Math.PI/180.) {
            if (Math.sin(3.*fi) < 0)
		continue;
            g.drawLine(xp, yp, x(fi), y(fi));
            xp = x(fi); yp = y(fi);
        }
    }
}

HTML-файл

<HTML><BODY>
<APPLET code="FuncPolGraph.class" width=200 height=200></APPLET>
</BODY></HTML>

Результат работы этой программы приведен на рисунке рис. 11.7.

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

Задача 11.5. Создайте аплет, изображающий в окне стандартный прямоугольник (со сторонами, параллельными осям координат), заштрихованный под углом $$45^\circ$$.

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

Задача 11.7. Создайте аплет, изображающий в окне размером 600x600 график функции, заданной параметрически: $$x = \sin 2\varphi$$, $$y = \cos 3 \varphi$$.

Задача 11.8. Создайте аплет, изображающий в окне размером 600x600 линии уровня функции $$z = xy$$.

Задача 11.9. Создайте аплет, изображающий в окне размером 600x600 траекторию движения шара с начальными координатами $$(x_1, x_2)$$ и скоростью $$(v_1, v_2)$$ в квадратном билльярде со стороной единичной длины.

Задача 11.10. Модифицируйте текст эталонного проекта "Выпуклая оболочка" так, чтобы индуктивно определить:

a) среднее арифметическое значений функции $$\sin (xy)$$ в вершинах выпуклой оболочки;

b) максимальное значение функции $$\sin (xy)$$ в серединах сторон выпуклой оболочки;

c) мощность множества пересечения границы выпуклой оболочки с полосой $$-1 \leqslant y \leqslant 1$$ ;

d) площадь части выпуклой оболочки, расположенной внутри кольца $$1 \leqslant x^2+ y^2 \leqslant 4$$ ;

e) периметр части выпуклой оболочки, расположенной внутри кольца $$1 \leqslant x^2+ y^2 \leqslant 4$$ ;

f) количество ребер выпуклой оболочки, целиком расположенных внутри квадрата с вершинами $$(0,0)$$, $$(0,3)$$, $$(3,0)$$ и $$(3,3)$$ ;

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

h) количество ребер выпуклой оболочке, параллельных сторонам заданного треугольника;

i) угол между максимальным и минимальным ребрами выпуклой оболочки;

j) лежит ли заданная точка плоскости внутри выпуклой оболочки.

Задача 11.11. Модифицируйте текст эталонного проекта "Выпуклая оболочка" так, чтобы индуктивно определить:

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

b) расстояние от выпуклой оболочки до заданной прямой;

c) расстояние от выпуклой оболочки до заданного отрезка;

d) расстояние от выпуклой оболочки до заданного треугольника;

e) расстояние от выпуклой оболочки до заданного стандартного прямоугольника;

f) среднее арифметическое расстояний от заданной точки до вершин выпуклой оболочки;

g) сумму квадратов расстояний от заданной точки до вершин выпуклой оболочки;

h) сумму квадратов расстояний от начала координат до середин сторон выпуклой оболочки;

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

j) количество пар сторон выпуклой оболочки, расстояние между которыми не превосходит единицу.

Задача 11.12. Модифицируйте текст эталонного проекта "Выпуклая оболочка" так, чтобы индуктивно определить:

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

b) количество вершин выпуклой оболочки, расположенных в кольце $$1 \leqslant x^2 + y^2 \leqslant 4$$ ;

c) количество вершин выпуклой оболочки, расстояние от которых до квадрата с вершинами $$(0,0)$$, $$(1,0)$$, $$(0,1)$$ и $$(1,1)$$ не превосходит единицу;

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

e) максимальный стандартный прямоугольник, содержащийся в выпуклой оболочке;

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

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

h) диаметр выпуклой оболочки; диаметром $$d(M)$$ множества $$M$$ называется точная верхняя граница расстояний между всевозможными точками множества:$$$d(M) = \sup_{x_1,x_2\in M}|\overrightarrow{x_1 x_2}|;$$$

i) длину минимальной диагонали выпуклой оболочки;

j) координаты центра тяжести выпуклой оболочки с вершинами, массы $$m_i$$ которых вводятся вместе с их координатами; $$x$$ -координата центра тяжести определяется по формуле$$$c_x = \frac{\sum x_i m_i}{\sum m_i};$$$ $$y$$ -координата вычисляется аналогично.

Задача 11.13. Модифицируйте текст эталонного проекта "Выпуклая оболочка" так, чтобы индуктивно определить:

a) мощность множества точек пересечения границы выпуклой оболочки с окружностью $$x^2+y^2=1$$ ;

b) мощность множества точек пересечения границы выпуклой оболочки с кругом $$x^2+y^2 \leqslant 1$$ ;

c) мощность множества точек пересечения границы выпуклой оболочки с эллипсом $${x^2}/{a^2} + {y^2}/{b^2} = 1$$ ;

d) мощность множества точек пересечения границы выпуклой оболочки с гиперболой $${x^2}/{a^2} - {y^2}/{b^2} = 1$$ ;

e) мощность множества точек пересечения границы выпуклой оболочки с заданной прямой;

f) мощность множества точек пересечения границы выпуклой оболочки с заданным отрезком;

g) мощность множества точек пересечения границы выпуклой оболочки со сторонами заданного стандартного прямоугольника;

h) мощность множества точек пересечения границы выпуклой оболочки с заданным заполненным прямоугольником;

i) мощность множества точек пересечения границы выпуклой оболочки со сторонами заданного треугольника;

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