Nicholl–Lee–Nicholl-algoritm

Inom datorgrafik är Nicholl -Lee-Nicholl- algoritmen en snabb algoritm för linjeklippning som minskar chanserna att klippa ett enda linjesegment flera gånger, vilket kan hända i Cohen-Sutherland-algoritmen .

Beskrivning

Med hjälp av Nicholl–Lee–Nicholl-algoritmen delas området runt klippfönstret upp i ett antal olika områden, beroende på positionen för den initiala punkten på linjen som ska klippas. Denna initiala punkt bör vara i tre förutbestämda områden; sålunda kan linjen behöva förflyttas och/eller roteras för att föra den till det önskade området. Linjesegmentet kan sedan återtranslateras och/eller omroteras för att bringa det till den ursprungliga positionen. Därefter ritas raka linjesegment från linjens slutpunkt och passerar genom hörnen på klippfönstret. Dessa områden betecknas sedan som L, LT, LB eller TR, beroende på platsen för den initiala punkten. Sedan kontrolleras linjens andra ändpunkt mot dessa områden. Om en linje börjar i L-området och slutar i LT-området drar algoritmen slutsatsen att linjen ska klippas vid xw (max). Således minskas antalet klipppunkter till en, jämfört med andra algoritmer som kan kräva två eller flera klippningar

Se även

Algoritmer som används för samma ändamål:

• Liang–Barsky-algoritm
• Cyrus-Beck algoritm
• Snabb klippning

• Tina M. Nicholl; DT Lee; Robin A. Nicholl (1987). "En effektiv ny algoritm för 2D-linjeklippning: dess utveckling och analys" . SIGGRAF '87 : 253–262.