Построение многоугольников и многогранников, страница 7

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

{

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

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

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

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

};

int Pnt::code(Pnt 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 Pnt::operator*(Pnt q)

{

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

}

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

{

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

}

int operator<(Pnt p, Pnt q)

{

Pnt 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(Pnt p, Pnt p1, Pnt 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;

Pnt *p, pC;

public:

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

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

SPolygon(const SPolygon &ob);   // конструктор копирования

int isin(Pnt t);

void show(double xmin, double ymin,

double xmax, double ymax);

};

// Конструктор копирования

SPolygon::SPolygon(const SPolygon &ob)  // необходим для передачи объекта

{                                       // в качестве параметра

int i;

n = ob.n;

p = new Pnt[n];                        // выделим память

for(i=0; i < ob.n; i++) p[i]=ob.p[i]; // производим копирование

}

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

{

int i, j;

Pnt t;

p = new Pnt [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(Pnt 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;

TPoint *parray = new TPoint [n];

Form1->Image1->Canvas->Brush->Color=color;

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

{

parray[i] = Point(

(p[i].x - xmin) * getmaxx() / (xmax - xmin),

(ymax - p[i].y) * getmaxy() / (ymax - ymin));

}

Form1->Image1->Canvas->Polygon(parray,n-1);

int x = (pC.x - xmin) * getmaxx() / (xmax - xmin);

int y = (ymax - pC.y) * getmaxy() / (ymax - ymin);

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

{

line(parray[i].x, parray[i].y, x,y);

}

}

class CPolygon:public SPolygon

{

public:

int isin(Pnt r) {return SPolygon::isin(r);};

void Insert(Pnt t)

{

int i;  int j0, j1, j;

int *del = new int [n];

Pnt *q = new Pnt [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;