// step 2
originPt = s [0];
qsort ( & s [1], n -1, sizeof ( Vector2D ), polarCmp );
// step 3
for (i = 1; s [i+1].classify (s [0], s [i]) == BEYOND; i++ )
Stack stack;
stack.push ( s [0]); stack.push ( s [i]);
// step 4 for ( ++i; i < n; i++ )
{
while ( s [i].classify (*.stack.nextToTop (), *stack.top ()) != LEFT ) stack.pop ();
stack.push ( s [i]);
}
// step 5 Polygon * p = new Polygon;
while ( Lstack.isEmpty ())
p -> addVertex ( stack.pop (), p -> numVertices );
return p;
}Быстродействие данного алгоритма равно 0(n\og и).
8.9. Пересечение выпуклых многоугольников Рассмотрим задачу об отсечении произвольного многоугольника по границе заданного выпуклого многоугольника. Одним из наиболее простых алгоритмов для решения этой задачи является алгоритм Сазерленда - Ходжмана, который мы и рассмотрим.
Алгоритм сводит исходную задачу к серии более простых задач об отсечении многоугольника вдоль прямой, проходящей через одно из ребер отсекающего многоугольника.
На каждом шаге (рис. 8.8) выбираем очередное ребро отсекающего многоугольника и поочередно проверяем положение всех вершин отсекаемого многоугольника относительно прямой, проходящей через выбранное текущее ребро. При этом в результирующий многоугольник добавляется 0, 1 или 2 вершины.
Компьютерная графика. Полигональные модели
Рассмотрим ребро отсекаемого многоугольника, соединяющее вершины р(рх, ру) и с(сх, су). Возможны 4 различных ситуации (рис. 8.9).
Внутри Снаружи Внутри Снаружи Внутри Снаружи Внутри Снаружи
Предположим, что точка р уже обработана. В случае а ребро целиком лежит во внутренней области и точка с добавляется в результирующий многоугольник. В случае б в результирующий многоугольник добавляется точка пересечения /. В случае в обе вершины лежат во внешней области и поэтому в результирующий многоугольник не добавляется ни одной точки. В случае г в результирующий многоугольник добавляются точка пересечения / и точка с.
Приводимая ниже функция clipPolygon реализует описанный алгоритм.
О // File polyclip.cpp #include "polygon.h"