Algoritmo de Cyrus-Beck

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Ilustración del algoritmo de Cyrus-Beck.

El algoritmo de Cyrus-Beck es un algoritmo de recorte de líneas y polígonos convexos. De forma similar al algoritmo de Cohen-Sutherland también utiliza aristas extendidas. Se puede adaptar muy fácilmente entre rayos y polígonos convexos o segmentos y polígonos convexos.

Implementación del algoritmo de Cyrus-Beck en C#

internal sealed class CyrusBeckClipping : IClippingAlgorithm {
    private List<Vector2> _clipArea = new List<Vector2>();
    private List<Vector2> _normals = new List<Vector2>();

    public IEnumerable<Vector2> GetBoundingPolygon() {
        return _clipArea;
    }

    public void SetBoundingRectangle(Vector2 start, Vector2 end) {
        _clipArea.Clear();

        _clipArea.Add(start);
        _clipArea.Add(new Vector2(end.X, start.Y));
        _clipArea.Add(end);
        _clipArea.Add(new Vector2(start.X, end.Y));

        computeNormals();
    }

    public void SetBoundingPolygon(IEnumerable<Vector2> points) {
        _clipArea.Clear();
        _clipArea.AddRange(points);
        computeNormals();
    }

    private void computeNormals() {
        _normals.Clear();

        for (int i = 0; i < _clipArea.Count - 1; i++) {
            Vector2 direction = _clipArea[i + 1] - _clipArea[i];
            direction.Normalize();

            _normals.Add(new Vector2(-direction.Y, direction.X));
        }

        {
            Vector2 direction = _clipArea[0] - _clipArea[_clipArea.Count - 1];
            direction.Normalize();

            _normals.Add(new Vector2(-direction.Y, direction.X));
        }
    }

    public bool ClipLine(ref Line line) {
        Vector2 P = line.End - line.Start;
        float tMinimum = 0, tMaximum = 1;
        const float epsilon = 0.0001f;

        for (int i = 0; i < _clipArea.Count; i++) {
            Vector2 F = _clipArea[i];
            Vector2 N = _normals[i];
            Vector2 Q = line.Start - F;

            float Pn = Vector2.DotProduct(P, N);
            float Qn = Vector2.DotProduct(Q, N);

            if (Pn < epsilon && Pn > -epsilon) {
                if (Qn < 0) return false;
            }
            else {
                float computedT = -Qn / Pn;
                if (Pn < 0) {
                    if (computedT < tMinimum)
                        return false;
                    if (computedT < tMaximum)
                        tMaximum = computedT;
                }
                else {
                    if (computedT > tMaximum)
                        return false;
                    if (computedT > tMinimum)
                        tMinimum = computedT;
                }
            }
        }

        if (tMinimum < tMaximum) {
            if (tMaximum < 1)
                line.End = line.Start + tMaximum * P;

            if (tMinimum > 0)
                line.Start = line.Start + tMinimum * P;
        }
        else return false;

        return true;
    }

    public ClippingCapabilities Capabilities {
        get {
            return ClippingCapabilities.ConvexWindow |
                   ClippingCapabilities.RectangleWindow;
        }
    }

    public override string ToString() {
        return "Cyrus-Beck algorithm";
    }
}
// This code was implemented by Grishul Eugeny as part of preparation
// to exam in ITMO university