Структура сканирующей линии Структура сканирующей линии представляется в виде словаря(возможно использование класса RandomizedSearchTree, как показано в начале статьи) активных ребер, т. е. тех ребер полигона, которые пересекают сканирующую линию в данный момент, упорядоченных по увеличению координаты у. Кроме того, структура сканирующей линии содержит точку с минимальной координатой у (лежащую ниже всех ребер), служащую в качестве стража. Мы будем представлять структуру сканирующей линии в виде словаря объектов ActiveElement. class ActiveElement { public : int type; // ACTIVE_EDGE (ребро) или ACTIVE_POINT (точка) ActiveElement (int type); virtual double у (void) = 0; virtual Edge edge(void) { return Edge(); }; virtual double slope(void) { return 0.0; }; }; Конструктор ActiveElement инициализирует элемент данных type, который показывает, является ли элемент ребром или точкой: ActiveElement::ActiveElement (int t) : type(t) { } Остальные компонентные функции класса ActiveElement являются виртуальными и они будут обсуждены несколько позже, в контексте двух производных классов. Активные ребра представляются в виде объектов класса ActiveEdg: class ActiveEdge : public ActiveElement { public : Vertex *v; Vertex *w; int rotation; ActiveEdge (Vertex *_v, int _r, Vertex *_w); Edge edge (void); double у (void); double slope (void); }; Элемент данных v указывает на одну из концевых точек текущего ребра, a v->cw() - на другой конец. Элемент данных w является целевой вершиной пары ребер, состоящей из текущего ребра и активного ребра, расположенного непосредственно над ним. Элемент данных rotation используется для отслеживания связи от текущего ребра к ребру, которое может пересекать текущее ребро за сканирующей линией: если такое ребро существует, то v->neighbor (rotation) определяет окно на ребре. Конструктор ActiveEdge определяется непосредственно: ActiveEdge::ActiveEdge (Vertex *_v, int _r, Vertex *_w) : ActiveElement (ACTIVE_EDGE), v(_v), rotation (_r), w(_w) { } Компонентная функция у возвращает координату у точки пересечения текущего ребра со сканирующей линией. Компонентные функции edge и slope возвращают текущее ребро и наклон текущего ребра соответственно. Эти три функции определяются как: double ActiveEdge::у(void) { return edge().y(curx); } Edge ActiveEdge::edge(void) { return Edge(v->point(), v->cw()>point()); } double ActiveEdge::slope(void) { return edge().slope(); } Структура сканирующей линии формируется так, чтобы она могла содержать точки наряду с ребрами, поскольку она должна обеспечивать операции определения положения точки в такой форме: для данной точки на сканирующей линии найти пару активных ребер, между которыми находится данная точка. Вот поэтому мы и определили класс ActiveElement так, чтобы получить из него производные классы, один для представления ребер и второй - для представления точек. Для целей поиска внутри структуры сканирующей линии мы будем представлять точку в виде объекта класса ActivePoint: class ActivePoint : public ActiveElement { public: Point p; ActivePoint (Point&); double у(void); }; Конструктор класса определим как: ActivePoint::ActivePoint (Point &_p) : ActiveElement (ACTIVE_POINT), p (_p) { } Компонентная функция у просто возвращает координату у текущей точки double ActivePoint::у (void) { return р.у; } Определив необходимые классы, перейдем к рассмотрению структуры сканирующей линии. Структура сканирующей линии создается с помощью функции buildSweepline. Функция инициализирует новый словарь и сохраняет активную точку, служащую в качестве стража - точку, расположенную ниже любого ребра, которое будет записано в словарь впоследствии: Dictionary &buildSweepline () { Dictionary *sweepline = new Dictionary (activeElementCmp); sweepline->insert (new ActivePoint (Point (0.0, -DBL_MAX))); return *sweepline; } Функция сравнения activeElementCmp применяется для сравнения двух активных элементов: int activeElementCmp (ActiveElement *а, ActiveElement *b) { double ya = a->y(); double yb = b->y(); if (ya < yb) return -1; else if (ya > yb) return 1; if ( (a->type == ACTIVE_POINT) && (b->type == ACTIVE_POINT)) return 0; else if (a->type == ACTIVE_POINT) return -1; else if (b->type == ACTIVE_POINT) return 1; int rval = 1; if ( (sweepdirection==LEFT_TO_RIGHT && curtype==START_TYPE) || (sweepdirection==RIGHT_TO_LEFT && curtype==END_TYPE) ) rval = -1; double ma = a->slope(); double mb = b->slope(); if (ma < mb) return rval; else if (ma > mb) return -rval; return 0; } Функция activeElementCmp вначале сравнивает активные элементы а и b на основе координат у их точек пересечения со сканирующей линией. Если они пересекаются в одной и той же точке, то считается, что активная точка расположена под активным ребром. Если оба элемента а и b являются активными ребрами, то для определения, какое из них лежит ниже другого, используются их соответствующие параметры наклона. Если предположим, что сканирование осуществляется слева направо, то ребро с меньшим коэффициентом наклона расположено ниже другого, если точка-событие является начальной вершиной, и выше другого, если точка-событие является конечной вершиной. Если предположим, что сканирование производится справа налево, то роли начальной и конечной вершин взаимно меняются местами (например, начальная вершина при сканировании слева направо становится конечной вершиной при сканировании в противоположном направлении) <<<  Назад Вперед  >>>  1  2  3   8  Комментарии к статье  8 8  Обсудить в чате