Алгоритм Сазерленда – Ходжмана

Алгоритм Сазерленда -Ходжмана — это алгоритм, используемый для отсечения многоугольников . Он работает путем расширения каждой линии выпуклого полигона обрезки по очереди и выбора только вершин из рассматриваемого многоугольника , которые находятся на видимой стороне.

Описание

Алгоритм начинается с ввода списка всех вершин рассматриваемого многоугольника. Затем одна сторона многоугольника отсечения бесконечно расширяется в обоих направлениях и пересекается путь рассматриваемого многоугольника. Вершины из входного списка вставляются в выходной список, если они лежат на видимой стороне линии расширенного полигона отсечения, а новые вершины добавляются в выходной список там, где путь рассматриваемого полигона пересекает линию расширенного полигона отсечения.

Этот процесс повторяется итеративно для каждой стороны полигона обрезки, используя выходной список одного этапа в качестве входного списка для следующего. После обработки всех сторон обрезанного многоугольника окончательный сгенерированный список вершин определяет новый одиночный многоугольник, который полностью видим. Обратите внимание: если рассматриваемый многоугольник был вогнутым в вершинах за пределами обтравочного многоугольника, новый многоугольник может иметь совпадающие (т. е. перекрывающиеся) края – это приемлемо для рендеринга, но не для других приложений, таких как вычисление теней.

Алгоритм Вейлера-Атертона преодолевает эту проблему, возвращая набор разделенных многоугольников, но он более сложен и требует больше вычислительных затрат, поэтому Сазерленд-Ходжман используется во многих приложениях рендеринга. Сазерленда-Ходжмана также можно расширить в трехмерное пространство, обрезав пути многоугольников на основе границ плоскостей, определенных пространством просмотра.

Псевдокод

Учитывая список ребер в полигоне обрезки и список вершин в полигоне субъекта, следующая процедура отсекает полигон субъекта относительно полигона обрезки.

List outputList = subjectPolygon;  

for (Edge clipEdge in clipPolygon) do
    List inputList = outputList;
    outputList.clear();

    for (int i = 0; i < inputList.count; i += 1) do
        Point current_point = inputList[i];
        Point prev_point = inputList[(i − 1) % inputList.count];

        Point Intersecting_point = ComputeIntersection(prev_point, current_point, clipEdge)

        if (current_point inside clipEdge) then
            if (prev_point not inside clipEdge) then
                outputList.add(Intersecting_point);
            end if
            outputList.add(current_point);

        else if (prev_point inside clipEdge) then
            outputList.add(Intersecting_point);
        end if

    done
done

Вершины обрезанного многоугольника должны быть найдены в списке вывода после завершения работы алгоритма. Обратите внимание, что точка считается находящейся внутри края, если она находится на той же стороне края, что и остальная часть многоугольника. Если вершины многоугольника отсечения последовательно перечислены против часовой стрелки, то это эквивалентно проверке того, находится ли точка слева от линии (слева означает внутри , а справа означает снаружи ), и это можно реализовать просто с помощью используя перекрестное произведение .

ComputeIntersection — это функция, опущенная здесь для ясности, которая возвращает пересечение отрезка линии и бесконечного ребра. Обратите внимание, что точка пересечения добавляется в выходной список только тогда, когда известно, что пересечение существует, поэтому обе линии всегда можно рассматривать как бесконечно длинные.

Реализации

Python-реализацию метода Сазерленда-Ходжмана можно найти здесь .

См. также

Другие алгоритмы отсечения полигонов:

По поводу обрезки:

Ссылки

Мел Слейтер, Энтони Стид, Йоргос Хрисанту: Компьютерная графика и виртуальная среда: от реализма к реальному времени. Эддисон Уэсли, 2002. ISBN 0-201-62420-6 .
Иван Сазерленд , Гэри В. Ходжман: Обрезка возвратного полигона. Сообщения ACM , вып. 17, стр. 32–42, 1974 г.

Внешние ссылки

Обрезка и заполнение полигонов. Описывает алгоритм с использованием простых для понимания изображений.
Пример Розеттского кода