Класс Polygon (Полигон)
Полигон представляется в виде объекта класса Polygon. Класс содержит два элемента данных. Первый из них, _v, указывает на некоторую вершину полигона - текущую позицию окна полигона. Большинство операций с полигонами относятся либо к текущему окну, либо к вершите в окне. Иногда мы будем ссылаться на вершину в окне как на текущую вершину. Во втором элементе данных, _size, хранится размер полигона:
class Polygon {
private:
Vertex *_v;
int _size;
void resize (void);
public:
Polygon (void);
Polygon (Polygon&);
Polygon (Vertex*);
~Polygon (void);
Vertex *v(void);
int size (void);
Point point (void);
Edge edge (void);
Vertex *cw(void);
Vertex *ccw (void);
Vertex *neighbor (int rotation);
Vertex *advance (int rotation);
Vertex *setV (Vertex*);
Vertex *insert (Point&);
void remove (void);
Polygon * split (Vertex*);
}
Конструкторы и деструкторы
Имеется несколько конструкторов для класса Polygon. Конструктор, не имеющий аргументов, инициирует пустой полигон
Polygon::Polygon(void) :
_v(NULL) , _size(0)
{
}
Копирующий конструктор берет некоторый полигон p и с его помощью инициализирует новый полигон. Он осуществляет полную копию, дублируя связный список, в котором хранится полигон р. Окно нового полигона помещается над вершиной, соответствующей текущей вершине полигона р:
Polygon::Polygon (Polygon &р) {
_size = p._size;
if (_size == 0)
_v = NULL;
else {
_v = new Vertex (p.point());
for (int i = 1; i < _size; i++) {
p.advance(CLOCKWISE);
_v = _v->insert (new Vertex (p.point()));
}
p.advance (CLOCKWISE);
_v = _v->cw();
}
}
Третий конструктор инициализирует полигон с кольцевым двухсвязным списком вершин:
Polygon::Polygon (Vertex *v):
_v(v)
{
resize();
}
Конструктор вызывает собственную компонентную функцию resize для изменения значения элемента _size. В принципе, функция resize должна вызываться всегда, когда к полигону добавляется или из него удаляется цепочка вершин неизвестной длины. Эта функция определяется следующим образом:
void Polygon::resize (void)
{
if (_v == NULL)
_size = 0;
else {
Vertex *v = _v->cw();
for (_size = 1; v != _v; ++_size, v = v->cw());
}
}
Деструктор ~Polygon освобождает вершины текущего полигона, прежде чем удалить сам объект Polygon:
Polygon::~Polygon (void)
{
if (_v) {
Vertex *w = _v- >cw();
while (_v != w) {
delete w->remove();
w = _v->cw();
}
delete _v;
}
}
Функции доступа
Следующие несколько компонентных функций позволяют получить некоторые сведения о текущем полигоне. Функция v возвращает текущую вершину данного полигона, а функция size - его размер:
Vertex *Polygon::v(void)
{
return _v;
}
int Polygon::size(void)
{
return _size;
}
Указатель, возвращаемый функцией v, может быть использован в виде дополнительного окна для полигона как дополнение к неявному окну полигона. В некоторых применениях требуется одновременное использование нескольких окон для одного и того же полигона - единственного окна, обеспечиваемого в классе неявно, не всегда оказывается достаточно.
Компонентная функция point возвращает точку на плоскости, которая соответствует текущей вершине. Компонентная функция edge возвращает текущее ребро. Текущее ребро начинается в текущей вершине и заканчивается в следующей после нее вершине:
Point Polygon::point (void)
{
return _v->point();
}
Edge Polygon::edge(void)
{
return Edge (point(), _v->cw()->point());
}
Класс Edge (ребро) будет определен в следующем разделе.
Компонентные функции cw и ccw возвращают последователя и предшественника для текущей вершины, оставляя без изменения положение окна. Функция neighbor (сосед) возвращает указатель на последователя или предшественника текущей вершины в зависимости от значения аргумента, с которым она вызывается (CLOCKWISE или COUNTER_CLOCKWISE - по часовой стрелке или против):
Vertex *Polygon::cw(void)
{
return _v->cw();
}
Vertex *Polygon::ccw(void)
{
return _v->ccw();
}
Vertex *Polygon::neighbor(int rotation)
{
return _v->neighbor(rotation);
}
Функции редактирования
Компонентные функции advance и setV перемещают окно на различные вершины. Функция advance (продвинуть) перемещает окно на последователя или предшественника текущей вершины в зависимости от заданного аргумента:
Vertex *Polygon::advance(int rotation)
{
return _v = _v->neighbor(rotation);
}
Компонентная функция setV перемещает окно на вершину v, указанную в качестве аргумента:
Vertex *Polygon::setV(Vertex *v)
{
return _v = v;
}
В программе должно быть обеспечено, чтобы вершина - v принадлежала текущему полигону.
Компонентная функция insert вносит новую вершину после текущей и затем перемещает окно на новую вершину:
Vertex *Polygon::insert(Point &p)
{
if (_size++ == 0)
_v = new Vertex(p);
else
_v = _v->insert(new Vertex(p));
return _v;
}
Компонентная функция remove удаляет текущую вершину. Окно перемещается на предшественника или остается неопределенным, если полигон становится пустым:
void Polygon::remove(void)
{
Vertex *v = _v;
_v = (--_size == 0) ? NULL : _v->ccw();
delete v->remove();
}
Расщепление полигонов
Расщепление полигонов заключается в делении полигонов на два меньших полигона. Разрезание осуществляется по некоторой хорде. Чтобы разрезать полигон вдоль хорды ab, вначале внесем после вершины а ее дубликат, а дубликат вершины b внесем перед вершиной b (эти дубликаты назовем ар и bр). Затем произведем разделение в вершинах а и bр. Этот процесс проиллюстрирован на рисунке ниже
Компонентная функция Polygon::split определена в терминах функции Vertex::split. Эта последняя функция разделяет полигон вдоль хорды, соединяющей текущую вершину (которая играет роль вершины а) с вершиной b. Она возвращает указатель на вершину bр, являющуюся дублем вершины b:
Vertex *Vertex::split(Vertex *b)
{ // занесение bр перед вершиной b
Vertex *bр = b->ccw()->insert(new Vertex(b->point()));
insert(new Vertex(point()));
// занесение ар после текущей вершины
splice(bр);
return bр;
}
Компонентная функция Polygon::split разрезает текущий полигон вдоль хорды, соединяющей ее текущую вершину с вершиной b. Она возвращает указатель на новый полигон, окно которого размещено над вершиной bр, являющейся дубликатом вершины b. Положение окна над текущим полигоном не изменяется.
Polygon *Polygon::split (Vertex *b)
{
Vertex *bp = _v->split(b);
resize();
return new Polygon(bр);
}
Компонентная функция Polygon::split должна использоваться с некоторой осторожностью. Если вершина b является последователем текущей вершины _v, то после выполнения операции полигон остается неизменным. Если разрезание производится вдоль диагонали, не являющейся хордой, то один или даже оба результирующих 'полигона' могут оказаться взаимно пересекающимися. Если вершины b и _v принадлежат разным полигонам, то операция разделения приводит к соединению двух полигонов по двум совпадающим ребрам, которые соединяют эти две вершины.
Точки, входящие в состав выпуклого полигона
В этом и последующем подразделах будут представлены две простые программы для работы с полигонами. Программа point InConvexPolygon обсчитывает точку s и полигон р и возвращает значение TRUE только в том случае, если точка лежит внутри полигона р (в том числе и на его границе):
bool pointlnConvexPolygon (Point &s , Polygon &p)
{
if (p. size() == 1)
return (s == p.point());
if (p. size () == 2) {
int c = s .classify (p. edge ());
return ( (c==BETWEEN) || (c==ORIGIN) | || (c==DESTINATION) );
}
Vertex *org = p.v();
for (int i = 0; i < p.size(); i++, p.advance(CLOCKWISE))
if (s.classify (p.edge()) == LEFT) {
p.setV(org);
return FALSE;
}
return TRUE;
}
В этой функции вначале анализируются специальные случаи на принадлежность полигона р вырожденным полигонам - 1-гону или 2-гону. В общем случае в процессе работы алгоритма обходится граница полигона, т. е. окно перемещается от вершины к соседней вершине и производится поочередный анализ взаимного положения точки s и каждого ребра. Поскольку предполагается, что полигон р выпуклый, то точка s лежит вне полигона только в том случае, если она окажется слева от какого-либо узла. Заметим, что перед выходом в программе восстанавливается первоначальное положение окна в полигоне р.
Определение наименьшей вершины в полигоне
В следующую функцию в качестве аргументов передаются полигон р и функция сравнения cmp и в ней производится поиск наименьшей вершины в полигоне р. Здесь под термином наименьшая вершина подразумевается вершина, которая меньше всех остальных при линейном упорядочении точек в смысле, задаваемом функцией cmp. Функция leastVertex перемещает окно полигона р на эту наименьшую вершину и возвращает указатель на эту вершину:
Vertex *leastVertex( Polygon &p, int (*cmp)(Point*,Point*) )
{
Vertex *bestV = p.v();
p.advance(CLOCKWISE);
for (int i=1; i < p.size(); p.advance(CLOCKWISE), i++)
if ((*cmp)(p.v(),bestV) < 0)
bestV = p.v();
p.setV(bestV);
return bestV;
}
Например, для обнаружения самой левой вершины следует обратиться к функции leastVertex со следующей функцией сравнения:
int leftToRightCmp (Point *a, Point *b)
{
if (*a < *b) return -1;
if (*a > *b) return 1;
return 0;
}
Для нахождения самой правой вершины можно использовать такую функцию сравнения:
int rightToLeftCmp(Point *a, Point *b)
{
return leftToRightCmp(b, a);
}
1 2 3 4
8 8 8
| 
*
Обратная связь