5.5. Абстрактные классы

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

virtual тип_возвр_значения имя(параметры) = 0;

Например,

      Class Figure

            {

                  int color;

            public:

                  virtual void show();

            };

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

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

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

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

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

функцию. Будем рассматривать следующую область:

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

· многоугольник, заданный списком своих вершин (класс Polygon);

· выпуклый многоугольник (класс CPolygon);

· звездчатый многоугольник (класс SPolygon).

Эти классы составляют иерархию, приведенную на рис. 5.1.

Определим область как абстрактный класс:

class Domain

      {

      protected:

      // Защищённые элементы класса

            int color;  // цвет области

            int n;      // количество сторон

      public:

      // Общедоступные элементы класса

            Domain(int c = WHITE): color(c) {} // Конструктор

            // Определение принадлежности точки области

            virtual int isin(Point p) = 0;

            // Функция вывода области на экран

            void show(double xmin, double ymin, double xmax, double ymax);

      };

Класс Point определим позже.

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

Функция isin(Point p) будет возвращать 1, если и только если координаты точки p удовлетворяют этим неравенствам.

class Convex: virtual public Domain

      {

      protected:

      // Защищённые элементы класса

            double *a, *b, *c;      // Коэффициенты ограничивающих

                                   // прямых ax+by+c=0

      public:

      // Общедоступные элементы класса

            Convex() { n = 0; }     // Конструктор по умолчанию

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

            Convex(double *av,double *bv,double *cv,int nv,Point p,int cl);

            // Переопределённая функция определения принадлежности

            // точки области

            int isin(Point p);

};

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

Convex::Convex(double *av, double *bv, double *cv, int nv,

                  Point p,int cl):Domain(cl)

      {

      // Задается некоторая внутренняя точка p многоугольника

      int i;

  n = nv;

      // Выделяем память под коэффициенты

      a = new double[n];

      b = new double[n];

      c = new double[n];

      for (i = 0; i < nv; i++)

            {

            if (av[i] * p.x + bv[i] * p.y + cv[i] <= 0)    // Если вектор

                  {                            // нормали направлен наружу

                  a[i] = av[i]; b[i] = bv[i]; c[i] = cv[i];

                  }

            else  // Иначе изменяем направление нормали на противоположное

                  {

                  a[i] = -av[i]; b[i] = -bv[i]; c[i] = -cv[i];

                  }

            }

      }

// Переопределённая функция определения принадлежности точки области

int Convex::isin(Point p)

      {

      int i;

      // Перебор всех ограничивающих прямых

      for (i = 0; i < n;i++)

            if (a[i] * p.x + b[i] * p.y + c[i] > 0) return 0; // Точка

                                               // расположена вне области

      return 1;   // Если точка расположена с противоположной

//стороны от нормали

      }

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

Класс Polygon определим как последовательность вершин многоугольника:

class Polygon: virtual public Domain

      {

      protected:

      // Защищённые элементы класса

            Point *p;   // Список вершин многоугольника

      public:

      // Общедоступные элементы класса

            Polygon() {n = 0;}      // Конструктор по умолчанию

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

            Polygon(double *x, double *y, int num, int cl);

            // Переопределённая функция определения принадлежности

            // точки области

            int isin(Point t);

      };

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

В последнем случае, если t находится слева от , то , а если справа, то . Индексом  точки t относительно многоугольника M называется число . Имеет место следующее утверждение: индекс равен 0 тогда и только тогда, когда точка t лежит вне многоугольника М.

Рассмотрим, например, точку t и многоугольник, изображенные ниже на рис. 5.2. Точки первой четверти имеют код code(p) = 0, второй –1, третьей – 2, четвертой – 3.

Получаем m0 = 0, m1 = 1, m2 = -2, m3 = 2, m4 = 1, m5 = 1, m6 = 1. Индекс равен . Следовательно, точка t – внутренняя, по отношению к многоугольнику.

Предполагая, что класс Point имеет составную функцию code(Point q), возвращающую номер четверти, которой принадлежит точка q, если взять данную точку в качестве начала системы координат, приведём подпрограмму теста на принадлежность точки многоугольнику:

int Polygon::isin(Point t)

      {

      int i, ind = 0;

      Point q = p[n-1];

      // Перебор вершин полигона для вычисления индекса полигона

      for (i = 0; i < n; i++)

            {

            if (t.code(q) == t.code(p[i])) ;

            else if ((t.code(p[i]) — t.code(q) — 1) % 4 == 0) ind++;

                  else if ((t.code(p[i]) — t.code(q) + 1) % 4 == 0) ind—;

                        else if ((p[i] — q) * (t — q) > 0) ind += 2;

                             else ind -= 2;

            q = p[i];

            }

      if (ind == 0) return 0;

      return 1;

      }

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

Подпрограмму show() можно реализовать с помощью функции fillpoly():

Void Polygon :: show()

      {

      int coord = new int[2*n];

      setfillstyle (SOLID_FILL, color);

      fillpoly(n, coord);

      }

Определим класс звездчатого многоугольника. Напомним, что многоугольник М называется звездчатым, если существует такая точка r, что для каждой точки p  M весь отрезок, соединяющий точки р и r, содержится в М. Точки r, обладающие этим свойством, называются ядерными.

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

class SPolygon: public Polygon

      {

      protected:

      // Защищённые элементы класса

            Point pC;   // Центр тяжести

      public:

      // Общедоступные элементы класса

            SPolygon() {}     // Конструктор по умолчанию

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

            SPolygon(double *x, double *y, int m, int cl);

      };

Определим звездчатый полигон как производный от класса Polygon. Конструктор строит звездчатый полигон из набора точек  с помощью присоединения по одной точке. Вначале звездчатый полигон состоит из единственной точки . Затем в цикле по i = 1, 2, …, n-1 добавляются точки Si.

Точки упорядочиваются в порядке возрастания угла SiS0. Затем точка S0 удаляется из списка вершин, и точки последовательно соединяются, как это показано на рис. 5.3. Лучи соединяют вершину S0 с вершинами Si.

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

Пусть М – выпуклый многоугольник, р – произвольная внешняя точка. Сторона многоугольника

называется видимой из точки р, если существует такая точка q, принадлежащая этой стороне, что отрезок, соединяющий ее с точкой р, не имеет других общих точек со стороной, кроме точки q. На рис. 5.4 видимыми будут стороны S0S1, S1S2 и S5S0. В частности, для стороны S5S0 такой точкой q будет S0.         

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

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

Ниже приведен текст программы, в которой реализована иерархия классов, приведенная на рис. 5.1.                                                      

#include <graphics.h>

#include <conio.h>

#include <math.h>

#include <stdlib.h>

#define PI 3.14159

struct Point          // класс точки

{

   double x,y;        // координаты точки

   int code(Point q); // код четверти, в которой лежит точка q

   double operator*(Point q);// векторное произведение

   Point operator-(Point q); // разность векторов

};

int Point::code(Point q) // код четверти, в которой лежит точка q

{                 // начало координат находится в точке (x,y)

   if (q.x-x>=0 && q.y-y>=0) return 0;

   if (q.x-x< 0 && q.y-y>=0) return 1;

   if (q.x-x>=0 && q.y-y< 0) return 3;

   if (q.x-x< 0 && q.y-y< 0) return 2;

}

double Point::operator*(Point q)

{

   return x*q.y-y*q.x; // векторное произведение

}

Point Point::operator-(Point q) // разность векторов

{

   Point t; t.x=x-q.x; t.y=y-q.y; return t;

}

int operator <(Point p, Point q)

{

Point t;             // сравнение углов радиус-векторов p и q

   t.x=0; t.y=0;     // коды четвертей вычисляются относительно (0,0)

   if(t.code(p)<t.code(q)) return 1;

   if(t.code(p)>t.code(q)) return 0;

    return (p*q>0); // вращение от p к q направлено против часовой стрелки

}

int intersect(Point p,Point p1, Point p2)

{                   // тест на пересечение луча и отрезка

   if (p1.y==p2.y) return 0;

   if ((p1.y<p2.y?p2.y:p1.y)<=p.y) return 0;

   if ((p1.y<p2.y?p1.y:p2.y)>p.y) return 0;

   if (p2.y-p1.y>0) return

                    ((p.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p.y-p1.y) > 0);

   else return

                    ((p.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p.y-p1.y) < 0);

}

class Domain              // абстрактный класс области

{

   protected:

             int color;   // цвет области

             int n;       // количество сторон

   public:

     virtual int isin(Point p)=0; // функция принадлежности

  Domain(int c=15): color(c){} // конструктор

     void show(double xmin, double ymin, double xmax, double ymax);

                          // функция вывода области

};

void Domain::show(double xmin, double ymin, double xmax, double ymax)

{

     int ix, iy; Point q;

     for (iy=0; iy<=getmaxy(); iy++)

      for (ix=0; ix<=getmaxx(); ix++)

        {

          q.x = xmin+ix*(xmax-xmin)/(getmaxx()+1);

          q.y = ymin+(getmaxy()+1-iy)*(ymax-ymin)/(getmaxy()+1);

          if (isin(q)) putpixel(ix,iy, color);

        }

}

class Convex: virtual public Domain

{

   protected:

     double *a, *b, *c; // коэффициенты ограничивающих прямых ax+by+c=0

   public:

 Convex(){n=0;}

 Convex(double *av, double *bv, double *cv, int nv, Point p,int cl);

   int isin(Point p); // функция принадлежности переопределена

};

Convex::Convex(double *av, double *bv, double *cv, int nv,

           Point p,int cl):Domain(cl)

{          // задается некоторая внутренняя точка p многоугольника

   int i; n = nv;

   a = new double[n]; b = new double[n]; c = new double[n];

   for (i=0; i<nv; i++)

   {

      if (av[i]*p.x+bv[i]*p.y+cv[i]<=0) // если вектор нормали

      {                                 // направлен наружу

        a[i]=av[i]; b[i]=bv[i]; c[i]=cv[i];

      } else   // иначе изменяем направление нормали на противоположное

        {

          a[i]=-av[i]; b[i]=-bv[i]; c[i]=-cv[i];

         }

   }

}

int Convex::isin(Point p)

{

   int i;

   for (i=0; i<n;i++)

    if (a[i]*p.x+b[i]*p.y+ c[i] > 0) return 0; // точка лежит вне области

   return 1; // если точка лежит с противоположной стороны от нормали

}

class Polygon: virtual public Domain

{

   protected:

     Point *p;

   public:

     Polygon(){n=0;}

     Polygon(double *x, double *y, int num, int cl);

     int isin(Point t);

};

Polygon::Polygon(double *x, double *y, int num, int cl):Domain(cl)

{

   int i; n = num; p= new Point [num];

   for (i=0; i<n; i++)

   {

     p[i].x=x[i]; p[i].y=y[i];

   }

}

/*

int Polygon::isin(Point t)  // тест на принадлежность методом углов

{

   int i, ind=0;

   Point q = p[n-1];

   for (i=0; i<n; i++)

   {

      if (t.code(q)==t.code(p[i]));

       else if ((t.code(p[i])-t.code(q)-1)%4==0) ind++;

           else if ((t.code(p[i])-t.code(q)+1)%4==0) ind—;

                else if ((p[i]-q)*(t-q)>0) ind+=2;

                     else ind-=2;

      q = p[i];

   }

   ind = ind/4;

   if (ind==0) return 0; else return 1;

} */

int Polygon::isin(Point t)

{

   int i, parity=0;

   for (i=0; i<n; i++)

       if (intersect(t, p[i],p[(i+1)%n]))

          parity = 1-parity; return parity;

}

class SPolygon: public Polygon

{

   protected:

     Point pC;

   public:

     SPolygon(){} // конструктор по умолчанию

     SPolygon(double *x, double *y, int m, int cl);

};

SPolygon::SPolygon(double *x, double *y, int m, int cl):Domain(cl)

{

   int i,j;

   Point t;

   p= new Point [m]; n=m;

   pC.x=0; pC.y=0;

   for(i=0;i<m;i++)

   {

     pC.x+=x[i]; pC.y+=y[i];

   }

     pC.x= pC.x/m; pC.y= pC.y/m;

   for(i=0;i<m;i++)

   {

     p[i].x=x[i]; p[i].y=y[i];

   }

// Сортируем точки по возрастанию угла вокруг центра

// тяжести методом вставок

   for(i=1; i<m; i++)

   {

     t = p[i];

     for (j=i-1; (j>=0) && ((t-pC)<(p[j]-pC)); j—)

       p[j+1] = p[j];

     p[j+1]=t;

   }

}

class CPolygon: public SPolygon, public Convex

{

   public:

     int isin(Point r){return Polygon::isin(r);};

     void Insert(Point t)

     {

             int i;  int j0, j1, j;

             int *del = new int [n];

             Point *q= new Point [n+1];

             if (isin(t)) return;

             j0=j1=0;

             for (i=0; i<n; i++)

             {

                   if ((t-p[i])*(p[(i+1)%n]-p[i])>=0) del[i]=1;

                   else del[i]=0;

             }

             for (i=0;i<n;i++)

                   if (del[i]==1&& del[(i+1)%n]==0) break;

                   j=0; i=(i+1)%n;

                   while(del[i]==0)

                   {

                         q[j++]=p[i];

                         i=(i+1)%n;

                   } q[j]=p[i];

                     q[j+1] = t; delete [] p;

                     p=new Point [j+2]; n=j+2;

                     for (i=0; i<n; i++)

                     p[i]=q[i];

                     delete []q;

  }

        CPolygon(double *x, double *y, int m, int cl);

};

CPolygon::CPolygon(double *x, double *y, int m, int cl):Domain(cl)

{   // выпуклая оболочка методом Дейкстры

int i; Point t; p= new Point [3]; n=3;

for (i=0; i<3; i++)

{

   p[i].x=x[i]; p[i].y=y[i];

}

if ((p[1]-p[0])*(p[2]-p[1])<0)

{

       t=p[1]; p[1]=p[2]; p[2]=t;

}

for(i=3; i<m; i++)

{

      t.x=x[i]; t.y=y[i];

   Insert (t);

}

}

/*

CPolygon::CPolygon(double *x, double *y, int m, int cl):Domain(cl)

{  // выпуклая оболочка методом заворачивания подарка

  int i, j0, j1, j=0, k=0; Point t, r, *q= new Point [m];

  for (i=0; i<m; i++)

  {

   q[i].x=x[i]; q[i].y=y[i];

   if (x[i]>x[j]) j=i; // находим точку с максимальной x-координатой

  }

  j0=j; // начало стороны многоугольника

  j1=(j+1)%m;

  while(j1%m!=j0)

  {

   p[k++]=q[j]; r=q[j]; t= q[(j+1)%m]; j1=(j+1)%m;

   for(i=(j+1)%m; i!=j; i=(i+1)%m)

     if (q[i]-r< t-r)

     {

      t= q[i]; j1=i;

     }

   j=j1;

  } p[k++]=q[j1%m];

}

*/

int main()

{

// определяем область, ограниченную прямыми x=200, y=200, x=-200, y=-200

double a[4]={1,0,1,0}, b[4]={0,1,0,1}, c[4]={200,200,-200,-200};

double rad=150, x[10], y[10];//радиус окружности и вершины пятиугольника

int i;

Point r={0,0}; // внутренняя точка для области Convex

Convex dom(a,b,c,4,r,LIGHTBLUE); // область Convex является квадратом

for(i=0;i<5;i++)

{

   // вершины большого пятиугольника

x[i] = rad*cos(2*PI*i/5); y[i] = rad*sin(2*PI*i/5);

   // вершины маленького пятиугольника

x[i+5] = rad*cos(2*PI*i/5+PI/5)/2;

    y[i+5] = rad*sin(2*PI*i/5+PI/5)/2;

}

randomize();

for(i=0;i<10;i++)

   x[i]+=  random(100)-200;

Polygon dom1(x,y,10,GREEN);         // построение многоугольника

for(i=0;i<10;i++)

   x[i]+= 300;

CPolygon dom2(x,y,10,BLACK);        // построение выпуклой облочки

SPolygon dom3(x,y,10,LIGHTRED);          // построение звездчатого полигона

int gm, gd=DETECT;

initgraph(&gd, &gm, "..\bgi");     // инициализация графики

   setfillstyle(SOLID_FILL, WHITE); // фон — белый

   bar(0, 0, getmaxx(), getmaxy()); // закраска экрана

dom.show(-300,-300,300,300);     // вывод квадрата

dom1.show(-300,-300,300,300);    // вывод многоугольника

dom2.show(-300,-300,300,300);    // вывод выпуклой облолочки

dom3.show(-300,-300,300,300);    // вывод звездчатого полигона

getch(); closegraph();

       return 0;

}

В главной программе сначала экран будет окрашен в белый цвет. Затем  выводится голубой квадрат, соответствующий объекту класса Convex. Затем будет выведен многоугольник, построенный по десяти точкам, полученным прибавлением случайных чисел к координатам  точек двух пятиугольников, один из которых имеет радиус 150, а другой – радиус 75. Затем выводится выпуклая оболочка этих десяти точек и звездчатый многоугольник, построенный по тем же самым десяти точкам.