Liang–Barskyアルゴリズム

コンピュータグラフィックスにおいて、Liang–Barskyアルゴリズム（ You-Dong LiangとBrian A. Barskyにちなんで命名）は、 1984年初頭に初めて発表された線分クリッピングアルゴリズムです。Liang–Barskyアルゴリズムは、線分の媒介変数表示とクリッピングウィンドウの範囲を表す不等式を用いて、線分とクリッピングウィンドウの交点を決定します。これらの交点によって、線分のどの部分を描画すべきかが分かります。そのため、このアルゴリズムは Cohen–Sutherlandアルゴリズムよりもはるかに効率的です。Liang–Barskyクリッピングアルゴリズムの基本的な考え方は、線分の交点を計算する前に、できるだけ多くのテストを行うことです。

このアルゴリズムは直線のパラメトリック表現を使用します。

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

y=y_{0}+t(y_{1}-y_{0})=y_{0}+t\デルタ y.

ポイントがクリップウィンドウ内にある場合、

x_{\text{min}}\leq x_{0}+t\Delta x\leq x_{\text{max}}

そして

y_{\text{min}}\leq y_{0}+t\Delta y\leq y_{\text{max}},

これは4つの不等式として表現できる。

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

どこ

{\begin{aligned}p_{1}&=-\Delta x,&q_{1}&=x_{0}-x_{\text{min}},&&{\text{(left)}}\\p_{2}&=\Delta x,&q_{2}&=x_{\text{max}}-x_{0},&&{\text{(right)}}\\p_{3}&=-\Delta y,&q_{3}&=y_{0}-y_{\text{min}},&&{\text{(bottom)}}\\p_{4}&=\Delta y,&q_{4}&=y_{\text{max}}-y_{0}.&&{\text{(top)}}\end{aligned}}

最終的な線分を計算するには：

クリッピングウィンドウの端に平行な線は $p_{i}=0$ その境界線に関して。
もしそれが $i$ 、 $q_{i}<0$ そうすれば、その線は完全に外側にあるため、削除できます。
いつ $p_{i}<0$ 線はクリップウィンドウの外側から内側に進み、 $p_{i}>0$ 線は内側から外側へと進む。
ゼロ以外の場合 $p_{i}$ 、 $u=q_{i}/p_{i}}$ 与える $t$ 線と窓の端（投影されている場合も含む）の交点。
線と窓の端との実際の交点（存在する場合）は、次のように記述されます。 $u_1$ そして $u2$ 以下のように計算されます。 $u_1$ 境界を見て $p_{i}<0$ （つまり、外側から内側へ）。 $u_1$ 最大になる $\{0,q_{i}/p_{i}\}$ 。のために $u2$ 境界を見て $p_{i}>0$ （つまり内側から外側へ）。 $u2$ 最低限 $\{1,q_{i}/p_{i}\}$ 。
もし $u_1>u_2$ 線が完全にクリップウィンドウの外にある場合。 $u_{1}<0<1<u_{2}$ それは完全にその中に含まれています。

// Liang–Barsky 線切りアルゴリズム#include <iostream> #include <graphics.h> #include <math.h>using namespace std ;// この関数は最大値を返しますfloat maxi ( float arr [], int n ) { float m = 0 ; for ( int i = 0 ; i < n ; ++ i ) if ( m < arr [ i ]) m = arr [ i ]; return m ; }// この関数は最小のfloat mini ( float arr [], int n ) { float m = 1 ; for ( int i = 0 ; i < n ; ++ i ) if ( m > arr [ i ]) m = arr [ i ]; return m ; }void liang_barsky_clipper ( float xmin , float ymin , float xmax , float ymax , float x1 , float y1 , float x2 , float y2 ) { // 変数の定義float p1 = - ( x2 - x1 ); float p2 = - p1 ; float p3 = - ( y2 - y1 ); float p4 = - p3 ;float q1 = x1 - xmin ; float q2 = xmax - x1 ; float q3 = y1 - ymin ; float q4 = ymax - y1 ;float exitParams [ 5 ], entryParams [ 5 ]; int exitIndex = 1 , entryIndex = 1 ; exitParams [ 0 ] = 1 ; entryParams [ 0 ] = 0 ;rectangle ( xmin , ymin , xmax , ymax ); // クリッピングウィンドウを描画if (( p1 == 0 && q1 < 0 ) || ( p2 == 0 && q2 < 0 ) || ( p3 == 0 && q3 < 0 ) || ( p4 == 0 && q4 < 0 )) { outtextxy ( 80 , 80 , "Line is parallel to clipping window!" ); return ; } if ( p1 != 0 ) { float r1 = q1 / p1 ; float r2 = q2 / p2 ; if ( p1 < 0 ) { entryParams [ entryIndex ++ ] = r1 ; exitParams [ exitIndex ++ ] = r2 ; } else { entryParams [ entryIndex ++ ] = r2 ; exitParams [ exitIndex ++ ] = r1 ; } } if ( p3 != 0 ) { float r3 = q3 / p3 ; float r4 = q4 / p4 ; if ( p3 < 0 ) { entryParams [ entryIndex ++ ] = r3 ; exitParams [ exitIndex ++ ] = r4 ; } else { entryParams [ entryIndex ++ ] = r4 ; exitParams [ exitIndex ++ ] = r3 ; } }float clippedX1 , clippedY1 , clippedX2 , clippedY2 ; float u1 , u2 ; u1 = maxi ( entryParams , entryIndex ); // エントリーポイントの最大値u2 = mini ( exitParams , exitIndex ); // 出口ポイントの最小値if ( u1 > u2 ) { outtextxy ( 80 , 80 , "線がクリッピングウィンドウの外にあります！" ); return ; }clippedX1 = x1 + ( x2 - x1 ) * u1 ; clippedY1 = y1 + ( y2 - y1 ) * u1 ; clippedX2 = x1 + ( x2 - x1 ) * u2 ; clippedY2 = y1 + ( y2 - y1 ) * u2 ;setcolor ( CYAN ); line ( clippedX1 , clippedY1 , clippedX2 , clippedY2 ); // 切り取られたセグメントを描画setlinestyle ( 1 , 1 , 0 ); line ( x1 , y1 , clippedX1 , clippedY1 ); // 元の開始位置からクリップされた開始位置までline ( x2 , y2 , clippedX2 , clippedY2 ); // 元終了位置からクリップされた終了位置まで}int main () { cout << " \n Liang-Barsky ライン クリッピング" ; cout << " \nシステム ウィンドウのレイアウトは、左下が (0,0)、右上が (631, 467) です" ; cout << " \nウィンドウの座標 (xmin, ymin, xmax, ymax) を入力してください: " ; float xmin , ymin , xmax , ymax ; cin >> xmin >> ymin >> xmax >> ymax ;cout << " \n線分 (x1, y1) と (x2, y2) の端点を入力してください: " ; float x1 , y1 , x2 , y2 ; cin >> x1 >> y1 >> x2 >> y2 ;int gd = DETECT , gm ; initgraph ( & gd , & gm , "" ); // winbgimを使用liang_barsky_clipper ( xmin , ymin , xmax , ymax , x1 , y1 , x2 , y2 ); getch (); closegraph (); }

参考文献

Liang, YD、および Barsky, B.、「線分クリッピングのための新しい概念と方法」、ACM Transactions on Graphics、3(1):1–22、1984 年 1 月。
Liang, YD、BA、Barsky、およびM. Slater、「パラメトリック線クリッピングアルゴリズムのいくつかの改良」、CSD-92-688、コンピュータサイエンス部門、カリフォルニア大学バークレー校、1992年。
ジェームズ・D・フォーリー著『コンピュータグラフィックス：原理と実践』アディソン・ウェスリー・プロフェッショナル、1996年、117ページ。

外部リンク

https://hinjang.com/articles/04.html#eight
Skytopia：Liang-Barsky線分クリッピングアルゴリズムの概要！

Liang–Barskyアルゴリズム

関連項目

参考文献

外部リンク

関連するトピック

コンピュータグラフィックス

You-Dong Liang

Brian A. Barsky

線分クリッピング