Построение выпуклой оболочки методом Дейкстры и звёздчатого многоугольника на Си(C++)

Код на C++
#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 SPolygon
{
protected:
int color, n;
Point *p, pC;
public:
SPolygon(int cl):color(cl){}		// конструктор по умолчанию
SPolygon(double *x, double *y, int m, int cl);
int isin(Point t);
void show(double xmin, double ymin,
double xmax, double ymax);
};
SPolygon::SPolygon(double *x, double *y, int m, int cl):color(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;
}
}
int SPolygon::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;
}
void SPolygon::show(double xmin, double ymin,
double xmax, double ymax)
{
int i;
int *coord = new int [2 * n];
setfillstyle(SOLID_FILL, color);
for(i = 0; i < n; i++)
{
coord[2 * i] = (p[i].x - xmin) * getmaxx() / (xmax - xmin);
coord[2*i + 1] = (ymax - p[i].y) * getmaxy() / (ymax - ymin);
}
fillpoly(n, coord);
}
 
class CPolygon:public SPolygon
{
public:
int isin(Point r) {return SPolygon::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;               //t-принадлежит
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):SPolygon(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);
}
}
 
int main()
{
double rad = 150;	//радиус окружности и вершины семиугольника
int i, mm = 7;
double *x, *y;
x = new double [2 * mm]; y = new double [2 * mm];
 
for(i = 0; i < mm; i++)
{
// вершины большого семиугольника
x[i] = rad * cos(2 * PI * i / mm);
y[i] = rad * sin(2 * PI * i / mm);
// вершины маленького семиугольника
x[i + mm] = rad * cos(2 * PI * i / mm + PI / mm) / 2;
y[i + mm] = rad * sin(2 * PI * i / mm + PI / mm) / 2;
}
randomize();
for(i = 0; i < 2 * mm; i++)
x[i] += random(100) - 50;
 
CPolygon dom2(x, y, 2 * mm, BLACK);	// построение выпуклой
// оболочки
SPolygon dom3(x, y, 2 * mm, LIGHTRED);// построение звездчатого
// полигона
 
int gm, gd = DETECT;
initgraph(&gd, &gm, "..\\bgi");		// инициализация графики
 
setfillstyle(SOLID_FILL, WHITE);		// фон - белый
 
bar(0, 0, getmaxx(), getmaxy());		// закраска экрана
 
dom2.show(-300, -300, 300, 300);	// вывод выпуклой оболочки
dom3.show(-300, -300, 300, 300);	// вывод звездчатого полигона
getch();
closegraph();
return 0;
}
При использовании обязательна ссылка на http://DMTSoft.ru