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

Данный метод построения является частным случаем метода заворачивания подарка и называется методом обхода Джарвиса. Метод заворачивания подарка является более общим и годится для построения выпуклой оболочки в пространстве размерности более двух. Приведем программную реализацию описанного алгоритма.

Для создания ее проекта достаточно загрузить Borland C++ Builder, перенести компонент Image на главную форму Form1, набрать следующий далее текст Unit1.cpp и запустить приложение на компиляцию, сборку и выполнение с помощью выбора пункта Run главного меню.

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

#include <vcl.h>

#pragma hdrstop

#include "Unit1.h"

//--------------------------------------------------------------------------#pragma package(smart_init)

#pragma resource "*.dfm"

#include <math.h>

#include <stdlib.h>

#define PI 3.14159

TForm1 *Form1;

int maxX, maxY;

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

{

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

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

float 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;

}

float 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;

}

float fabs(Pnt p)

{

return sqrt(p.x*p.x+p.y*p.y);

}

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 направлено

// против часовой стрелки

}

class CPolygon

{

int color, n;

Pnt *p;

public:

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

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

int isin(Pnt t);

void show(float xmin, float ymin, float xmax, float 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(float xmin, float ymin, float xmax, float 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) * maxX / (xmax - xmin),

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

}

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

}

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

{                    

// построение выауклой оболочки

int a, i, j = 0, k = 0; Pnt *pp = new Pnt [m + 1];

Pnt temp, *s = new Pnt [m + 1];

for(a = 0, i = 1; i < m; i++)      //выбор точки с наименьшей абсциссой

if((x[i] < x[a]) || (x[i] == x[a] && (y[i] < y[a]))) a = i;

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

{

s[i].x = x[i]; s[i].y = y[i]; // перестановка s[a] и s[k]

}

s[m].x = x[a]; s[m].y = y[a];

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

{

temp = s[a]; s[a] = s[k]; s[k] = temp; pp[j++] = s[k];

a = k + 1;

for(i = k + 2; i <= m; i++)

{                            // нахождение точки лежащей слева от остальных