По книге Ласло,
"Вычислительная геометрия и компьютерная графика на С++"

Кл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<p.y)));
}

int Point::operator> (Point &p)
{
  return ((x>p.x) || ((x == p.x) && (y > p.y)));
}

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

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

Упорядоченная пара векторов (здесь p₀p₁ и p₀p₂) называется положительно ориентированной, если кратчайший поворот от первого вектора ко второму осуществляется против часовой стрелки. Если наоборот, то эта пара отрицательно ориентирована. Пример положительно определенной пары: (1,0) и (0,1). Отрицательно ориентирована пара (0,1) и (1,0). Ориентация пары векторов a=(x_a,y_a) и b=(x_b,y_b) может быть получена как знак sin(x_ay_b-x_by_a). Более подробно об ориентации читайте в начальном учебнике по линейной алгебре или аналитической геометрии. Выражение x_ay_b-x_by_a равно площади со знаком паралеллограмма с вершинами 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;
}

Относительное положение точки и прямой линии

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

Для определения положения текущей точки относительно отрезка прямой линии p₀p₁, направленного от точки р₀ к точке p₁, используется компонентная функция 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 слева или справа, или она коллинеарна с отрезком p₀p₁. В последнем случае необходимы дополнительные вычисления, ели векторы a=pl-pO и b=р2-p0 имеют противоположное направление, то точка р2 лежит позади направленного отрезка p₀p₁ если вектор а короче вектора b, то точка р2 расположена после отрезка p₀p₁. В противном случае точка р2 сравнивается с точками p0 и р1 для определения, совпадает ли с одной из этих концевых точек или лежит между ними.

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

int Point::classify(Edge &e)
{
  return classify(e.org, e.dest);
}

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

Полярные координаты

Система полярных координат обеспечивает второй способ задания положения точки на плоскости. Полярная ось выходит из точки начала координат 0 и направлена в виде горизонтального луча вправо, как показано рис. 2. Точка а представляется парой чисел (r_a, Theta_a). Принимая точку a за вектор, начинающийся в точке начала координат, число r_a определяет тину вектора, а Theta_a — его полярный угол (угол, образуемый между вектором а и полярной осью и отсчитываемый в направлении вращения против часовой стрелки).

Соответствие между парами чисел (r_a, Theta_a) и точками не является однозначным: множество пар могут представлять одну и ту же точку. Пара (0, Theta) соответствует началу координат для любого значения 0. Более того, пары чисел (r, Theta + 360k) соответствуют одной и той же точке для любого целого числа k.

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

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

Для использования этого выражения в функции 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);
}

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

Класс Vertex (Вершина)

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

Эту схему обеспечивают классы Vertex и Polygon. Полигон хранится в виде циклического списка объектов класса Vertex с двойными связями. Поскольку вершины полигона существуют одновременно как точки на плоскости и узлы в связном списке, класс Vertex формируется на основе класса Point и класса Node. Класс Polygon содержит элемент данных, указывающий на некоторую вершину в связном списке, представляющем полигон. Класс Polygon служит как общедоступный (public) интерфейс для полигонов.

class Node {  //  Узел кольцевого двойного списка
 protected:
  Node *_next;	// связь к последующему узлу
  Node *_prev;	// связь к предшествующему узлу
 public:
  Node (void);
  virtual ~Node (void);
  Node *next(void);
  Node *prev(void);
  Node *insert(Node*);  // вставить узел после текущего
  Node *remove(void);// удалить узел из списка, возвратить его указатель
  void splice(Node*); // слияние/разделение кольцевых списков
};

class Vertex: public Node, public  Point  {
 public:
  Vertex (double x, double y);
  Vertex (Point&);
  Vertex *cw(void);
  Vertex *ccw(void);
  Vertex *neighbor (int rotation);
  Point point (void);
  Vertex *insert (Vertex* );
  Vertex *remove (void);
  void splice (Vertex*);
  Vertex *split (Vertex*);
  friend class Polygon;
}
};

Объект класса Vertex может быть сформирован на основе точки или по ее координатам х и у.

Vertex::Vertex (double x, double у) :
  Point (x, у)
{
}

Vertex::Vertex (Point &p) :
  Point (p)
{
}

Компонентные функции cw и ccw возвращают указатели на последователя и предшественника текущей вершины соответственно.

Vertex *Vertex::cw(void)
{
  return (Vertex*)_next;
}

Vertex *Vertex::ccw(void)
{
  return (Vertex*)_prev;
}

Компонентная функция neighbor сообщает, какой из соседей определен параметром rotation, возвращая одно из значений типа перечисления CLOCKWISE или COUNTER_CLOCKWISE

Vertex *Vertex::neighbor (int rotation)
{
  return ((rotation == CLOCKWISE) ? cw() : ccw());
}

Компонентная функция point возвращает точку на плоскости, в которой находится текущая вершина

Point Vertex::point(void)
{
  return  *((Point*)this);
}

Компонентные функции insert , remove и splice соответствуют своим аналогам, определенным в базовом классе Node.

Vertex *Vertex::insert (Vertex *v)
{
  return (Vertex *) (Node::insert (v));
}

Vertex *Vertex::remove (void)
{
  return (Vertex *) (Node::remove ());
}
void Vertex::splice (Vertex *b)
{
  Node::splice (b);
}

Заметим, что в функциях insert и remove перед выводом производится преобразование возвращаемых значений к типу указатель_на_Vertех. Явное преобразование необходимо здесь потому, что язык C++ не может автоматически преобразовать указатель из базового класса, чтобы указать на объект производного класса. Причина заключается в том, что компилятор языка C++ не может быть уверенным в том, что имеется объект производного класса, на который нужно указать, поскольку объект базового класса не обязательно должен быть частью объекта производного класса (но, с другой стороны, компилятор языка C++ автоматически преобразует указатель на производный класс для указания на объект базового класса, поскольку каждый объект производного класса включает внутри себя объект базового класса).

Последняя компонентная функция Vertex::split будет определена несколько ниже.

Полигон представляется в виде объекта класса Polygon. Класс содержит два элемента данных. Первый из них, _v, указывает на некоторую вершину полигона — текущую позицию окна полигона. Большинство операций с полигонами относятся либо к текущему окну, либо к вершите в окне. Иногда мы будем ссылаться на вершину в окне как на текущую вершину. Во втором элементе данных, _size, хранится размер полигона:

class Polygon {
 private:
  Vertex *_v;
  int _size;
  void resize (void);
 public:
  Polygon (void);
  Polygon (Polygon&);
  Polygon (Vertex*);
  ~Polygon (void);
  Vertex *v(void);
  int size (void);
  Point point (void);
  Edge edge (void);
  Vertex *cw(void);
  Vertex *ccw (void);
  Vertex *neighbor (int rotation);
  Vertex *advance (int rotation);
  Vertex *setV (Vertex*);
  Vertex *insert (Point&);
  void remove (void);
  Polygon * split (Vertex*);
}

Конструкторы и деструкторы

Имеется несколько конструкторов для класса Polygon. Конструктор, не имеющий аргументов, инициирует пустой полигон

Polygon::Polygon(void) : 
  _v(NULL) , _size(0)
{
}

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

Polygon::Polygon (Polygon &р) {
  _size = p._size;
  if (_size == 0)
    _v = NULL;
  else {
    _v = new Vertex (p.point());
    for (int i = 1; i < _size; i++) {
      p.advance(CLOCKWISE);
      _v = _v->insert (new Vertex (p.point()));
    }
    p.advance (CLOCKWISE);
    _v = _v->cw();
  }
}

Третий конструктор инициализирует полигон с кольцевым двухсвязным списком вершин:

Polygon::Polygon (Vertex *v):
  _v(v)
{
  resize();
}

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

void Polygon::resize (void)
{
  if (_v == NULL)
    _size = 0;
  else {
    Vertex *v = _v->cw();
    for (_size = 1; v != _v; ++_size, v = v->cw());
  }
}

Деструктор ~Polygon освобождает вершины текущего полигона, прежде чем удалить сам объект Polygon:

Polygon::~Polygon (void)
{
  if (_v) {
    Vertex *w = _v- >cw();
    while (_v != w) {
      delete w->remove();
      w = _v->cw();
    }
    delete _v;
  }
}

Функции доступа

Следующие несколько компонентных функций позволяют получить некоторые сведения о текущем полигоне. Функция v возвращает текущую вершину данного полигона, а функция size — его размер:

Vertex *Polygon::v(void)
{
  return _v;
}

int Polygon::size(void)
{
  return _size;
}

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

Компонентная функция point возвращает точку на плоскости, которая соответствует текущей вершине. Компонентная функция edge возвращает текущее ребро. Текущее ребро начинается в текущей вершине и заканчивается в следующей после нее вершине:

Point Polygon::point (void)
{
  return _v->point();
}

Edge Polygon::edge(void)
{
  return Edge (point(), _v->cw()->point());
}

Класс Edge (ребро) будет определен в следующем разделе.

Компонентные функции cw и ccw возвращают последователя и предшественника для текущей вершины, оставляя без изменения положение окна. Функция neighbor (сосед) возвращает указатель на последователя или предшественника текущей вершины в зависимости от значения аргумента, с которым она вызывается (CLOCKWISE или COUNTER_CLOCKWISE — по часовой стрелке или против):

Vertex *Polygon::cw(void)
{
  return _v->cw();
}

Vertex *Polygon::ccw(void)
{
  return _v->ccw();
}

Vertex *Polygon::neighbor(int rotation)
{
  return _v->neighbor(rotation);
}

Функции редактирования

Компонентные функции advance и setV перемещают окно на различные вершины. Функция advance (продвинуть) перемещает окно на последователя или предшественника текущей вершины в зависимости от заданного аргумента:

Vertex *Polygon::advance(int rotation)
{
  return _v = _v->neighbor(rotation);
}

Компонентная функция setV перемещает окно на вершину v, указанную в качестве аргумента:

Vertex *Polygon::setV(Vertex *v)
{
  return _v = v;
}

В программе должно быть обеспечено, чтобы вершина - v принадлежала текущему полигону.

Компонентная функция insert вносит новую вершину после текущей и затем перемещает окно на новую вершину:

Vertex *Polygon::insert(Point &p)
{
  if (_size++ == 0)
    _v = new Vertex(p);
  else
    _v = _v->insert(new Vertex(p));
  return _v;
}

Компонентная функция remove удаляет текущую вершину. Окно перемещается на предшественника или остается неопределенным, если полигон становится пустым:

void Polygon::remove(void)
{
  Vertex *v = _v;
  _v = (--_size == 0) ? NULL : _v->ccw();
  delete v->remove();
}

Расщепление полигонов

Расщепление полигонов заключается в делении полигонов на два меньших полигона. Разрезание осуществляется по некоторой хорде. Чтобы разрезать полигон вдоль хорды ab, вначале внесем после вершины а ее дубликат, а дубликат вершины b внесем перед вершиной b (эти дубликаты назовем ар и bр). Затем произведем разделение в вершинах а и bр. Этот процесс проиллюстрирован на рис. 1.

Компонентная функция Polygon::split определена в терминах функции Vertex::split. Эта последняя функция разделяет полигон вдоль хорды, соединяющей текущую вершину (которая играет роль вершины а) с вершиной b. Она возвращает указатель на вершину bр, являющуюся дублем вершины b:

Vertex *Vertex::split(Vertex *b)
{	                    // занесение bр перед вершиной b
  Vertex *bр = b->ccw()->insert(new Vertex(b->point()));
  insert(new Vertex(point()));
                       // занесение ар после текущей вершины
  splice(bр);
  return bр;
}

Компонентная функция Polygon::split разрезает текущий полигон вдоль хорды, соединяющей ее текущую вершину с вершиной b. Она возвращает указатель на новый полигон, окно которого размещено над вершиной bр, являющейся дубликатом вершины b. Положение окна над текущим полигоном не изменяется.

Polygon *Polygon::split (Vertex *b)
{
  Vertex *bp = _v->split(b);
  resize();
  return new Polygon(bр);
}

Компонентная функция Polygon::split должна использоваться с некоторой осторожностью. Если вершина b является последователем текущей вершины _v, то после выполнения операции полигон остается неизменным. Если разрезание производится вдоль диагонали, не являющейся хордой, то один или даже оба результирующих «полигона» могут оказаться взаимно пересекающимися. Если вершины b и _v принадлежат разным полигонам, то операция разделения приводит к соединению двух полигонов по двум совпадающим ребрам, которые соединяют эти две вершины.

Точки, входящие в состав выпуклого полигона

bool pointlnConvexPolygon (Point &s , Polygon &p)
{
  if (p. size() == 1)
    return (s == p.point());
  if (p. size () == 2) {
    int c = s .classify (p. edge ());
    return ( (c==BETWEEN) || (c==ORIGIN) | || (c==DESTINATION) );
  }
  Vertex *org = p.v();
  for (int i = 0; i < p.size(); i++, p.advance(CLOCKWISE))
    if (s.classify (p.edge()) == LEFT) {
      p.setV(org);
      return FALSE;
    }
  return TRUE;
}

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

Определение наименьшей вершины в полигоне

В следующую функцию в качестве аргументов передаются полигон р и функция сравнения cmp и в ней производится поиск наименьшей вершины в полигоне р. Здесь под термином наименьшая вершина подразумевается вершина, которая меньше всех остальных при линейном упорядочении точек в смысле, задаваемом функцией cmp. Функция leastVertex перемещает окно полигона р на эту наименьшую вершину и возвращает указатель на эту вершину:

Vertex *leastVertex( Polygon &p, int (*cmp)(Point*,Point*) )
{
  Vertex *bestV = p.v();
  p.advance(CLOCKWISE);
  for (int  i=1; i < p.size(); p.advance(CLOCKWISE), i++)
    if ((*cmp)(p.v(),bestV) < 0)
      bestV = p.v();
  p.setV(bestV);
  return bestV;
}

Например, для обнаружения самой левой вершины следует обратиться к функции leastVertex со следующей функцией сравнения:

int leftToRightCmp (Point *a, Point *b)
{
  if (*a < *b) return -1;
  if (*a > *b) return 1;
  return 0;
}

Для нахождения самой правой вершины можно использовать такую функцию сравнения:

int rightToLeftCmp(Point *a, Point *b)
{
  return leftToRightCmp(b, a);
}

Множество геометрических алгоритмов затрагивает прямые линии в той или иной форме. Отрезок прямой линии p₀p₁ состоит из двух концевых точек р₀ и p₁ вместе с точками, лежащими между ними. Когда важен порядок следования точек р₀ и p₁, то мы говорим о направленном отрезке прямой линии р₀р₁. Концевая точка р₀ является началом направленного отрезка прямой линии, а точка p₁ — его концом. Обычно направленный отрезок прямой линии будем называть ребром, если он представляет собой сторону некоторого полигона. Ребро направлено таким образом, что внутренняя часть полигона располагается всегда справа от него. Бесконечная (направленная) прямая линия определяется двумя точками и направлена от первой точки ко второй. Луч является полубесконечной прямой линией, начинающейся в точке начала и проходящей через вторую точку.

Класс Edge (Ребро, любые линии)

class Edge {
 public:
  Point org;
  Point dest;
  Edge (Point &_org, Point &_dest);
  Edge (void);
  Edge &rot (void);
  Edge &flip (void);
  Point point (double);
  int intersect (Edge&, double&);
  int cross (Edge&, double&);
  bool isVertical(void);
  double slope(void);
  double у(double);
};

Концевые точки начала и конца хранятся в элементах данных org и dest соответственно. Эти элементы инициализируются конструктором Edge:

Edge::Edge (Point &_org, Point &_dest) :
  org (_org), dest (_dest)
{
}

Полезно также иметь конструктор для класса Edge, не требующий аргументов:

Edge::Edge (void) :
  org (Point (0,0)), dest (Point (1,0))
{
}

Поворот ребер

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

На рис. 3 показано, как путем поворота ребра ab формируется ребро ca. Если вектор b - а = (х, у), то вектор n, перпендикулярный вектору b - а, определяется как n = (у, -х). Средняя точка m между точками а и b определяется как m = (а + b)/2. Тогда точки с и d определяются как с = m - n/2 и d = m + n/2. Поворот реализуется компонентной функцией rot следующим образом:

Edge &Edge::rot(void)
{
  Point m = 0.5 * (org + dest);
  Point v = dest - org;
  Point n(v.у, -v.x);
  org = m - 0.5 * n;
  dest = m + 0.5 * n;
  return *this;
}

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

Edge &Edge::flip(void)
{
  return rot().rot();
}

При таком определении компонентной функции flip первое обращение к функции rot (слева от оператора доступа к элементу) поворачивает текущее ребро, а затем второе обращение поворачивает его еще раз.

Определение точки пересечения двух прямых линий

Бесконечная прямая линия ab, проходящая через две точки а и b, может быть записана в параметрической форме как

Компонентные функции Edge::intersect и Edge::point предусмотрены для совместной работы при поиске точки пересечения двух бесконечных прямых линий е и f. Если е и f являются объектами класса Edge, то фрагмент программы

double t;
Point p;
if (e.intersect(f,t) = SKEW)
  p = e.point(t)

определяет t как параметрическое значение (вдоль прямой линии е) точки, в которой пересекаются прямые линии е и f и затем эта точка р становится текущей точкой. Функция intersect возвращает значения типа перечисления: SKEW (наклон), если прямые линии пересекаются в некоторой точке, COLLINEAR, если прямые линии коллинеарны, или PARALLEL, если они параллельны. Компонентная функция point обрабатывает параметрическое значение t и возвращает соответствующую точку. Задача решается обращением к двум координатным функциям вместо обращения к одной общей функции, поскольку иногда нам достаточно определить параметрическое значение точки пересечения, а не саму точку пересечения.

Реализация компонентной функции point очень проста — значение параметра t подставляется в параметрическое уравнение для этой линии:

Point Edge::point(double t)
{
  return Point(org + t * (dest - org));
}

Реализация компонентной функции intersect основана на записи скалярного произведения а * b для двух векторов а = (х_а, у_а) и b = (х_b, у_b), которое определяется как а * b = х_aх_b + y_ay_b. Скалярное произведение имеет несколько важных свойств, включая основные:

1. Если a, b и с — векторы, то a * b = b * а и
2. а * (b + с) = а * b + а * с = (b + с) * а.
3. Если s — скаляр, то (sa) * b = s(a * b) и a * (sb) = s(a * b).
4. Если а — нулевой вектор, то a * a = 0, в противном случае a * a > 0.
5. ||a|| = а * а.

На основании этих основных свойств можно получить очень важное свойство, на котором основан целый ряд операций с прямыми линиями: два вектора а и b перпендикулярны, если, и только если их скалярное произведение равно нулю a * b = 0. Вообще говоря, имеет место следующая теорема:

Пусть a и b - векторы, Theta - угол между ними. Тогда

Теорема о скалярном произведении может быть использована для нахождения точки пересечения двух прямых линий ab и cd. Если прямая линия ab описывается уравнением P(t) = а + t(b - а), то будем искать значение t такое, что прямые линии аb и cd пересекаются в точке P(t). Поскольку вектор P(t)-с должен совпадать с прямой линией cd, то и вектор P(t)-с и прямая линия cd должны быть перпендикулярны одному и тому же вектору n. Следовательно, на основании теоремы о скалярном произведении нам необходимо решить относительно t уравнение

Поскольку P(t) = а + t(b - а), уравнение (2) можно переписать в виде

Уравнение (3) удовлетворяется, если и только если бесконечные прямые линии аb и cd не параллельны и они пересекаются в единственной точке. Если две прямые линии параллельны или совпадают, то этот факт соответствует выполнению условия n * (b - а) = 0, поскольку оба вектора (b - а) и (d - с) перпендикулярны одному и тому же вектору п. В результате получаем следующую реализацию компонентной функции intersect:

enum { COLLINEAR, PARALLEL, SKEW, SKEW_CROSS, SKEW_NO_CROSS };
int Edge::intersect(Edge &e, double &t)
{
  Point a = org;
  Point b = dest;
  Point с = e.org;
  Point d = e.dest;
  Point n = Point((d-c).y, (c-d).x);
  double denom = dotProduct(n, b-a);
  if (denom ==0.0) {
    int aclass = org.classify(e);
    if ((aclass==LEFT) || (aclass==RIGHT))
      return PARALLEL;
    else return COLLINEAR;
  }
  double num = dotProduct(n, a-c);
  t = -num / denom;
  return SKEW;
}

Реализация функции dotProduct (скалярное произведение) очень проста:

double dotProduct(Point &p, Point &q)
{
  return (p.x * q.x + p.у * q.y);
}

Компонентная функция Edge::cross возвращает значение SKEW_CROSS (наклонены, и пересекаются), если и только если текущий отрезок прямой линии пересекает отрезок прямой линии е. Если отрезки прямой линии пересекаются, то возвращается значение параметра t вдоль этого отрезка прямой линии, соответствующее точке пересечения. В противном случае функция возвращает одно из следующих подходящих значений COLLINEAR (коллинеарны) , PARALLEL (параллельны) или SKEW_NO_CROSS (наклонены, но без пересечения).

int Edge::cross(Edge &e, double &t)
{
  double s;
  int crossType = e.intersect(*this, s);
  if ((crossType==COLLINEAR) || (crossType==PARALLEL))
    return crossType;
  if ((s < 0.0) || (s > 1.0))
    return SKEW_NO_CROSS;
  intersect(e, t);
  if ((0.0 <= t) && (t <= 1.0))
    return SKEW_CROSS;
  else
    return SKEW_NO_CROSS;
}

Расстояние от точки до прямой линии

Определение функции Point::distance иллюстрирует некоторые иа только что описанных свойств. В эту компонентную функцию класса Point передается ребро е и возвращается значение расстояния от текущей точка до ребра е со знаком. Здесь под термином расстояние от точки р до ребра е понимается минимальное расстояние от точки р до некоторой точки на бесконечной прямой линии, определяемой ребром е. Расстояние со знакол будет положительным, если точка р лежит справа от ребра е, отрицательным, если точка р лежит слева от ребра е, либо нулевым, если точка принадлежит прямой линии.

Компонентная функция distance определяется следующим образом:

double Point::distance(Edge &e)
{
  Edge ab = e;
  ab.flip().rot();             // поворот ab на 90 градусов
                               // против часовой стрелки
  Point n(ab.dest -  ab.org);
                               // n = вектор, перпендикулярный ребру е
  n = (1.0 / n.length()) * n;
                               // нормализация вектора n
  Edge f(*this, *this + n);
                              // ребро f = n позиционируется 
                              // на текущей точке  
  double t;                   // t = расстоянию со знаком
  f.intersect(e, t);          // вдоль вектора f до точки,
                              // в которой ребро f пересекает ребро е
  return t;
}

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

Дополнительные утилиты

Последние три компонентные функции класса Edge введены для удобства. Компонентная функция isVertical возвращает значение TRUE (истина) только в том случае, если текущее ребро вертикально:

bool Edge::isVertical(void)
{
  return (org.x == dest.x);
}

Компонентная функция slope возвращает величину наклона текущего ребра или значение DBL_MAX, если текущее ребро вертикально:

double Edge::slope(void)
{
  if (org.x != dest.x)
    return (dest.y - org.y) / (dest.x - org.x);
  return DBL MAX;
}

Для компонентной функции у задается значение х и она возвращает значение у, соответствующее точке (х, у) на текущей бесконечной прямой линии. Функция действует только в том случае, если текущее ребро не вертикально.

double Edge::у(double x)
{
  return slope() * (х - org.x) + org.y;
}