![]() |
||||
|
|
||||
|
|
||||
«Последовательное отсечение многоугольника - алгоритм Сазерленда-Ходжмена» |
||||
|
|
||||
|
Основная идея алгоритма Сазерленда - Ходжмена состоит в том, что отсечь многоугольник относительно одной прямой или плоскости очень легко. В этом алгоритме исходный и каждый из промежуточных многоугольников отсекается последовательно относительно одной прямой. Исходный многоугольник задается списком вершин P1, ..., Pn, который порождает список его ребер P1 P2, P2 P3, : ,Pn-1 Pn, Pn P1.
Результатом работы алгоритма является список вершин многоугольника, у которого все вершины лежат по видимую сторону от очередной отсекающей плоскости. Поскольку каждая вершина многоугольника отсекается независимо от других, то достаточно рассмотреть только возможные ситуации расположения одного отрезка относительно одной отсекающей плоскости. Будем рассматривать каждую точку P из списка вершин многоугольника, за исключением первой, как конечную точку ребра, начальной точкой S которого является вершина, предшествующая P в этом списке. Тогда возможны только четыре ситуации взаимного расположения ребра и отсекающей плоскости...
|
||||
|
|
||||
|
|