Класс Point (Точка) Класс Polygon (Многоугольник) Класс Polygon (Полигон) Ребра Класс Point (Точка) Конструкторы Векторная арифметика Операции отношения Относительное положение точки и прямой линии Полярные координаты Клacc Point содержит элементы данных х и у для хранения координат очки. Компонентные функции обеспечивают выполнение операций по определению положения точки относительно заданного отрезка прямой линии и вычисления расстояния от заданной точки до прямой линии. Дополнительные компонентные функции рассматривают текущую точку как вектор и перегружают соответствующие операции для реализации векторной арифметики, используя ключевое слово operator. Включены также компонентные функции, возвращающие значения полярного угла и длины. class Point { public: double x; double у; Point(double _x = 0.0, double _y =0.0); Point operator+(Point&); Point operator-(Point&); friend Point operator* (double, Point&); // возвращает координату х, если в качестве индекса // координаты указано значение О, или координату у при индексе 1 double operator[] (int); // одинаковы ли точки ? int operator== (Point&); int operator!= (Point&); // лексикографический порядок отношений, точка а < точки b, // если либо а.х < b.х, либо a.х = b.x и а.у < b.у. int operator< (Point&); int operator> (Point&); // Возвращается значение типа перечисления, указывающее на положение // точки относительно отрезка // enum {LEFT, RIGHT, BEYOND, BEHIND, BETWEEN, ORIGIN, DESTINATION}; // СЛЕВА, СПРАВА, ВПЕРЕДИ, ПОЗАДИ, МЕЖДУ, НАЧАЛО, КОНЕЦ int classify(Point&, Point&); int classify(Edge&); // ребро вместо пары точек // Угол точки в полярной системе координат // возвращает -1, если точка = (0, 0) double polarAngle(void); double length(void); double distance(Edge&); }; Конструкторы Конструктор инициализирует новую точку с координатами х и у: Point::Point (double _х, double _y): х (_х), у (_у) { } Если аргумент не указан, то по умолчанию инициализируется точка в начале координат (О, О). Можно инициализировать точку как дубль другой точки. Например, обращение Point p(q) инициализирует новую точку р с теми же координатами, как и точка q. В этом случае инициализация осуществляется копирующим конструктором по умолчанию (существующем в компиляторе" языка C++), который выполняет копию со всеми элементами. Векторная арифметика Векторное сложение и векторное вычитание выполняется с помощью операций-функций со знаками операций + и - соответственно: Point Point::operator+ (Point &p) { return Point (х + р.х, у + р. у); } Point Point::operator- (Point &p) { return Point (x - р.х, у - p. у); } Операция скалярного умножения реализована в виде дружественной функции классу Point, а не члена класса, поскольку ее первый операнд не относится к типу Point. Оператор определен следующим образом: Point operator* (double s , Point &p) { return point (s * p.x, s * p.y); } Операция-функция operator[] возвращает координату х текущей точки, если в обращении в качестве индекса координаты было указано значение О, или координату у при указании значения индекса 1: double Point::operator [] (int i) { return (i == 0) ? х : y; } Операции отношения Операции отношения == и != используются для определения эквивалентности двух точек: int Point::operator== (Point &p) { return (x == p.x) && (y == p.y); } int Point::operator!= (Point &p) { return !(*this == p); } Операции < и > реализуют лексикографический порядок отношений, когда считается, что точка а меньше точки b, если либо а.х < b.х, либо a.x = b.х и а.у < b.у. Для двух данных точек сначала сравниваются их x-координаты, и, если они равны, то сравниваются y-координаты. Такой порядок иногда называется словарным порядком отношений, поскольку точно пo такому же правилу располагаются в словаре двухбуквенные слова. int Point::operator< (Point &p) { return ((x < p.x) || ((x == p.x) && (y} int Point::operator> (Point &p) { return ((x>p.x) || ((x == p.x) && (y > p.y))); } Упорядочение точек на плоскости может быть выполнено бесконечным числом пособов. Тем не менее удобно использовать операции < и < для канонического упорядочения, поскольку нам часто придется сохранять точки в словарях и эти операторы можно будет применять для упрощения необходимых функций сравнения. Прежде, чем переходить к остальным компонентным функциям класса Point, рассмотрим следующий простой пример, который показывает применение объектов класса Point. Упорядоченная пара векторов (здесь p0p1 и p0p2) называется положительно ориентированной, если кратчайший поворот от первого вектора ко второму осуществляется против часовой стрелки. Если наоборот, то эта пара отрицательно ориентирована. Пример положительно определенной пары: (1,0) и (0,1). Отрицательно ориентирована пара (0,1) и (1,0). Ориентация пары векторов a=(xa,ya) и b=(xb,yb) может быть получена как знак sin(xayb-xbya). Более подробно об ориентации читайте в начальном учебнике по линейной алгебре или аналитической геометрии. Выражение xayb-xbya равно площади со знаком паралеллограмма с вершинами 0, a, b, a+b. Функция orientation возвращает значение 1, если обрабатываемые три точки ориентированы положительно, -1, если они ориентированы отрицательно, или 0, если они коллинеарны. int orientation (Point &pO, Point &pl, Point &p2) { Point a = p1 - pO; Point b = p2 - pO; double sa = a.x * b.y - b.х * а.у; if (sa > 0.0) return 1; if (sa < 0.0) return -1; return 0; } Относительное положение точки и прямой линии Одна из важнейших операций заключается в определении положения точки относительно направленного отрезка прямой линии. Результат выполнения операции показывает, лежит ли точка слева или справа от направленного отрезка прямой линии или, если она совпадает с прямой линией, располагается она после конца направленного отрезка этой прямой линии, до начала, а если ни то, ни другое, то не совпадает ли она с началом или с концом или лежит между ними. Направленный отрезок прямой линии четко разделяет плоскость на семь непересекающихся областей и эта операция сообщает, какой из этих областей принадлежит точка. Для определения положения текущей точки относительно отрезка прямой линии p0p1, направленного от точки р0 к точке p1, используется компонентная функция classify. Возвращается значение типа перечисления, указывающее на положение текущей точки: enum {LEFT, RIGHT, BEYOND, BEHIND, BETWEEN, ORIGIN, DESTINATION}; // СЛЕВА, СПРАВА, ВПЕРЕДИ, ПОЗАДИ, МЕЖДУ, НАЧАЛО, КОНЕЦ int Point::classify(Point &p0, Point &pl) { Point p2 = *this; Point a = p1 - pO; Point b = p2 - pO; double sa = a. x * b.y - b.x * a.y; if (sa > 0.0) return LEFT; if (sa < 0.0) return RIGHT; if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0)) return BEHIND; if (a.length() < b.length()) return BEYOND; if (pO == p2) return ORIGIN; if (p1 == p2) return DESTINATION; return BETWEEN; } Вначале проверяется ориентация точек p0, p1 и р2, чтобы определить, располагается ли точка р2 слева или справа, или она коллинеарна с отрезком p0p1. В последнем случае необходимы дополнительные вычисления, ели векторы a=pl-pO и b=р2-p0 имеют противоположное направление, то точка р2 лежит позади направленного отрезка p0p1 если вектор а короче вектора b, то точка р2 расположена после отрезка p0p1. В противном случае точка р2 сравнивается с точками p0 и р1 для определения, совпадает ли с одной из этих концевых точек или лежит между ними. Для удобства предусмотрена несколько иная версия компонентной функции classify, которой в качестве аргумента передается ребро вместо пары точек. int Point::classify(Edge &e) { return classify(e.org, e.dest); } Определение относительного положения точки и прямой линии используется очень часто. В некоторых применениях достаточна более грубая классификация (т. е. достаточно индикации положения точки слева или справа от прямой линии, или просто фиксации совпадения с ней). В других же применениях требуется полная схема этой классификации. Полярные координаты Система полярных координат обеспечивает второй способ задания положения точки на плоскости. Полярная ось выходит из точки начала координат 0 и направлена в виде горизонтального луча вправо, как показано рис. 2. Точка а представляется парой чисел (ra, Thetaa). Принимая точку a за вектор, начинающийся в точке начала координат, число ra определяет тину вектора, а Thetaa - его полярный угол (угол, образуемый между вектором а и полярной осью и отсчитываемый в направлении вращения против часовой стрелки). Соответствие между парами чисел (ra, Thetaa) и точками не является однозначным: множество пар могут представлять одну и ту же точку. Пара (0, Theta) соответствует началу координат для любого значения 0. Более того, пары чисел (r, Theta + 360k) соответствуют одной и той же точке для любого целого числа k. Точка может быть представлена как в декартовых, так и в полярных координатах и иногда бывает необходимо переходить от одной системы к другой. Как это очевидно из рис. 2, два выражения х = r cos(Theta), у = r sin(Theta) осуществляют преобразования из полярных координат (r, Theta) в декартовы координаты (х, у). Для обратного преобразования координата расстояния определяется как ||a|| = КОРЕНЬ КВАДРАТНЫЙ(x2 + y2) Чтобы выразить полярный угол Theta в функции от х и у заметим, что существует соотношение tan Theta = y/x из которого следует Theta = arctan (y/x) Для использования этого выражения в функции polarAngle необходимо различать квадранты на плоскости и учитывать случай возможного равенства нулю координаты х: double Point::polarAngle(void) { if ((x == 0.0) && (у == 0.0)) return -1.0; if (x == 0.0) return ((y > 0.0) ? 90 : 270); double theta = atan(y/x); // в радианах theta *= 360 / (2 * 3.1415926); // перевод в градусы if (x > 0.0) // 1 и 4 квадранты return ((y >= 0.0) ? theta : 360 + theta); else // 2 и З квадранты return (180 + theta); Заметим, что функция polarAngle возвращает значение -1.0, если текущий вектор является нулевым вектором (в противном случае возвращается неотрицательное значение). Это обстоятельство мы используем впоследствии для упрощения описания функции сравнения, основанной на задании полярного угла. Компонентная функция length возвращает длину текущего вектора double Point::length (void) { return sqrt(x*x + y*y); } Компонентная функция distance возвращает значение расстояния (со знаком) от текущей точки до ребра. Эту функцию определим ниже. Вперед  >>>  1  2  3  4   8  Комментарии к статье  8 8  Обсудить в чате