Algoritmo de Liang-Barsky

Algoritmo de Liang-Barsky

El algoritmo de Liang-Barsky es un algoritmo de recorte de líneas similar al algoritmo de Cohen-Sutherland. Usa la ecuación paramétrica de la línea y desigualdades describiendo el rango del área de recorte para determinar las intersecciones entre la línea y el área de recorte. Fue desarrollado por You-Dong Liang y Brian A. Barsky.

Basandonos en las siguientes ecuaciones:

x=x1 + uΔx
y=y1 + uΔy
0<=u<=1

Donde Δx= x2-x1 y Δy= y2-y1

Con estas intersecciones se sabe qué porción de la línea debería ser dibujada. Este algoritmo es significativamente más eficiente que el de Cohen-Sutherland.

Implementación en C# del algoritmo 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.Y);
        yield return _clipMax;
        yield return new Vector2(_clipMin.X, _clipMax.Y);
    }
 
    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.Y - _clipMin.Y)) {
                    if (pqClip(P.Y, _clipMax.Y - line.Start.Y)) {
                        if (tMaximum < 1) {
                            line.End.X = line.Start.X + tMaximum * P.X;
                            line.End.Y = line.Start.Y + tMaximum * P.Y;
                        }
                        if (tMinimum > 0) {
                            line.Start.X += tMinimum * P.X;
                            line.Start.Y += 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ón a recorte de polígonos

Se amplía con un planteamiento similar el del método Sutherland-Hodgman. Las representaciones paramétricas de líneas se utilizan para procesar las aristas de los polígonos en orden alrededor del perímetro del polígono utilizando procedimientos de prueba similares a aquellos que se emplean en el recorte de líneas.

Véase también

  • Cohen-Sutherland, algoritmo para recorte de líneas.
  • Cyrus-Beck, algoritmo para recorte de líneas.
  • Fast-Clipping, algoritmo para recorte de líneas.
  • Nicholl-Lee-Nicholl, algoritmo para recorte de líneas.
  • Sutherland-Hodgman, algoritmo para recorte de líneas y polígonos.
  • Weiler-Atherton, algoritmo para recorte de líneas y polígonos.
  • Recorte de Polígonos, algoritmos de recorte de polígonos.

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Algoritmo de Cohen-Sutherland — El algoritmo de Cohen Sutherland es un algoritmo de recorte de líneas usado en gráficos por computadora. Fue desarrollado por Danny Cohen e Ivan Sutherland en 1967. Contenido 1 Introducción 2 Funcionamiento 2.1 Códigos de frontera …   Wikipedia Español

  • Algoritmo de Sutherland-Hodgman — Sutherland Hodgman Empezando por el conjunto inicial de vertices del polígono, primero recorta el poligono contra una frontera para producir una nueva secuencia de vertices, con esta nueva secuencia se recorta contra otra frontera y así… …   Wikipedia Español

  • Algoritmo de Weiler-Atherton — Contenido 1 Recorte de polígonos de Weiler 2 Recorte de polígonos de Weiler Atherton 3 Véase también 4 Referencias …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”