В предыдущих разделах были рассмотрены два алгоритма отсечения многоугольника, последовательно отсекающие произвольный (как выпуклый, так и невыпуклый) многоугольник каждой из сторон выпуклого окна. Зачастую же требуется отсечение по невыпуклому окну. Кроме того оба рассмотренных алгоритма могут генерировать лишние стороны для отсеченного многоугольника, проходящие вдоль ребра окна отсечения. Далее рассматриваемый алгоритм Вейлера-Азертона [41] свободен от указанных недостатков ценой заметно большей сложности и меньшей скорости работы. Предполагается, что каждый из многоугольников задан списком вершин, причем таким образом, что при движении по списку вершин в порядке их задания внутренняя область многоугольника находится справа от границы. В случае пересечения границ и отсекаемого многоугольника и окна возникают точки двух типов: входные точки, когда ориентированное ребро отсекаемого многоугольника входит в окно, выходные точки, когда ребро отсекаемого многоугольника идет с внутренней на внешнюю стороны окна. Общая схема алгоритма Вейлера-Азертона для определения части отсекаемого многоугольника, попавшей в окно, следующая: Строятся списки вершин отсекаемого многоугольника и окна. Отыскиваются все точки пересечения. При этом расчете касания не считаются пересечением, т.е. когда вершина или ребро отсекаемого многоугольника инцидентна или совпадает со стороной окна (рис. 0.3.29 и 0.3.30). Списки координат вершин отсекаемого многоугольника и окна дополняются новыми вершинами - координатами точек пересечения. Причем если точка пересечения Pk находится на ребре, соединяющем вершины Vi, Vj, то последовательность точек Vi, Vj превращается в последовательность Vi, Pk, Vj. При этом устанавливаются двухсторонние связи между одноименными точками пересечения в списках вершин отсекаемого многоугольника и окна. Входные и выходные точки пересечения образуют отдельные подсписки входных и выходных точек в списках вершин. Определение части обрабатываемого многоугольника, попавшей в окно выполняется следующим образом: Если не исчерпан список входных точек пересечения, то выбираем очередную входную точку. Двигаемся по вершинам отсекаемого многоугольника пока не обнаружится следующая точка пересечения; все пройденные точки, не включая прервавшую просмотр, заносим в результат; используя двухстороннюю связь точек пересечения, переключаемся на просмотр списка вершин окна. Двигаемся по вершинам окна до обнаружения следующей точки пересечения; все пройденные точки, не включая последнюю, прервавшую просмотр, заносим в результат. Используя двухстороннюю связь точек пересечения, переключаемся на список вершин обрабатываемого многоугольника. Эти действия повторяем пока не будет достигнута исходная вершина - очередная часть отсекаемого многоугольника, попавшая в окно, замкнулась. Переходим на выбор следующей входной точки в списке отсекаемого многоугольника. Рис. 0.3.27: Случаи не считающиеся пересечением Рис. 0.3.28: Частные случаи пересечения Модификация этого алгоритма для определения части отсекаемого многоугольника, находящейся вне окна, заключается в следующем: исходная точка пересечения пересечения берется из списка выходных точек, движение по списку вершин окна выполняется в обратном порядке, т.е. так чтобы внутренняя часть отсекателя была слева. На рис. 0.3.31 иллюстрируется отсечение многоугольника ABCDEFGHI окном PQRS по алгоритму Вейлера-Азертона. Рис. 0.3.29: Отсечение по алгоритму Вейлера-Азертона Начиная с этого алгоритма, при рассмотрении многих дальнейших требуется представления о различных структурах данных и работе с ними. Следующий раздел и посвящен беглому рассмотрению некоторых наиболее важных структур данных.  8  Комментарии к статье  8 8  Обсудить в чате