「サイラス・ベック・アルゴリズム」を編集中

サイラス・ベック・アルゴリズム（英語：Cyrus Beck algorithm）とは、コンピューターグラフィックスにおけるラインクリッピングのアルゴリズムである。

コーエン・サザーランド・アルゴリズムより効率的になるよう設計されている。
またコーエン・サザーランド・アルゴリズムは長方形のみなのに対して、サイラス・ベック・アルゴリズムは多角形にも適用できる。

== 詳細 ==
直線のパラメトリック方程式
:<math>
\begin{align}
\mathbf p(t) &= t \mathbf p_1 + (1 - t) \mathbf p_0\\
\end{align}
</math>
:<math> 0 \leq t \leq 1 </math>.

クリッピング領域との交点を見つけるために、領域の辺の法線（多角形を構成する直線の法線）と直線の内積を計算する。'''p'''<sub>''E''</sub> は多角形の頂点。 '''n'''は法線。
:<math>\mathbf n \cdot (\mathbf p(t) - \mathbf p_E)</math>

この値が、
* if < 0, 直線は内側になる。
* if = 0, 直線は平行である。
* if > 0, 直線は内側にない。

== 2Dでの実装例 ==
verticesからなる多角形と、point0とpoint1からなる直線に対して、
サイラスベックアルゴリズムを適用し、直線が多角形外であればnullを、多角形内であれば接点となる2点を返す。

<source lang="csharp">
public static Vector2[] CyrusBeck(Vector2[] vertices, Vector2 point0, Vector2 point1)
{
    // 引数チェック
    if (vertices == null || vertices.Length < 3)
    {
        throw new ArgumentException(nameof(vertices));
    }

    // 頂点数
    var vcount = vertices.Length;

    // 法線を計算
    var normal = new Vector2[vcount];

    for (int i = 0; i < vcount; i++)
    {
        normal[i].X = vertices[i].Y - vertices[(i + 1) % vcount].Y;
        normal[i].Y = vertices[(i + 1) % vcount].X - vertices[i].X;
    }

    // P1-P0を計算
    var p1p0 = point1 - point0;

    // P0-PEiを計算
    var p0pei = new Vector2[vcount];

    for (int i = 0; i < vcount; i++)
    {
        p0pei[i] = vertices[i] - point0;
    }

    // 分子と分母を計算
    var numerator = new float[vcount];
    var denominator = new float[vcount];

    for (int i = 0; i < vcount; i++)
    {
        numerator[i]   = Vector2.Dot(normal[i], p0pei[i]);
        denominator[i] = Vector2.Dot(normal[i], p1p0);
    }

    // enterとleavingを計算
    var t = new float[vcount];
    var tE = new List<float>();
    var tL = new List<float>();

    for (int i = 0; i < vcount; i++)
    {
        t[i] = numerator[i] / denominator[i];

        if (0 < denominator[i])
            tE.Add(t[i]);
        else
            tL.Add(t[i]);
    }
    tE.Add(0);
    tL.Add(1);

    var temp = new float[2];
    temp[0] = tE.Max();
    temp[1] = tL.Min();

    // 範囲外（外側）にあると思われる
    if (temp[1] < temp[0])
    {
        return null;
    }

    // 結果
    var result = new Vector2[2];
    result[0].X = point0.X + p1p0.X * temp[0];
    result[0].Y = point0.Y + p1p0.Y * temp[0];
    result[1].X = point0.X + p1p0.X * temp[1];
    result[1].Y = point0.Y + p1p0.Y * temp[1];
    return result;
}
</source>

== 関連項目 ==
* [[Cohen–Sutherland algorithm]]
* [[Liang–Barsky algorithm]]
* [[Nicholl–Lee–Nicholl algorithm]]
* [[Fast clipping]]

[[category: 2DCG]]
[[category: 3DCG]]