Algoritmus Liang – Barsky - Liang–Barsky algorithm - Wikipedia

v počítačová grafika, Algoritmus Liang – Barsky (pojmenoval podle Ty-Dong Liang a Brian A. Barsky ) je oříznutí čáry algoritmus. Algoritmus Liang – Barsky používá k určení průsečíků mezi přímkou ​​a rovnicí parametrickou rovnici přímky a nerovnosti popisující rozsah ořezového okna. klip okno. S těmito křižovatkami ví, která část čáry by měla být nakreslena. Tento algoritmus je výrazně účinnější než Cohen – Sutherland. Myšlenkou ořezového algoritmu Liang – Barsky je udělat co nejvíce testování před výpočtem liniových průsečíků.

Zvažte nejprve obvyklou parametrickou formu přímky:

${ displaystyle x = x_ {0} + t (x_ {1} -x_ {0}) = x_ {0} + t Delta x,}$

${ displaystyle y = y_ {0} + t (y_ {1} -y_ {0}) = y_ {0} + t Delta y.}$

Bod je v okně klipu, pokud

${ displaystyle x _ { text {min}} leq x_ {0} + t Delta x leq x _ { text {max}}}$

a

${ displaystyle y _ { text {min}} leq y_ {0} + t Delta y leq y _ { text {max}},}$

což lze vyjádřit jako 4 nerovnosti

${ displaystyle tp_ {i} leq q_ {i}, quad i = 1,2,3,4,}$

kde

${ displaystyle { begin {aligned} p_ {1} & = - Delta x, & q_ {1} & = x_ {0} -x _ { text {min}}, && { text {(vlevo)}} p_ {2} & = Delta x, & q_ {2} & = x _ { text {max}} - x_ {0}, && { text {(vpravo)}} p_ {3} & = - Delta y, & q_ {3} & = y_ {0} -y _ { text {min}}, && { text {(dole)}} p_ {4} & = Delta y, & q_ {4 } & = y _ { text {max}} - y_ {0}. && { text {(nahoře)}} end {zarovnáno}}}$

Výpočet posledního úsečky:

1. Čára rovnoběžná s hranou ořezového okna má ${ displaystyle p_ {i} = 0}$ pro tu hranici.
2. Pokud k tomu ${ displaystyle i}$, ${ displaystyle q_ {i} <0}$, pak je linka úplně venku a může být odstraněna.
3. Když ${ displaystyle p_ {i} <0}$, čára pokračuje ven dovnitř okna klipu a kdy ${ displaystyle p_ {i}> 0}$, linka pokračuje dovnitř ven.
4. Pro nenulovou hodnotu ${ displaystyle p_ {i}}$, ${ displaystyle u = q_ {i} / p_ {i}}$ dává průsečík.
5. Pro každý řádek vypočítat ${ displaystyle u_ {1}}$ a ${ displaystyle u_ {2}}$. Pro ${ displaystyle u_ {1}}$, podívejte se na hranice, pro které ${ displaystyle p_ {i} <0}$ (tj. zvenčí dovnitř). Vzít ${ displaystyle u_ {1}}$ být největší mezi ${ displaystyle {0, q_ {i} / p_ {i} }}$. Pro ${ displaystyle u_ {2}}$, podívejte se na hranice, pro které ${ displaystyle p_ {i}> 0}$ (tj. zevnitř ven). Vzít ${ displaystyle u_ {2}}$ být minimem ${ displaystyle {1, q_ {i} / p_ {i} }}$. Li ${ displaystyle u_ {1}> u_ {2}}$, linka je venku, a proto byla zamítnuta.

// Liang - Barskyho algoritmus ořezávání řádků#zahrnout<iostream>#zahrnout<graphics.h>#zahrnout<math.h>použitím jmenný prostor std;// tato funkce dává maximumplovák max(plovák přílet[],int n) {  plovák m = 0;  pro (int i = 0; i < n; ++i)    -li (m < přílet[i])      m = přílet[i];  vrátit se m;}// tato funkce udává minimumplovák mini(plovák přílet[], int n) {  plovák m = 1;  pro (int i = 0; i < n; ++i)    -li (m > přílet[i])      m = přílet[i];  vrátit se m;}prázdnota liang_barsky_clipper(plovák xmin, plovák ymin, plovák xmax, plovák ymax,                          plovák x1, plovák y1, plovák x2, plovák y2) {  // definování proměnných  plovák p1 = -(x2 - x1);  plovák p2 = -p1;  plovák p3 = -(y2 - y1);  plovák p4 = -p3;  plovák q1 = x1 - xmin;  plovák q2 = xmax - x1;  plovák q3 = y1 - ymin;  plovák q4 = ymax - y1;  plovák posarr[5], negarr[5];  int posind = 1, negind = 1;  posarr[0] = 1;  negarr[0] = 0;  obdélník(xmin, ymin, xmax, ymax); // kreslení ořezového okna  -li ((p1 == 0 && q1 < 0) || (p2 == 0 && q2 < 0) || (p3 == 0 && q3 < 0) || (p4 == 0 && q4 < 0)) {      outtextxy(80, 80, "Čára je rovnoběžná s ořezovým oknem!");      vrátit se;  }  -li (p1 != 0) {    plovák R1 = q1 / p1;    plovák r2 = q2 / p2;    -li (p1 < 0) {      negarr[negind++] = R1; // pro záporný p1, přidejte jej do záporného pole      posarr[posind++] = r2; // a přidejte p2 do pozitivního pole    } jiný {      negarr[negind++] = r2;      posarr[posind++] = R1;    }  }  -li (p3 != 0) {    plovák r3 = q3 / p3;    plovák r4 = q4 / p4;    -li (p3 < 0) {      negarr[negind++] = r3;      posarr[posind++] = r4;    } jiný {      negarr[negind++] = r4;      posarr[posind++] = r3;    }  }  plovák xn1, yn1, xn2, yn2;  plovák rn1, RN2;  rn1 = max(negarr, negind); // maximum záporného pole  RN2 = mini(posarr, posind); // minimum kladného pole  -li (rn1 > RN2)  { // odmítnout    outtextxy(80, 80, „Linka je mimo ořezové okno!“);    vrátit se;  }  xn1 = x1 + p2 * rn1;  yn1 = y1 + p4 * rn1; // výpočet nových bodů  xn2 = x1 + p2 * RN2;  yn2 = y1 + p4 * RN2;  setcolor(TYRKYSOVÁ);  čára(xn1, yn1, xn2, yn2); // kreslení nového řádku  setlinestyle(1, 1, 0);  čára(x1, y1, xn1, yn1);  čára(x2, y2, xn2, yn2);}int hlavní() {  cout << " nOříznutí čáry Liang-Barsky ";  cout << " nVýdaje systémového okna jsou: (0,0) vlevo dole a (631, 467) vpravo nahoře ";  cout << " nZadejte souřadnice okna (wxmin, wxmax, wymin, wymax): ";  plovák xmin, xmax, ymin, ymax;  cin >> xmin >> ymin >> xmax >> ymax;  cout << " nZadejte koncové body úsečky (x1, y1) a (x2, y2): ";  plovák x1, y1, x2, y2;  cin >> x1 >> y1 >> x2 >> y2;  int gd = ZJISTIT, gm;  // použití knihovny winbgim pro C ++, inicializace grafického režimu  Initgraph(&gd, &gm, "");  liang_barsky_clipper(xmin, ymin, xmax, ymax, x1, y1, x2, y2);  getch();  closegraph();}

Viz také

Algoritmy použité pro stejný účel:

• Cyrus-Beckův algoritmus
• Algoritmus Nicholl – Lee – Nicholl
• Rychlé ořezávání

Reference

• Liang, Y. D. a Barsky, B., "Nový koncept a metoda ořezávání čar ", Transakce ACM v grafice, 3 (1): 1–22, leden 1984.
• Liang, Y. D., B. A., Barsky a M. Slater, Některá vylepšení parametrického algoritmu oříznutí čáry, CSD-92-688, divize počítačové vědy, University of California, Berkeley, 1992.
• James D. Foley. Počítačová grafika: principy a praxe. Addison-Wesley Professional, 1996. str. 117.

externí odkazy

• http://hinjang.com/articles/04.html#eight
• Skytopia: Algoritmus ořezu čáry Liang-Barsky v kostce!