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.
Ejemplo de auto-intersección.
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.
Greiner, Günther & Kai Hormann (abril de 1998). «Efficient clipping of arbitrary polygons». Journal ACM Transactions on Graphics17 (2): 71-83.
Ionel Daniel Stroe. «Efficient Clipping of Arbitrary Polygons». Consultado el 17 de mayo de 2014.
Enlaces externos
Geographic Clipping Describe los algoritmos de recorte usados en la librería D3.js.
Implementación en Python y en Java.
Datos:Q17083989
Abril 03, 2022
algoritmo, greiner, hormann, algoritmo, greiner, hormann, utilizado, computación, gráfica, para, recortar, polígonos, más, eficiente, algoritmo, vatti, pero, puede, gestionar, eventuales, casos, degenerados, puede, embargo, utilizarse, polígonos, auto, interse. El algoritmo de Greiner Hormann es utilizado en computacion grafica para recortar poligonos 1 Es mas eficiente que el algoritmo de Vatti pero no puede gestionar eventuales casos degenerados 2 Puede sin embargo utilizarse con poligonos que se auto intersectan sin ser convexos Puede facilmente ser generalizado con el fin de efectuar otras operaciones booleanas sobre poligonos tales que la union y la diferencia Ejemplo de poligonos que se intersectan El algoritmo esta basado en la definicion del interior de un poligono ella misma basada en la nocion de indice Considera las regiones de indice par como interiores al poligono esto es conocido tambien con el nombre de regla par impar El algoritmo toma dos listas de poligonos como entrada cada poligono representado como una lista de cumbres conectadas Ejemplo de auto interseccion En su formulacion inicial el algoritmo se divide en tres fases En la primera fase se calculan las intersecciones entre los lados de los poligonos Las cumbres son anadidos a los puntos de interseccion y a cada uno se la agrega un apuntador hacia su homologo del otro poligono En la segunda fase se marca cada interseccion sea como una interseccion de entrada o como una interseccion de salida Esta decision se toma aplicando la regla par impar a la primera cumbre despues atravesando el poligono alternando las marcas a una interseccion de entrada tiene que seguir una interseccion de salida En la tercera y ultima fase se genera el resultado El algoritmo arranca de una interseccion no tratada y escoge la direccion del recorrido del poligono sobre la base de las marcas de entrada o salida para una interseccion de entrada se atraviesa hacia adelante y para una interseccion de salida atraviesa en sentido inverso Se anaden las cumbres al resultado hasta que otra interseccion sea encontrada a continuacion el algoritmo se ocupa de la interseccion correspondiente en el otro poligono y va a escoger nuevamente una direccion de recorrido segun la misma regla Si la interseccion 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 poligonos y puede tambien bien tratar segmentos de curvas parametricas 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 publicacion original sugiere modificar ciertas cumbres para retirar los casos degenerados Vease tambien EditarAlgoritmo de Vatti Algoritmo de Sutherland Hodgman Algoritmo de Weiler Atherton Operaciones booleanas sobre poligonosReferencias Editar Greiner Gunther amp Kai Hormann abril de 1998 Efficient clipping of arbitrary polygons Journal ACM Transactions on Graphics 17 2 71 83 Ionel Daniel Stroe Efficient Clipping of Arbitrary Polygons Consultado el 17 de mayo de 2014 Enlaces externos EditarGeographic Clipping Describe los algoritmos de recorte usados en la libreria D3 js Implementacion en Python y en Java Datos Q17083989 Obtenido de https es wikipedia org w index php title Algoritmo de Greiner Hormann amp oldid 119129162, wikipedia, wiki, leyendo, leer, libro, biblioteca,
