8,465
回編集
差分
ナビゲーションに移動
検索に移動
'''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> [[クリップスペース座標]]
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> [[クリップスペース座標]]
