Algoritmo de Sutherland-Hodgman

El algoritmo Sutherland-Hodgman es un algoritmo que se utiliza para recortar polígonos. Funciona extendiendo cada línea del polígono de recorte convexo por turno y seleccionando solo los vértices del polígono objeto que se encuentren en el lado visible.

El algoritmo comienza con una lista de entrada de todos los vértices del polígono de referencia. A continuación, se extiende un lado del polígono de recorte infinitamente en ambas direcciones y se recorre la ruta del polígono de referencia. Los vértices de la lista de entrada se insertan en una lista de salida si se encuentran en el lado visible de la línea del polígono de recorte extendida y se agregan nuevos vértices a la lista de salida donde la ruta del polígono de referencia cruza la línea del polígono de recorte extendida.

Este proceso se repite iterativamente para cada lado del polígono de recorte, utilizando la lista de salida de una etapa como lista de entrada para la siguiente. Una vez que se han procesado todos los lados del polígono de recorte, la lista final generada de vértices define un nuevo polígono único que es completamente visible. Tenga en cuenta que si el polígono en cuestión era cóncavo en los vértices fuera del polígono de recorte, el nuevo polígono puede tener bordes coincidentes (es decir, superpuestos); esto es aceptable para la representación, pero no para otras aplicaciones, como el cálculo de sombras.

El algoritmo Weiler-Atherton supera este problema al devolver un conjunto de polígonos divididos, pero es más complejo y computacionalmente más costoso, por lo que Sutherland-Hodgman se utiliza para muchas aplicaciones de renderizado. Sutherland-Hodgman también se puede extender al espacio 3D al recortar las rutas de los polígonos en función de los límites de los planos definidos por el espacio de visualización.

Dada una lista de aristas en un polígono de recorte y una lista de vértices en un polígono sujeto, el siguiente procedimiento recorta el polígono sujeto contra el polígono de recorte.

Producto de la lista Lista = temaPolígono;

para (Edge clipEdge en clipPolygon) doList inputList = salida Lista;
outputList.clear();

 para (int i = 0; i) 1) doPoint current_point = inputList[i];
Point prev_point = inputList[(i −1) % inputList.count];

Punto Intersecting_point = ComputeIntersection(prev_point, current_point, clipEdge)

 si (current_punto dentro clipEdge) entonces si (prev_point not inside clipEdge) entoncesoutputList.add(Intersecting_point);
 terminar sioutputList.add(current_point);

 si (prev_punto dentro clipEdge) entoncesoutputList.add(Intersecting_point);
 terminar si hechohecho

Los vértices del polígono recortado se encuentran en outputList cuando finaliza el algoritmo. Tenga en cuenta que un punto se define como dentro de un borde si se encuentra en el mismo lado del borde que el resto del polígono. Si los vértices del polígono recortado se enumeran de manera consistente en sentido antihorario, esto es equivalente a probar si el punto se encuentra a la izquierda de la línea (izquierda significa dentro, mientras que derecha significa fuera), y se puede implementar simplemente utilizando un producto vectorial.

ComputeIntersection es una función, omitida aquí para mayor claridad, que devuelve la intersección de un segmento de línea y una arista infinita. Tenga en cuenta que el punto de intersección solo se agrega a la lista de salida cuando se sabe que existe la intersección, por lo tanto, ambas líneas siempre se pueden tratar como infinitamente largas.

Puede encontrar una implementación de Python de Sutherland-Hodgman aquí.

Otros algoritmos de recorte de polígonos:

• Weiler–Atherton clipping algoritmo
• algoritmo de clipping

Sobre el tema del recorte:

• Clipping (gráficos de ordenador)
• Clipping (en rasterización)
• algoritmos de clipping de línea

• Mel Slater, Anthony Steed, Yiorgos Chrysanthou: Computación gráfica y entornos virtuales: del realismo al tiempo real. Addison Wesley, 2002. ISBN 0-201-62420-6.
• Ivan Sutherland, Gary W. Hodgman: Reentrant Polygon Clipping. Communications of the ACM, vol. 17, pp. 32–42, 1974

• Polygon clipping and fill Describe el algoritmo usando imágenes que son fáciles de entender.
• Rosetta Ejemplo de código