| dbo:abstract
|
- The Greiner-Hormann algorithm is used in computer graphics for polygon clipping. It performs better than the Vatti clipping algorithm, but cannot handle degeneracies. It can process both self-intersecting and non-convex polygons. It can be trivially generalized to compute other Boolean operations on polygons, such as union and difference. The algorithm is based on the definition of the "inside" of a polygon based on the winding number. It considers regions with odd winding number to be inside the polygon; this is known as the even–odd rule. It takes two lists of polygons as input. In its original form, the algorithm is divided into three phases:
* In the first phase, pairwise intersections between edges of the polygons are computed. Additional vertices are inserted into both polygons at the points of intersection; an intersection vertex holds a pointer to its counterpart in the other polygon.
* In the second phase, each intersection is marked as either an entry intersection or an exit intersection. This is accomplished by evaluating the even–odd rule at the first vertex, which allows you to know whether the first vertex is inside or outside the other polygon. Then, following the polygon's borders, the intersections are marked with alternating flags (the next intersection after an entry intersection must be an exit intersection).
* In the third phase, the result is generated. The algorithm starts at an unprocessed intersection and picks the direction of traversal based on the entry/exit flag: for an entry intersection it traverses forward, and for an exit intersection it traverses in reverse. Vertices are added to the result until the next intersection is found; the algorithm then switches to the corresponding intersection vertex in the other polygon and picks the traversal direction again using the same rule. If the next intersection has already been processed, the algorithm finishes the current component of the output and starts again from an unprocessed intersection. The output is complete when there are no more unprocessed intersections. The algorithm is not restricted to polygons and can handle arbitrary parametric curves as segments, as long as there is a suitable pairwise intersection procedure. A major shortcoming of the original Greiner–Hormann algorithm is the fact that it cannot handle degeneracies, such as common edges or intersections exactly at a vertex. The original paper suggests perturbing the vertices to remove them. (en)
- 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. (es)
- L’algorithme de Greiner-Hormann est utilisé en infographie pour découper des polygones. Il est plus performant que l’algorithme de Vatti, mais ne peut pas gérer d’éventuels cas dégénérés. Il peut cependant être utilisé avec des polygones s’auto-intersectant et n'étant pas convexes. Il peut facilement être généralisé afin d’effectuer d’autres opérations booléennes sur les polygones, telles que l’union et la différence. (fr)
|
| rdfs:comment
|
- L’algorithme de Greiner-Hormann est utilisé en infographie pour découper des polygones. Il est plus performant que l’algorithme de Vatti, mais ne peut pas gérer d’éventuels cas dégénérés. Il peut cependant être utilisé avec des polygones s’auto-intersectant et n'étant pas convexes. Il peut facilement être généralisé afin d’effectuer d’autres opérations booléennes sur les polygones, telles que l’union et la différence. (fr)
- The Greiner-Hormann algorithm is used in computer graphics for polygon clipping. It performs better than the Vatti clipping algorithm, but cannot handle degeneracies. It can process both self-intersecting and non-convex polygons. It can be trivially generalized to compute other Boolean operations on polygons, such as union and difference. The algorithm is based on the definition of the "inside" of a polygon based on the winding number. It considers regions with odd winding number to be inside the polygon; this is known as the even–odd rule. It takes two lists of polygons as input. (en)
- 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. (es)
|
