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;
}
}
C++での実装例
// C++ Program to implement Cyrus Beck
#include <SFML/Graphics.hpp>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
using namespace sf;
// Function to draw a line in SFML
void drawline(RenderWindow* window, pair<int, int> p0, pair<int, int> p1)
{
Vertex line[] = {
Vertex(Vector2f(p0.first, p0.second)),
Vertex(Vector2f(p1.first, p1.second))
};
window->draw(line, 2, Lines);
}
// Function to draw a polygon, given vertices
void drawPolygon(RenderWindow* window, pair<int, int> vertices[], int n)
{
for (int i = 0; i < n - 1; i++)
drawline(window, vertices[i], vertices[i + 1]);
drawline(window, vertices[0], vertices[n - 1]);
}
// Function to take dot product
int dot(pair<int, int> p0, pair<int, int> p1)
{
return p0.first * p1.first + p0.second * p1.second;
}
// Function to calculate the max from a vector of floats
float max(vector<float> t)
{
float maximum = INT_MIN;
for (int i = 0; i < t.size(); i++)
if (t[i] > maximum)
maximum = t[i];
return maximum;
}
// Function to calculate the min from a vector of floats
float min(vector<float> t)
{
float minimum = INT_MAX;
for (int i = 0; i < t.size(); i++)
if (t[i] < minimum)
minimum = t[i];
return minimum;
}
// Cyrus Beck function, returns a pair of values
// that are then displayed as a line
pair<int, int>* CyrusBeck(pair<int, int> vertices[],
pair<int, int> line[], int n)
{
// Temporary holder value that will be returned
pair<int, int>* newPair = new pair<int, int>[2];
// Normals initialized dynamically(can do it statically also, doesn't matter)
pair<int, int>* normal = new pair<int, int>[n];
// Calculating the normals
for (int i = 0; i < n; i++) {
normal[i].second = vertices[(i + 1) % n].first - vertices[i].first;
normal[i].first = vertices[i].second - vertices[(i + 1) % n].second;
}
// Calculating P1 - P0
pair<int, int> P1_P0
= make_pair(line[1].first - line[0].first,
line[1].second - line[0].second);
// Initializing all values of P0 - PEi
pair<int, int>* P0_PEi = new pair<int, int>[n];
// Calculating the values of P0 - PEi for all edges
for (int i = 0; i < n; i++) {
// Calculating PEi - P0, so that the
// denominator won't have to multiply by -1
P0_PEi[i].first
= vertices[i].first - line[0].first;
// while calculating 't'
P0_PEi[i].second = vertices[i].second - line[0].second;
cout << P0_PEi[i].first << "," << P0_PEi[i].second <<endl;
}
cout << endl;
int *numerator = new int[n], *denominator = new int[n];
// Calculating the numerator and denominators
// using the dot function
for (int i = 0; i < n; i++) {
numerator[i] = dot(normal[i], P0_PEi[i]);
denominator[i] = dot(normal[i], P1_P0);
cout << numerator[i] << "," << denominator[i] << endl;
}
cout << endl;
// Initializing the 't' values dynamically
float* t = new float[n];
// Making two vectors called 't entering'
// and 't leaving' to group the 't's
// according to their denominators
vector<float> tE, tL;
// Calculating 't' and grouping them accordingly
for (int i = 0; i < n; i++) {
t[i] = (float)(numerator[i]) / (float)(denominator[i]);
cout << t[i] << endl;
if (denominator[i] > 0)
tE.push_back(t[i]);
else
tL.push_back(t[i]);
}
cout << endl;
// Initializing the final two values of 't'
float temp[2];
// Taking the max of all 'tE' and 0, so pushing 0
tE.push_back(0.f);
temp[0] = max(tE);
// Taking the min of all 'tL' and 1, so pushing 1
tL.push_back(1.f);
temp[1] = min(tL);
// Entering 't' value cannot be
// greater than exiting 't' value,
// hence, this is the case when the line
// is completely outside
if (temp[0] > temp[1]) {
newPair[0] = make_pair(-1, -1);
newPair[1] = make_pair(-1, -1);
return newPair;
}
// Calculating the coordinates in terms of x and y
newPair[0].first = (float)line[0].first + (float)P1_P0.first * (float)temp[0];
newPair[0].second = (float)line[0].second + (float)P1_P0.second * (float)temp[0];
newPair[1].first = (float)line[0].first + (float)P1_P0.first * (float)temp[1];
newPair[1].second = (float)line[0].second + (float)P1_P0.second * (float)temp[1];
cout << '(' << newPair[0].first << ", "
<< newPair[0].second << ") ("
<< newPair[1].first << ", "
<< newPair[1].second << ")";
return newPair;
}
// Driver code
int main()
{
// Setting up a window and loop
// and the vertices of the polygon and line
RenderWindow window(VideoMode(500, 500), "Cyrus Beck");
pair<int, int> vertices[]
= { make_pair(200, 50),
make_pair(250, 100),
make_pair(200, 150),
make_pair(100, 150),
make_pair(50, 100),
make_pair(100, 50) };
// Make sure that the vertices
// are put in a clockwise order
int n = sizeof(vertices) / sizeof(vertices[0]);
pair<int, int> line[] = { make_pair(10, 10), make_pair(450, 200) };
pair<int, int>* temp1 = CyrusBeck(vertices, line, n);
pair<int, int> temp2[2];
temp2[0] = line[0];
temp2[1] = line[1];
// To allow clipping and unclipping
// of the line by just pressing a key
bool trigger = false;
while (window.isOpen()) {
window.clear();
Event event;
if (window.pollEvent(event)) {
if (event.type == Event::Closed)
window.close();
if (event.type == Event::KeyPressed)
trigger = !trigger;
}
drawPolygon(&window, vertices, n);
// Using the trigger value to clip
// and unclip a line
if (trigger) {
line[0] = temp1[0];
line[1] = temp1[1];
}
else {
line[0] = temp2[0];
line[1] = temp2[1];
}
drawline(&window, line[0], line[1]);
window.display();
}
return 0;
}
brew install sfml
c++ cyrusbeck.cpp -o cyrusbeck -lsfml-window -lsfml-graphics -lsfml-system