Algoritmul Cyrus-Beck

Algoritmul Cyrus-Beck ( ing. Cyrus-Beck ) este un algoritm pentru tăierea segmentelor printr-un poligon convex arbitrar . A fost propus ca un înlocuitor mai eficient pentru algoritmul Cohen-Sutherland , care realizează tăierea în mai multe iterații. [unu]

Descrierea algoritmului

Segmentele tăiate sunt prezentate într-o formă parametrică:

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

Unde

p 0 , p 1 sunt coordonatele începutului și, respectiv, sfârșitului segmentului, t este un parametru.

Fiecare segment tăiat conține coordonatele începutului și sfârșitului, precum și doi parametri t A și t B corespunzători începutului și sfârșitului segmentului.
Pentru fiecare segment trunchiat P se efectuează următoarele acțiuni:

Marginile poligonului tăiat sunt parcurse în sens invers acelor de ceasornic . Pentru fiecare muchie E se calculeaza parametrul t E , care descrie intersectia lui E cu dreapta pe care se afla segmentul P . Produsul scalar al vectorului E și normala exterioară N se calculează , în funcție de semnul căruia apare una din următoarele situații:
- E · N < 0 — segmentul P este îndreptat dinspre interior spre exteriorul muchiei E . În acest caz, parametrul t A este înlocuit cu t E dacă t E > t A .
- E · N > 0 — segmentul P este îndreptat dinspre exterior spre interiorul muchiei E . În acest caz, parametrul t B este înlocuit cu t E dacă t E < t B .
- E · N = 0 — segmentul P este paralel cu muchia E . Segmentul P este aruncat ca invizibil dacă se află în partea dreaptă a lui E.
Dacă t A t B , atunci partea de segment P specificată de parametrii t A și t B este vizibilă. În caz contrar, segmentul P este complet invizibil. $\leq$

Complexitate computațională

Vezi și

Algoritmul Liang-Barsky
Nicholl-Lee

Note

↑ „Clipping” (prezentare) . Data accesului: 22 iunie 2013. Arhivat din original pe 4 martie 2016. (nedefinit)

Link -uri

Literatură

Mike Cyrus, Jay Beck. „Tăiere generalizată în două și trei dimensiuni”. Computers & Graphics, 1978: 23-28.
James D Foley Grafica pe computer: principii și practică . Addison-Wesley Professional, 1996. p. 117.