Отсечение многоугольников

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

Рассмотрим алгоритм Сазерленда-Ходгмана (Sutherland-Hodgman). В алго­ритме исполь­зуется стратегия «разде­ляй и властвуй», которая позволяет решение общей задачи свести к решению ряда простых и похожих под­задач. Примером такой подзадачи явля­ется отсечение многоугольника относительно одной отсекающей границы. Последова­тельное решение четы­рех таких задач позволяет провести отсечение относительно пря­моугольной об­ласти (Рис. 2.7.).

Рис. 2.7 Последовательное отсечение многоугольника

На вход алгоритма поступает последовательность вершин многоугольника V₁, V₂, …, V_n. Ребра многоугольника проходят от V_i к V_i+1 от V_n к V₁. С помо­щью алгоритма производится отсечение относительно ребра и выводится другая последовательность вершин, описывающая усеченный многоугольник.

Алгоритм «обходит» вокруг многоугольника от V_n к V₁ и обратно к V_n, проверяя на ка­ждом шаге соотношение между последовательными верши­нами и отсекающей границей. Необходимо проанализировать четыре случая:

Рис. 2.8 Случаи, возникающие при отсечении многоуголь­ников

Рассмотрим изображенное на рис. 2.8. ребро многоугольника, соединяющее вершину s с вершиной p. В первом случае ребро полностью лежит внутри отсекающей границы, к выходному списку добавляется вер­шина p. Во втором случае в качестве вершин выво­дится точка пересечения i, поскольку ребро пересекает границу, а началь­ная точка была выведена при анализе первого случая. В третьем случае обе вершины находятся за пре­де­лами границы, и ни одна из них не выводится. В четвертом случае к выход­ному списку добавляется и точка пересече­ния i и вершина p.

При отсечении многоугольника, описанным алгоритмом, возникает про­блема, связанная с тем, что появляются ребра, частично совпадающие с гра­ницей окон. Лишние ребра можно устранить, введя дополнительную обра­ботку, или воспользовавшись более общим, и более сложным, алгоритмом Вейлера – Азертона.