Алгоритм Николла – Ли – Николла

В компьютерной графике алгоритм Николла-Ли-Николла представляет собой быстрый алгоритм обрезки линий , который снижает вероятность многократного отсечения одного сегмента линии, как это может произойти в алгоритме Коэна-Сазерленда .

Описание

Используя алгоритм Николла-Ли-Николла, область вокруг окна отсечения делится на несколько различных областей в зависимости от положения начальной точки обрезаемой линии. Эта начальная точка должна находиться в трех заранее определенных областях; таким образом, линию, возможно, придется переместить и/или повернуть, чтобы перенести ее в нужную область. Затем сегмент линии можно повторно переместить и/или повернуть, чтобы вернуть его в исходное положение. После этого от конечной точки линии рисуются отрезки прямых, проходящие через углы окна отсечения. Эти области затем обозначаются как L, LT, LB или TR, в зависимости от местоположения начальной точки. Затем другая конечная точка линии сверяется с этими областями. Если линия начинается в области L и заканчивается в области LT, алгоритм приходит к выводу, что линия должна быть обрезана в точке xw (макс.). Таким образом, количество точек отсечения сокращается до одной по сравнению с другими алгоритмами, которым может потребоваться две или более точек отсечения.

См. также

Алгоритмы, используемые для той же цели:

• Алгоритм Ляна – Барского
• Алгоритм Сайруса – Бека
• Быстрая обрезка

Ссылки

• Тина М. Николл; Д.Т. Ли; Робин А. Николл (1987). «Новый эффективный алгоритм обрезки двумерных линий: его разработка и анализ» . Материалы 14-й ежегодной конференции по компьютерной графике и интерактивным технологиям - SIGGRAPH '87 . стр. 253–262. дои : 10.1145/37401.37432 . ISBN  0897912276 . S2CID   32296395 .