Первая дробь (числитель равен 10, знаменатель равен 20): 1/2
Вторая дробь (числитель равен -15,знаменатель равен 10): -3/2
Виртуальные классы
#include <graphics.h>
#include <math.h>
#include <conio.h>
class four // четырехугольник
{
protected:
float x[4], y[4]; // координаты вершин
public:
four(){}
four(float *ix, float *iy) // конструктор
{
int i;
for(i=0; i<4; i++)
{
x[i] = ix[i]; y[i] = iy[i];
}
}
~four() {delete x; delete y;} //деструктор
void show(); //вывод четырёхугольника на экран
};
class rect: public virtual four // прямоугольник
{
protected:
int xleft, xright, ytop, ybottom;
public:
rect(int x1, int y1, int x2, int y2):
xleft(x1), ytop(y1), xright(x2), ybottom(y2) // конструктор
{
x[0] = x1; y[0] = y1;
x[1] = x1; y[1] = y2;
x[2] = x2; y[2] = y2;
x[3] = x2; y[3] = y1;
}
};
//класс ромба
class romb: public virtual four
{
protected:
float xc, yc, alpha, a, b;
public:
romb(float x1, float y, float ugol, float d1, float d2)
{
xc = x1; yc = y; alpha = ugol; a = d1; b = d2;
x[0] = xc + (a/2)*cos(alpha);
x[0] = yc + (a/2)*sin(alpha);
x[1] = xc - (b/2)*sin(alpha);
x[1] = yc + (b/2)*cos(alpha);
x[2] = xc - (a/2)*cos(alpha);
x[2] = yc - (a/2)*sin(alpha);
x[3] = xc + (b/2)*sin(alpha);
x[3] = yc - (b/2)*cos(alpha);
}
};
// стороны квадрата параллельны осям координат
class square: public rect, public romb
{
int xcenter, ycenter; // центр квадрата
int size; // сторона квадрата
public:
square(int x0, int y0, int s): xcenter(x0+s/2), ycenter(y0+s/2),
size(s), rect(x0 - s/2, y0 - s/2, x0 + s/2, y0 + s/2),
romb(x0, y0, 3.14159/4, s, s) {show();}
};
void four:: show() // вывод четырехугольника
{
int i;
moveto (x[3], y[3]);
for(i=0; i<4; i++)
lineto(x[i], y[i]);
};
void main()
{
int gd = DETECT, gm;
initgraph (&gd, &gm,"c:\\prog\\bc31\\bgi");
square q(320, 240, 100);.
getch(); //ожидание нажатия любой клавиши
}
В результате работы программы на экран будет выведен квадрат, сторона которого равна 100, а центр квадрата совпадает с центром экрана.
#include <stdio.h> //стандартная библиотека ввода-вывода
//классы реализованы посредством конструкторов и информационных полей
class V
{
public:
int a,b,c;
V(): c(3){};
V(int p): a(p){};
};
class A: virtual public V
{
public:
A():V(3) {a=1;}
};
class B: virtual public V
{
public:
B() {b=2;}
};
class C: public A,B
{
public:
//функция вывода
void out(){printf("a=%d b=%d c=%d\n",a,b,c);}
};
int main()
{
C ob1;
ob1.out();
return 0;
}
Результаты работы программы
a=1 b=2 c=3
Пример. Рассмотрим иерархию классов, приведённую на рис. 4.5. Этот пример, как и предыдущий, иллюстрирует порядок вызова конструкторов виртуальных классов, но для более сложного случая.
Ниже приведён текст программы.
#include <stdio.h> //стандартная библиотека ввода-вывода
class V1 //первый класс
{
friend class D; //дружественный класс
friend class B; //дружественный класс
int fix1;
public:
V1(int val): fix1(val){}; //конструктор
V1(): fix1(10){};
};
class V2 //второй класс
{
friend class D; //дружественный класс
int fix2;
public:
V2(): fix2(20){}; //конструктор
V2(int p): fix2(p){};
};
//схема наследования
class B: virtual public V1, virtual public V2 {};
class C: virtual public V1, virtual public V2 {};
class D: public B,C {
public:
D(): V1(30){};
D(int p): V2(p){};
//функция вывода
void out(){printf("fix1=%d fix2=%d \n",fix1,fix2);}
};
int main()
{
D ob1; D ob2(100);
ob1.out();
ob2.out();
return 0;
}
При создании объекта ob1 будут вызваны конструкторы V1(30) и V2(), которые установят fix1 = 30 и fix2 = 20. При создании объекта ob2 будет вызван конструктор V1() без параметра, а затем – конструктор V2(100). Они установят fix1 = 10 и fix2 = 100.
Результаты работы программы
fix1=30 fix2=20
fix1=10 fix2=100
Пример. Рассмотрим иерархию классов, приведённую на рис. 4.6. Сначала вызываются конструкторы V1,V2,V3, а затем – B,C,D.
Ниже приведён текст программы, иллюстрирующей вышеприведённую иерархию.
#include <stdio.h> //стандартная библиотека ввода-вывода
//построения иерархии
class V1 //класс V1
{
friend class D; //дружественный класс
int fix1;
public:
V1(int val): fix1(val){};
V1(): fix1(10){};
};
class V2 //класс V2
{
friend class D; //дружественный класс
int fix2;
public:
V2(): fix2(20){};
};
class V3 //класс V3
{
int fix3;
friend D;
public:
V3(): fix3(40){};
V3(int p): fix3(p){};
};
//схема наследования
class A: virtual public V1 {};
class B: virtual public V1 {};
class C: virtual public V2, virtual public V3 {};
class D: public B,C {
public:
D(): V1(30){};
D(int p): V3(p){};
//функция вывода
void out(){printf("fix1=%d fix2=%d fix3=%d\n",fix1,fix2,fix3);}
};
int main()
{
D ob1; D ob2(100);
ob1.out();
ob2.out();
return 0;
}
Результаты работы программы
fix1=30 fix2=20 fix3=40
fix1=10 fix2=20 fix3=100
виртуальные функции
Переопределение составной функции
Например, рассмотрим класс «фрукты» и производные от него – «яблоки» и «апельсины».
#include <iostream.h>
#include <conio.h>
// Класс фрукты
class fruit
{
public:
void show()
{
cout << "фрукты"<< endl;
}
};
// Класс яблоки
class apple
{
public:
void show()
{
cout << "яблоки" << endl;
}
};
// Класс апельсины
class orange
{
public:
void show()
{
cout << "апельсины" << endl;
}
};
void main()
{
clrscr(); // Очистка экрана
// Создаём объекты
fruit *a = (fruit *)new apple, *b = (fruit *)new orange;
a -> show(); b -> show(); // Выводим сообщения
getch(); // Ожидание нажатия клавиши
}
Организация списка объектов различного типа
// Класс точки
class Point
{
// Собственные элементы
friend MPoint; // Класс MPoint будет дружественным
protected:
// Защищённые элементы
int x,y; // Координаты
int itype; // Тип
Point *next; // Указатель на следующий элемент в списке
public:
// Общедоступные элементы
Point(int a,int b):x(a), y(b), itype(0) {} // Конструктор
virtual void get()
{
// Вывод координат точки
cout << "Point(" << x << ',' << y << ")\n";
}
virtual int type() // Виртуальная функция возвращения типа
{
return itype;
}
};
// Класс линии (производный от класса точки)
class Line: public Point
{
// Собственные элементы
friend MPoint; // Класс MPoint будет дружественным
int x2,y2; // Координаты второго конца линии
Point *next; // Указатель на следующий элемент в списке
public:
// Общедоступные элементы
// Конструктор
Line(int a,int b,int a2,int b2):Point(a,b), x2(a2), y2(b2) {}
virtual void get()
{
// Вывод координат линии
cout << "Line(" << x << ',' << y << ")(";
cout << x2 << ',' << y2 << ")\n";
}
};
// Класс списка
class MPoint
{
// Собственные элементы
Point *p; // Указатель на голову списка
public:
// Общедоступные элементы
MPoint() { p = NULL; } // Конструктор
void insert(Point z); // Добавление точки в список
void insert(Line t); // Добавление линии в список
void display(); // Вывод содержимого списка
};
Для того чтобы сделать доступными поля классов Point и Line, объявим класс Mpoint дружественным для этих классов. После добавления тестирующей главной программы получим окончательный текст программы.
#include <conio.h>
#include <iostream.h>
class MPoint;
// Класс точки
class Point
{
// Собственные элементы
friend MPoint; // Класс MPoint будет дружественным
protected:
// Защищённые элементы
int x,y; // Координаты
int itype; // Тип
Point *next; // Указатель на следующий элемент в списке
public:
// Общедоступные элементы
Point(int a,int b):x(a), y(b), itype(0) {} // Конструктор
virtual void get()
{
// Вывод координат точки
cout << "Point(" << x << ',' << y << ")\n";
}
virtual int type() // Виртуальная функция возвращения типа
{
return itype;
}
};
// Класс линии (производный от класса точки)
class Line: public Point
{
// Собственные элементы
friend MPoint; // Класс MPoint будет дружественным
int x2,y2; // Координаты второго конца линии
Point *next; // Указатель на следующий элемент в списке
public:
// Общедоступные элементы
// Конструктор
Line(int a,int b,int a2,int b2):Point(a,b), x2(a2), y2(b2) {}
virtual void get()
{
// Вывод координат линии
cout << "Line(" << x << ',' << y << ")(";
cout << x2 << ',' << y2 << ")\n";
}
};
// Класс списка
class MPoint
{
// Собственные элементы
Point *p; // Указатель на голову списка
public:
// Общедоступные элементы
MPoint() { p = NULL; } // Конструктор
void insert(Point z); // Добавление точки в список
void insert(Line t); // Добавление линии в список
void display(); // Вывод содержимого списка
};
// Вывод содержимого списка
void MPoint::display()
{
Point *q = p; // Создаём указатель и устанавливаем его
// на голову списка
while(q) // Пока не дойдём до конца списка
{
q->get(); // Вывод элемента списка
q=q->next; // Переход к следующему элементу
}
}
// Добавление точки в список
void MPoint::insert(Point z)
{
if(!p) // Если список пустой
{
p = new Point(z.x, z.y); // Создаём новый элемент
p->next = NULL; // Следующего элемента пока нет
return; // Выход из функции
}
// Если список не пустой
Point *q = p; // Создаём указатель и устанавливаем его
// на голову списка
// Идём до конца списка
while(q->next)
q = q->next; // Переход к следующему элементу списка
q->next = new Point(z.x,z.y); // Создаём новый элемент
q->next->next = NULL; // Следующего элемента пока нет
}
// Добавление линии в список
void MPoint::insert(Line z)
{
// Если список пустой
if(!p)
{
p = new Line(z.x,z.y,z.x2,z.y2); // Создаём новый элемент
p->next = NULL; // Следующего элемента пока нет
return; // Выход из функции
}
// Если список не пустой
Point *q = p; // Создаём указатель и устанавливаем его
// на голову списка
// Идём до конца списка
while(q->next)
q = q->next; // Переход к следующему элементу списка
q->next = new Line(z.x,z.y,z.x2,z.y2); // Создаём новый элемент
q->next->next = NULL; // Следующего элемента пока нет
}
void main()
{
clrscr(); // Очистка экрана
MPoint a; // Создаём список
Line l1(10,100,-1,0); // Создаём линию
Point p1(1,2); // Создаём точку
a.insert(l1); // Добавляем в список линию
a.insert(l1); // Добавляем в список линию
a.insert(p1); // Добавляем в список точку
a.insert(p1); // Добавляем в список точку
a.insert(l1); // Добавляем в список линию
a.insert(p1); // Добавляем в список точку
a.display(); // Выводим содержимое списка на экран
getch(); // Ожидание нажатия клавиши
}
В результате работы программы на экран будут выведены строки:
Line(10,100)(-1,0)
Line(10,100)(-1,0)
Point(1,2)
Point(1,2)
Line(10,100)(-1,0)
Point(1,2)
Виртуальные деструкторы
Пример. Рассмотрим следующую программу, в которой виртуальный деструктор базового класса будет переопределён деструктором производного класса.
#include <iostream.h>
#include <conio.h>
class integral
{
int num;
public:
integral(int n):num(n) {}
virtual ~integral()
{
cout << "Inside integral\n";
}
};
class rational: public integral
{
int den;
public:
rational(int n,int d): integral(n), den(d) {}
~rational()
{
cout << "Inside rational\n";
}
};
rational obj(13,5);
int main()
{
clrscr();
integral *ref = &obj;
ref->integral::~integral();
return 0;
}
В этом примере при явном вызове деструктора сначала будет выполнен деструктор производного класса, а потом – деструктор базового класса.
В результате работы программы на экран будет выведено:
Inside integral
Inside rational
Inside integral
Абстрактные классы
Пример. Рассмотрим приложения производных классов в машинной графике. Основным базовым классом здесь будет область – подмножество точек плоскости, для которых задается цвет, и функция, устанавливающая, принадлежит ли этой области точка, которая является аргументом функции. Эта функция называется тестом на принадлежность.
Поскольку заранее неизвестно, каким образом задана область, то тест на принадлежность определим как чисто виртуальную функцию. Будем рассматривать следующую область:
· выпуклая область, заданная системой линейных неравенств (класс 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. Затем выводится выпуклая оболочка этих десяти точек и звездчатый многоугольник, построенный по тем же самым десяти точкам.
