Metraipolis › archive › dc_7a78b699e39b

Algoritmo de Greiner-Hormann — Wikipedia (es)

Source
Wikipedia (es)
Original
https://es.wikipedia.org/wiki/Algoritmo_de_Greiner-Hormann
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-17T06:39:32.264Z
SHA-256 of the archived text
a726512ddc3629222b221dfff7c89f7793087cdc619f99dcefe548c52d427a4b
Stable URL of this page
https://metraipolis.com/documento/dc_7a78b699e39b

How to cite

Algoritmo de Greiner-Hormann — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Algoritmo_de_Greiner-Hormann (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7a78b699e39b (Metraipolis archive dc_7a78b699e39b, sha256 a726512ddc3629222b221dfff7c89f7793087cdc619f99dcefe548c52d427a4b)
BibTeX
@misc{dc7a78b699e39b,
  title = {Algoritmo de Greiner-Hormann — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/Algoritmo_de_Greiner-Hormann},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7a78b699e39b; sha256 a726512ddc3629222b221dfff7c89f7793087cdc619f99dcefe548c52d427a4b},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Algoritmo_de_Greiner-Hormann. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

El algoritmo de Greiner-Hormann es utilizado en computación gráfica para recortar polígonos. Es más eficiente que el algoritmo de Vatti, pero no puede gestionar eventuales casos degenerados. Puede sin embargo utilizarse con polígonos que se auto-intersectan sin ser convexos. Puede fácilmente ser generalizado con el fin de efectuar otras operaciones booleanas sobre polígonos, tales que la unión y la diferencia. El algoritmo está basado en la definición del "interior" de un polígono, ella misma basada en la noción de índice. Considera las regiones de índice par como interiores al polígono: esto es conocido también con el nombre de regla par-impar. El algoritmo toma dos listas de polígonos como entrada, cada polígono representado como una lista de cumbres conectadas. En su formulación inicial, el algoritmo se divide en tres fases : En la primera fase, se calculan las intersecciones entre los lados de los polígonos. Las cumbres son añadidos a los puntos de intersección, y a cada uno se la agrega un apuntador hacia su homólogo del otro polígono. En la segunda fase, se marca cada intersección sea como una intersección de entrada, o como una intersección de salida. Esta decisión se toma aplicando la regla par-impar a la primera cumbre, después atravesando el polígono alternando las marcas (a una intersección de entrada tiene que seguir una intersección de salida). En la tercera y última fase, se genera el resultado. El algoritmo arranca de una intersección no tratada y escoge la dirección del recorrido del polígono, sobre la base de las marcas de entrada o salida: para una intersección de entrada, se atraviesa hacia adelante, y para una intersección de salida, atraviesa en sentido inverso. Se añaden las cumbres al resultado hasta que otra intersección sea encontrada; a continuación, el algoritmo se ocupa de la intersección correspondiente en el otro polígono y va a escoger nuevamente una dirección de recorrido, según la misma regla. Si la intersección siguiente ya ha sido tratada, el algoritmo se detiene para esta parte de la salida, y recomienza para las intersecciones no tratadas. La salida queda totalmente determinada cuando ya no quedan intersecciones sin tratar. El algoritmo no se limita a los polígonos, y puede también bien tratar segmentos de curvas paramétricas. Un de los inconvenientes mayores del algoritmo original es que no se ocupa de los casos degenerados, tales que las cumbres duplicadas o las auto-intersecciones tomando en cuenta una sola cumbre. La publicación original sugiere modificar ciertas cumbres para retirar los casos degenerados.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in spagnolo, in ordine alfabetico).
Fonte: Wikipedia in spagnolo, voce «Algoritmo de Greiner-Hormann» — https://es.wikipedia.org/wiki/Algoritmo_de_Greiner-Hormann
Wikidata Q17083989: «algorithm in computer graphics» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q17083989
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Algoritmo_de_Greiner-Hormann?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 171266132, consultata il 2026-10-17T06:30:20.481Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 4fbc3e22a6a1c7758b03ad8f1a129f1ecd45988bf8c1f753fe878ff85fda385f