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

{

return x!=q.x || y!=q.y;

}

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 CPolygon

{

int color, n;

Pnt *p, pC;

public:

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

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

int isin(Pnt t);

void show(double xmin, double ymin,

double xmax, double ymax);

};

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

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

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

int i;

n = ob.n; color = ob.color;

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

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

}

void CPolygon::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);

}

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

{

int i, j; int i0 = 0, v, w, f = 0;

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;

}

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

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

{

if(p[j].y < p[i0].y) i0 = j;     // точка с наименьшей ординатой

else if(p[j].y == p[i0].y && p[j].x > p[i0].x)

i0 = j;                          // самая правая

}

v = i0;

Pnt p0 = p[i0];

if(v > 0) w = (v - 1)%n; else w = n - 1; f = 0;

Pnt p1 = p[w];

while((p[(v + 1)%n] != p0) || (f == 0))

{

if(p[(v + 1)%n] != p1); else f = 1;

if((p[(v + 1)%n] - p[v]) * (p[(v + 2)%n] - p[v]) > 0) v = (v + 1)%n;

else

{

for(i = (v + 1)%n; i < n; i++) p[i]=p[(i + 1)%n]; //i<n

n = n - 1;                            // удаление v + 1

if(v == 0) v = n - 1;

else v = (v - 1)%n;

}

}

}

//

int CPolygon::isin(Pnt t)

{

int i,j, parity = 0;

for(i = 0, j=n-1; i < n; j=i++)

{

if (( ( (p[i].y<=t.y)&&(t.y<p[j].y) )||

((p[j].y<=t.y)&&(t.y<p[i].y)))&&

(t.x<(p[j].x-p[i].x)*(t.y-p[i].y)/

(p[j].y-p[i].y)+p[i].x))

parity=1-parity;

}

return parity;

}

//--------------------------------------------------------------------------__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

double rad = 150, *x, *y;            // радиус окружности и

// вершины 2mm-угольника

int i; randomize();

int mm = 10;

x = new double[2 * mm]; y = new double [2 * mm];

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

{

// вершины большого 2mm-угольника

x[i] = rad * cos(2. * PI * i / mm);

y[i] = rad * sin(2. * PI * i / mm);

// вершины маленького 2mm-угольника

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 cpoly(x, y, 10, clLtGray);  // построение выпуклой оболочки

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

Pnt f = {0., 0.};

for(i = 0; i < 2 * mm; i++)

{

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

if(cpoly.isin(f))

Form1->Image1->Canvas->Rectangle((int)(x[i] + 300.) * getmaxx() / 600 - 1,