El algoritmo de Sutherland-Hodgman es un algoritmo utilizado para recortar polígonos . Funciona extendiendo cada línea del polígono de clip convexo por turno y seleccionando solo los vértices del polígono en cuestión que están en el lado visible.
El algoritmo comienza con una lista de entrada de todos los vértices del polígono en cuestión. A continuación, un lado del polígono de recorte se extiende infinitamente en ambas direcciones y se recorre la ruta del polígono en cuestión. 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 extendido, y se agregan nuevos vértices a la lista de salida donde la ruta del polígono en cuestión cruza la línea del polígono de recorte extendido.
Este proceso se repite iterativamente para cada lado del polígono de clip, 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 de vértices generada 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 renderizar, pero no para otras aplicaciones como calcular sombras.
El algoritmo de Weiler-Atherton supera esto 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 recortando los caminos poligonales según 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 salidaLista = sujetoPolígono; para (Edge clipEdge en clipPolygon) hacer Lista lista de entradas = lista de salidas; lista de salida.clear(); para (int i = 0; i < inputList.count; i += 1) hacer Punto punto_actual = listaentrada[i]; Punto punto_prev = listaentrada[(i − 1) % listaentrada.count]; Punto Punto_intersección = ComputeIntersection(punto_anterior, punto_actual, borde_clip) si (punto_actual dentro de clipEdge) entonces si (punto_prev no dentro de clipEdge) entonces salidaList.add(Intersecting_point); terminar si salidaList.add(current_point); de lo contrario, si (prev_point dentro de clipEdge) entonces salidaList.add(Intersecting_point); terminar si hecho hecho
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 de recorte se enumeran consistentemente en el sentido contrario a las agujas del reloj, entonces esto equivale a probar si el punto se encuentra a la izquierda de la línea (izquierda significa adentro , mientras que derecha significa afuera ), y puede implementarse simplemente mediante usando un producto cruzado .
ComputeIntersection es una función, omitida aquí por motivos de claridad, que devuelve la intersección de un segmento de línea y un borde infinito. 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 si fueran infinitamente largas.
Puede encontrar una implementación Python de Sutherland-Hodgman aquí.
Otros algoritmos de recorte de polígonos:
Sobre el tema del recorte: