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

Суть: Произвести отсечение относительно одной прямой.

Отсекается все что невидимо.

Исходный многоугольник задается списком вершин (P1,..., Pn).

Порождается список ребер (P1P2,..., Pn-1 Pn, PnP1). Нахождение точки Q8 стало тривиальным.

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

Возможны четыре варианта положения отсекателя и многоугольника:

рассмотрим точку P как конечную точку какого-то ребра

1.полная видимость:

видимая сторона отсекающая плоскость

P S - начальная точка;

P - конечная точка.

Результат - точка P(полная видимость);

S Точка S в результирующий список не заносится.

2. полная невидимость:

видимая сторона отсекающая плоскость

Результат - точек нет.

3. выход из области видимости:

видимая сторона отсекающая плоскость

Результат - точка I.

I

4. вход в видимую область:

видимая сторона отсекающая плоскость

Результат - точки I,P.

I

Для первой вершины достаточно определить, является ли она видимой, если да, то она попадает в результирующий список и является начальной точкой S; если нет, то она не попадает результирующий список, но становится точкой S.

Последнее ребро P_nP₁: точку P₁ рассматривают как точку F и ребро P_nP₁ рассматривают как обычное ребро P_nF.

Плохая особенность алгоритма: ложные границы.

Пр. Возникновения ложных границ.

1. 2. 3. 4.

5.

Дата добавления: 2014-01-07