Cyrus Beckアルゴリズム

Cyrus Beck アルゴリズムとは、線分をポリゴンの範囲内にクリッピングするアルゴリズムである。

Cohen SutherlandアルゴリズムやNicholl Le Nichollアルゴリズムとは異なり、非矩形（＝ポリゴン）のクリッピングが可能となっている。

C#での実装例

using System;
using System.Numerics;
using System.Collections.Generic;
using System.Linq;

public static class LineClipping
{
    public static Vector2[] CyrusBeck(Vector2[] vertices, Vector2[] line)
    {
        // 引数チェック
        if (vertices == null || vertices.Length < 3)
        {
            throw new ArgumentException(nameof(vertices));
        }

        if (line == null || line.Length < 2)
        {
            throw new ArgumentException(nameof(line));
        }

        // 頂点数
        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 = line[1] - line[0];

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

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

        // 分子と分母を計算
        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 = line[0].X + p1p0.X * temp[0];
        result[0].Y = line[0].Y + p1p0.Y * temp[0];
        result[1].X = line[0].X + p1p0.X * temp[1];
        result[1].Y = line[0].Y + p1p0.Y * temp[1];
        return result;
    }
}

関連項目

* クリップスペース座標