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 en cuestión que se encuentran 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 renderización, pero no para otras aplicaciones, como el cálculo de sombras.
El algoritmo Weiler-Atherton soluciona este problema devolviendo 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 recortando 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.
Lista salidaList = subjectPolygon; para (Borde clipEdge en clipPolygon) hacer Lista listaDeEntrada = ListaDeSalida; salidaList.clear(); para (int i = 0; i < inputList.count; i += 1) hacer Punto current_point = listaDeEntrada[i]; Punto prev_point = inputList[(i − 1) % inputList.count]; Punto que se cruza = ComputeIntersection(punto anterior, punto actual, clipEdge) si (punto actual dentro de clipEdge) entonces si (punto anterior no dentro de clipEdge) entonces outputList.add(Punto_de_intersección); terminar si outputList.add(punto_actual); De lo contrario, si (prev_point dentro de clipEdge), entonces outputList.add(Punto_de_intersección); terminar si hecho, hecho
Los vértices del polígono recortado se encuentran en outputList cuando el algoritmo termina. 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.
Una implementación Python de Sutherland-Hodgman se puede encontrar aquí.
Otros algoritmos de recorte de polígonos:
Sobre el tema del recorte: