Hispanopedia WikiLas operaciones booleanas sobre polígonos son un conjunto de operaciones booleanas (AND, OR, NOT, XOR, ...) que se realizan sobre uno o más conjuntos de polígonos en gráficos por computadora. Estos conjuntos de operaciones se utilizan ampliamente en gráficos por computadora , CAD y en EDA (en software de diseño físico y verificación de circuitos integrados ).
Algoritmos
- Algoritmo de recorte de Greiner-Hormann
- Algoritmo de recorte de Vatti
- Algoritmo de Sutherland-Hodgman (algoritmo de caso especial)
- Algoritmo de recorte de Weiler-Atherton (algoritmo de caso especial)
Usos en software
Los primeros algoritmos para operaciones booleanas en polígonos se basaban en el uso de mapas de bits . El uso de mapas de bits para modelar formas de polígonos tiene muchos inconvenientes. Uno de ellos es que el uso de memoria puede ser muy grande, ya que la resolución de los polígonos es proporcional al número de bits utilizados para representarlos. Cuanto mayor sea la resolución deseada, mayor será el número de bits necesarios.
Las implementaciones modernas de operaciones booleanas en polígonos tienden a utilizar algoritmos de barrido de plano (o algoritmos de barrido de línea ). En las referencias que aparecen a continuación se puede encontrar una lista de artículos que utilizan algoritmos de barrido de plano para operaciones booleanas en polígonos.
Las operaciones booleanas sobre polígonos convexos y polígonos monótonos de la misma dirección se pueden realizar en tiempo lineal . [1]
Véase también
- Álgebra de Boole
- Geometría computacional
- Geometría sólida constructiva , un método para definir formas tridimensionales utilizando un conjunto similar de operaciones.
- Procesamiento de geometría
- General Polygon Clipper , una biblioteca C que calcula los resultados de las operaciones de recorte
Notas
- ^ Katz, Matthew J.; Overmars, Mark H.; Sharir, Micha (1992), "Eliminación eficiente de superficies ocultas para objetos con un tamaño de unión pequeño", Computational Geometry: Theory and Applications , 2 (4): 223–234, doi : 10.1016/0925-7721(92)90024-M.
Bibliografía
- Mark de Berg, Marc van Kreveld, Mark Overmars y Otfried Schwarzkopf, Geometría computacional: algoritmos y aplicaciones, segunda edición, 2000
- Jon Louis Bentley y Thomas A. Ottmann, Algoritmos para informar y contar intersecciones geométricas, IEEE Transactions on Computers, vol. C-28, n.º 9, septiembre de 1979, págs. 643–647
- Jon Louis Bentley y Derick Wood , Un algoritmo óptimo en el peor de los casos para informar intersecciones de rectángulos, IEEE Transactions on Computers, vol. C-29, n.º 7, julio de 1980, págs. 571-577
- Ulrich Lauther, Un algoritmo O(N log N) para operaciones de máscara booleana, 18.ª Conferencia de Automatización de Diseño, 1981, págs. 555-562
- James A. Wilmore, Operaciones booleanas eficientes en máscaras de circuitos integrados, 18.ª Conferencia de automatización del diseño, 1981, págs. 571-579
- Nievergelt, J.; Preparata, FP (octubre de 1982). "Algoritmos de barrido de planos para intersecciones de figuras geométricas". Comunicaciones de la ACM . 25 (10): 739–747. CiteSeerX 10.1.1.83.3275 . doi :10.1145/358656.358681. S2CID 16606107.
- Thomas Ottmann, Peter Widmayer y Derick Wood, "Un algoritmo rápido para el problema de enmascaramiento booleano", Computer Vision, Graphics, and Image Processing, 30, 1985, págs. 249-268
Enlaces externos
- Páginas de geometría computacional de la UIUC
- Geometría plana constructiva, por Dave Eberly.
- Software
- Michael Leonov ha compilado una comparación de recortadores de polígonos.
- Angus Johnson también ha comparado tres bibliotecas de recorte.
- SINED GmbH ha comparado el rendimiento y la utilización de la memoria de tres recortadores de polígonos Archivado el 16 de noviembre de 2012 en Wayback Machine .
- Una comparación de 5 bibliotecas de recorte en rogue-modron.blogspot.com
- Una biblioteca comercial para operaciones booleanas 3D: biblioteca sgCore C++/C#.
- Preguntas frecuentes de comp.graphics.algorithms, soluciones a problemas matemáticos con polígonos 2D y 3D.
- gfxpoly de Matthias Kramm, una biblioteca C gratuita para polígonos 2D (licencia BSD).
- Boolean de Klaas Holwerda, una biblioteca C++ para polígonos 2D.
- Polypack de David Kennison, una biblioteca FORTRAN basada en el algoritmo Vatti.
- Clippoly de Klamer Schutte, un recortador de polígonos escrito en C++.
- poly_Boolean de Michael Leonov, una biblioteca de C++ que extiende el algoritmo Schutte.
- Clipper de Angus Johnson, una biblioteca freeware de código abierto (escrita en Delphi, C++ y C#) que se basa en el algoritmo Vatti .
- Caja Clipper2, un envoltorio seguro de Rust para la biblioteca Clipper2 de Angus Johnson.
- GeoLib, una biblioteca comercial disponible en C++ y C#.
- GPC de Alan Murta Archivado el 27 de febrero de 2011 en Wayback Machine , biblioteca General Polygon Clipper.
- PolygonLib Archivado el 16 de noviembre de 2012 en Wayback Machine , bibliotecas C++ y COM para polígonos 2D (optimizadas para conjuntos de polígonos grandes, índices espaciales integrados).