Algoritme de Liang-Barsky

El algoritme de Liang-Barsky és un algoritme de retallada de llínees similar al algoritme de Cohen-Sutherland. Usa l'equació paramètrica de la llínea i desigualtats descrivint el ranc de l'àrea de retallada per a determinar les interseccions entre la llínea i l'àrea de retallada. Va ser desenrollat per You-Dong Liang i Brian A. Barsky.

Basant-nos en les següents equacions:

x=x1 + oΔx
i=i1 + oΔi
0<=o<=1

A on Δx= x₂-x₁ i Δi= i₂-i₁

En estes interseccions se sap qué porció de la llínea deuria ser dibuixada. Este algoritme és significativament més eficient que el de Cohen-Sutherland.

Implementació en C# de l'algoritme de Liang-Barsky

internal sealed class LiangBarskyClipping : IClippingAlgorithm {
    private Vector2 _clipMin, _clipMax;

    public IEnumerable<Vector2> GetBoundingPolygon() {
        yield return _clipMin;
        yield return new Vector2(_clipMax.X, _clipMin.I);
        yield return _clipMax;
        yield return new Vector2(_clipMin.X, _clipMax.I);
    }

    public void SetBoundingRectangle(Vector2 start, Vector2 end) {
        _clipMin = start;
        _clipMax = end;
    }

    public void SetBoundingPolygon(IEnumerable<Vector2> points) {
        throw new NotSupportedException("see Capabilities =)");
    }

    private delegate bool ClippingHandler(float p, float q);

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

        ClippingHandler pqClip = delegate(float directedProjection,
                                          float directedDistance) {
            if (directedProjection == 0) {
                if (directedDistance < 0) return false;
            }
            else {
                float amount = directedDistance / directedProjection;
                if (directedProjection < 0) {
                    if (amount > tMaximum) return false;
                    else if (amount > tMinimum) tMinimum = amount;
                }
                else {
                    if (amount < tMinimum) return false;
                    else if (amount < tMaximum) tMaximum = amount;
                }
            }
            return true;
        };

        if (pqClip(-P.X, line.Start.X - _clipMin.X)) {
            if (pqClip(P.X, _clipMax.X - line.Start.X)) {
                if (pqClip(-P.Y, line.Start.I - _clipMin.I)) {
                    if (pqClip(P.Y, _clipMax.I - line.Start.I)) {
                        if (tMaximum < 1) {
                            line.End.X = line.Start.X + tMaximum * P.X;
                            line.End.I = line.Start.I + tMaximum * P.Y;
                        }
                        if (tMinimum > 0) {
                            line.Start.X += tMinimum * P.X;
                            line.Start.I += tMinimum * P.Y;
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }

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

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

Adaptació a retallada de polígons

S'amplia en un plantejament similar el del método Sutherland-Hodgman. Les representacions paramètriques de llínees s'utilisen per a processar les arestes dels polígons en orde al voltant del perímetro del polígon utilisant procediments de prova similars a aquells que s'ampren en la retallada de llínees.

Vore també

• Cohen-Sutherland, algoritme per a retallada de llínees.
• Cyrus-Beck, algoritme per a retallada de llínees.
• Fast-Clipping, algoritme per a retallada de llínees.
• Nicholl-Lee-Nicholl, algoritme per a retallada de llínees.
• Sutherland-Hodgman, algoritme per a retallada de llínees i polígons.
• Weiler-Atherton, algoritme per a retallada de llínees i polígons.
• Retallada de Polígons, algoritmes de retallada de polígons.