Cyrus-Beck algoritm

Cyrus -Beck-algoritmen ( eng. Cyrus-Beck ) är en algoritm för att skära av segment med en godtycklig konvex polygon . Det föreslogs som en mer effektiv ersättning för Cohen-Sutherland-algoritmen , som utför klippning i flera iterationer. [ett]

Beskrivning av algoritmen

Avskurna segment presenteras i en parametrisk form:

p(t)=p_{0}+t(p_{1}-p_{0}),t\in [0,1]

var

p 0 , p 1 är koordinaterna för början och slutet av segmentet, respektive, t är en parameter.

Varje skärsegment innehåller koordinaterna för början och slutet, samt två parametrar t A och t B som motsvarar början och slutet av segmentet.
För varje trunkerat segment P utförs följande åtgärder:

Kanterna på den skurna polygonen korsas moturs . För varje kant E beräknas parametern t E , som beskriver skärningspunkten mellan E och linjen som segmentet P ligger på . Den skalära produkten av vektorn E och det yttre normala N beräknas beroende på tecknet för vilken en av följande situationer inträffar:
- E · N < 0 — segmentet P är riktat från insidan till utsidan av kanten E . I detta fall ersätts parametern t A med t E om t E > t A .
- E · N > 0 — segmentet P är riktat från utsidan till insidan av kanten E . I detta fall ersätts parametern t B med t E om t E < t B .
- E · N = 0 — segmentet P är parallellt med kanten E . Segment P kasseras som osynligt om det är på höger sida av E .
Om t A t B är den del av segmentet P som anges av parametrarna t A och t B synlig. Annars är segment P helt osynligt. $\leq$

Beräkningskomplexitet

Se även

Liang-Barsky algoritm
Nicholl-Lee

Anteckningar

↑ "Klippning" (presentation) . Tillträdesdatum: 22 juni 2013. Arkiverad från originalet 4 mars 2016. (obestämd)

Länkar

Litteratur

Mike Cyrus, Jay Beck. "Generaliserad två- och tredimensionell klippning". Computers & Graphics, 1978: 23-28.
James D Foley Datorgrafik: principer och praxis . Addison-Wesley Professional, 1996. sid. 117.