Алгоритм Сазерленда-Ходжмена для отсечения многоугольника.

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

,

который порождает список его ребер:

.

Шаги алгоритма на рис.:

Рис. 4.9

Добавление точки Q₈ теперь стало тривиальным. Этот алгоритм может отсекать любой многоугольник (выпуклый и невыпуклый, плоский и неплоский) относительно любого окна, являющегося выпуклым многоугольником. Порядок отсечения многоугольника разными сторонами непринципиален. Результат работы алгоритма — список новых вершин многоугольника. Так как каждая сторона многоугольника отсекается независимо от других, то достаточно рассмотреть только возможные ситуации расположения одного отрезка относительно одной отсекающей плоскости.

Рассмотрим каждую точку Р из списка, за исключением первой, как конечную точку ребра, начальной точкой S которого является предыдущая Р_i-1 точка в этом списке. Возможны четыре ситуации расположения ребра и отсекающей плоскости:

Рис. 4.10

Результатом будет занесение в список вершин результирующего усеченного многоугольника нуля, одной или двух вершин.

· Полная видимость. Результат — вершина Р (1 точка) (заносить в результат начальную точку S не надо, так как если вершины рассматриваются поочередно, то точка S уже была конечной точкой предыдущего ребра и уже попала в результат).

· Полная невидимость. Результат — 0 точек.

· Выход из области видимости. Результат — точка R (1 точка).

· Вход в область видимости. Результат — точки R, P (2 точки) (так как конечная вершина Р видима, она тоже должна попасть в результат).

Для первой вершины многоугольника надо определить только факт ее видимости. Если вершина видима, то она попадает в результат и становиться начальной точкой S. Если же вершина невидима, она тоже становится начальной точкой, но в результат не попадает.