Vatti クリッピングアルゴリズム

Vattiクリッピングアルゴリズム^[1]はコンピュータグラフィックスで使用されています。任意の数の任意の形状のサブジェクトポリゴンを任意の数の任意の形状のクリップポリゴンでクリッピングできます。Sutherland -HodgmanやWeiler-Athertonポリゴンクリッピングアルゴリズムとは異なり、Vattiアルゴリズムはサブジェクトまたはクリップとして使用できるポリゴンの種類を制限しません。複雑な（自己交差する）ポリゴンや穴のあるポリゴンも処理できます。このアルゴリズムは一般に2D空間でのみ適用できます。

説明

クリッピングは、サブジェクトポリゴンとクリップポリゴンの相互作用として定義されます。クリッピングでは通常、サブジェクトポリゴンとクリップポリゴンの交差(重なり合う領域) を見つけますが、クリッピングアルゴリズムは他のブールクリッピング操作にも適用できます。differenceでは、クリッピングポリゴンによってサブジェクトから重なり合う領域が削除されます。unionでは、クリッピングによってサブジェクトポリゴンまたはクリップポリゴンのいずれかで覆われた領域が返されます。xorでは、クリッピングによって、サブジェクトポリゴンとクリップポリゴンの両方で覆われている領域を除き、サブジェクトポリゴンまたはクリップポリゴンのいずれかで覆われた領域が返されます。

Vatti アルゴリズムでは、対象ポリゴンエッジとクリッピングポリゴンエッジの両方を、最下部のエッジから始めて上部に向かって順番に処理します。これは概念的にはBentley-Ottmann アルゴリズムに似ています。このスイープラインアプローチでは、問題空間をスキャンラインで分割します。スキャンラインは、関係するポリゴンのすべての頂点を通過する仮想の水平線です。これらのスキャンラインは、スキャンビーム(隣接するスキャンライン間のスペース) の輪郭を描きます。これらのスキャンビームは、最下部のスキャンビームから順に処理され、アルゴリズムによってこれらのスキャンビーム内の交点がソリューションポリゴンに追加されます。

参照

参考文献

^ Bala R. Vatti. 「ポリゴンクリッピングの一般的なソリューション」、Communications of the ACM、Vol 35、Issue 7 (1992 年 7 月) pp. 56–63。

外部リンク

Clipper、Vatti アルゴリズムのオープンソースフリーウェア実装

[1] Bala R. Vatti. 「ポリゴンクリッピングの一般的なソリューション」、Communications of the ACM、Vol 35、Issue 7 (1992 年 7 月) pp. 56–63。