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.

Basándonos en las siguientes ecuaciones:

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

Donde Δx= x₂-x₁ y Δy= y₂-y₁

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.

•   Datos: Q606795