Algoritmo de Liang-Barsky

En la gráfica realizada por ordenador, el algoritmo de Liang-Barsky (nombrado por You-Dong Liang y Brian A. Barsky) es un algoritmo de recorte de periódico de la línea. El algoritmo de Liang-Barsky usa la ecuación paramétrica de una línea y desigualdades que describen la variedad de la caja de recorte de periódico para determinar las intersecciones entre la línea y la caja de recorte de periódico. Con estas intersecciones sabe qué parte de la línea se debería dibujar. Este algoritmo es considerablemente más eficiente que Cohen–Sutherland.

La idea de Liang-Barsky que prende el algoritmo es hacer tantas pruebas como posible antes de intersecciones de la línea de calcular.

Considere primero la forma paramétrica habitual de una línea recta:

:

:

Un punto está en la ventana del clip, si

:

y

:,

que se puede expresar como las 4 desigualdades

:,

donde

: (dejado)

: (derecho)

: (fondo)

: (cumbre)

Calcular el segmento de línea final:

  1. Una línea paralela a un borde de la ventana de recorte de periódico tiene para ese límite.
  2. Si para esto,
  1. Cuando
  1. Para el distinto a cero, da el punto de la intersección.
  2. Para cada línea, cuente y. Puesto que mirada a límites para cual

Véase también

Los algoritmos usaron con el mismo objetivo:

Enlaces externos



Buscar