This HTML5 document contains 14 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Subject Item

dbr:Greiner–Hormann_clipping_algorithm

owl:sameAs

dbpedia-es:Algoritmo_de_Greiner-Hormann

Subject Item

wikipedia-es:Algoritmo_de_Greiner-Hormann

foaf:primaryTopic

dbpedia-es:Algoritmo_de_Greiner-Hormann

Subject Item

dbpedia-es:Algoritmo_de_Greiner-Hormann

rdfs:label

Algoritmo de Greiner-Hormann

rdfs:comment

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. En su formulación inicial, el algoritmo se divide en tres fases : El algoritmo no se limita a los polígonos, y puede también bien tratar segmentos de curvas paramétricas.

dct:subject

category-es:Algoritmos_de_recorte category-es:Algoritmos_geométricos

foaf:isPrimaryTopicOf

wikipedia-es:Algoritmo_de_Greiner-Hormann

dbo:wikiPageID

7266903

dbo:wikiPageRevisionID

119129162

dbo:wikiPageExternalLink

n9:univ-polyclip n14:

dbo:wikiPageLength

3955

prov:wasDerivedFrom

n11:0

dbo:abstract

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.