Redigerer Sutherland-Hodgmans algoritme

'''Sutherland&#x2013;Hodgmans algoritme''' brukes for å [[Klipping (Datagrafikk)|klippe]] [[Polygon|polygoner]]. Den virker ved å utvide hver av kantene i det konvekse ''klippepolygonet'' etter tur, og så velge kun de knutepunktene fra ''polygonet'' som befinner seg i det synlige området.

== Beskrivelse ==
Algoritmen starter med en [[liste]] over alle knutepunktene i polygonet. Deretter velges en kant i klippepolygonet som utvides uendelig i begge retninger, før polygonet løpes gjennom. Knutepunktene fra polygonet settes direkte inn i en ny liste hvis de befinner seg på den synlige siden av den uendelig lange kanten. Hvis et knutepunkt befinner seg på utsiden, settes det inn et nytt punkt i krysningspunktet mellom den uendelige linjen og dette punktets linje. Dette nye punktet legges så inn i listen.

Denne prosessen blir utført for hver kant i klippepolygonet, og hver gang brukes den listen som ble laget ved forrige [[iterasjon]]. Når alle sidene i klippepolygonet har blitt prosessert, får man den endelige listen med knutepunkter, som nå definerer et polygon helt innenfor det synlige området. Merk at hvis polygonet er konkavt i området utenfor klippepolygonet, kan det hende det nye polygonet får en eller flere overlappende kanter. Dette er akseptabelt til rendering, men ikke i tilfeller hvor polygonet skal brukes til å generere skygger. 
[[Fil:Sutherland-Hodgman_clipping_sample.svg|centre|frame|Alle stegene som utføres ved klipping av det konkave polygonet ''W'' med et femsidet konvekst klippepolygon]]
[[Weiler–Athertons algoritme]] unngår dette ved å returnere et sett med oppdelte polygoner, men er mer komplisert, og krever mer prosesseringskraft. Derfor foretrekkes Sutherland–Hodgman i mange renderingsapplikasjoner. Sutherland&#x2013;Hodgman kan også utvides til 3D ved å bruke plan istedenfor kanter.

== Pseudokode ==
Gitt en liste med kanter i et klippepolygon, og en liste med kanter i et polygon vi ønsker å klippe, kjøres følgende prosedyre mot klippepolygonet.
   List outputList = subjectPolygon;
   for (Edge clipEdge in clipPolygon) do
      List inputList = outputList;
      outputList.clear();
      Point S = inputList.last;
      for (Point E in inputList) do
         if (E inside clipEdge) then
            if (S not inside clipEdge) then
               outputList.add(ComputeIntersection(S,E,clipEdge));
            end if
            outputList.add(E);
         else if (S inside clipEdge) then
            outputList.add(ComputeIntersection(S,E,clipEdge));
         end if
         S = E;
      done
   done
Knutepunktene i det klippede polygonet finnes i ''outputList''. Merk at et punkt defineres som ''på innsiden'' av en kant hvis det ligger på samme side av kanten som resten av polygonet. Hvis knutepunktene i klippepolygonet er angitt i retning med klokken, vil dette bli det samme som å sjekke om punktet ligger til venstre for linjen (venstre betyr ''innenfor'', høyre betyr ''utenfor''), og kan regnes ut enkelt ved å bruke [[Kryssprodukt|kryssproduktet]].

''ComputeIntersection'' er en enkel funksjon som returnerer krysningspunktet mellom en linje og en uendelig lang kant. Den er ikke tatt med her for ryddighetens skyld.  Merk at funksjonen kun kjøres hvis et krysningspunkt finnes, og vi kan derfor se på begge linjene som uendelig lange.

== Litteratur ==
* Mel Slater, Anthony Steed, Yiorgos Chrysanthou: ''Computer Graphics and Virtual Environments: From Realism to Real-Time.'' Addison Wesley. ISBN 0-201-62420-6
* [[Ivan Sutherland]], Gary W. Hodgman: ''Reentrant Polygon Clipping.'' Communications of the ACM, vol. 17, ss.&nbsp;32–42, 1974

== Eksterne lenker ==
* [http://www.cs.drexel.edu/~david/Classes/CS430/Lectures/L-05_Polygons.6.pdf Polygonklipping og fylling] Beskriver algoritmen ved bruk av bilder som er enkle å forstå.

{{Autoritetsdata}}

[[Kategori:Datagrafikk]]
[[Kategori:Algoritmer]]