差分

ナビゲーションに移動 検索に移動

Cyrus Beckアルゴリズム

2,797 バイト追加, 2020年3月11日 (水) 06:50
ページの作成:「'''Cyrus Beck アルゴリズム'''とは、線分をポリゴンの範囲内にクリッピングするアルゴリズムである。 Cohen Sutherlandアル…」
'''Cyrus Beck アルゴリズム'''とは、線分を[[ポリゴン]]の範囲内に[[クリッピング]]する[[アルゴリズム]]である。

Cohen SutherlandアルゴリズムやNicholl Le Nichollアルゴリズムとは異なり、非矩形(=ポリゴン)のクリッピングが可能となっている。
==C#での実装例==
<source lang="csharp">
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;
}
}
</source>

== 関連項目 ==
<nowiki>*</nowiki> [[クリップスペース座標]]

案内メニュー