Las operaciones booleanas sobre polígonos son un conjunto de operaciones booleanas (Y, O, NO, XOR, ...) que operan en 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 verificación y diseño físico 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 en el modelado de formas poligonales tiene muchos inconvenientes. Uno de los inconvenientes 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 representar los polígonos. Cuanto mayor sea la resolución deseada, mayor número de bits se requerirá.
Las implementaciones modernas para operaciones booleanas en polígonos tienden a usar algoritmos de barrido plano (o algoritmos de línea de barrido ). Se puede encontrar una lista de artículos que utilizan algoritmos de barrido plano para operaciones booleanas en polígonos en las Referencias a continuación.
Las operaciones booleanas en polígonos convexos y polígonos monótonos de la misma dirección se pueden realizar en tiempo lineal . [1]
Ver también
- Geometría sólida constructiva , un método para definir formas tridimensionales utilizando un conjunto similar de operaciones.
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", Geometría computacional: teoría y aplicaciones , 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, Computational Geometry - Algorithms and Applications, 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, No. 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. No. 7, julio de 1980, págs. 571–577
- Ulrich Lauther, Un algoritmo O (N log N) para operaciones con máscaras booleanas , 18a Conferencia de automatización del diseño, 1981, págs. 555–562
- James A. Wilmore, Operaciones booleanas eficientes en máscaras IC , 18ª Conferencia de automatización del diseño, 1981, págs. 571–579
- Nievergelt, J .; Preparata, FP (octubre de 1982). "Algoritmos de barrido plano para la intersección de figuras geométricas". Comunicaciones de la ACM . 25 (10): 739–747. CiteSeerX 10.1.1.83.3275 . doi : 10.1145 / 358656.358681 .
- Thomas Ottmann, Peter Widmayer y Derick Wood, " Un algoritmo rápido para el problema de enmascaramiento booleano ", Visión por computadora, gráficos y procesamiento de imágenes, 30, 1985, págs. 249-268.
Ver también
- álgebra de Boole
- Geometría Computacional
- Geometría sólida constructiva
- Procesamiento de geometría
- General Polygon Clipper , una biblioteca de C que calcula los resultados de las operaciones de recorte
enlaces externos
- Páginas de geometría computacional de UIUC
- Geometría plana constructiva , por Dave Eberly.
- Software
- Michael Leonov ha compilado una comparación de cortadoras de polígonos .
- Angus Johnson también ha comparado tres bibliotecas de recortes .
- SINED GmbH ha comparado el rendimiento y la utilización de la memoria de tres recortadores de polígonos .
- Una comparación de 5 bibliotecas de recorte en rogue-modron.blogspot.com
- Una biblioteca comercial para operaciones booleanas 3D: biblioteca sgCore C ++ / C # .
- Las 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 clipper de polígonos escrito en C ++.
- Poly_Boolean de Michael Leonov , una biblioteca de C ++, que amplía el algoritmo de Schutte.
- Clipper de Angus Johnson , una biblioteca de software gratuito de código abierto (escrita en Delphi, C ++ y C #) que se basa en el algoritmo Vatti .
- GeoLib , una biblioteca comercial disponible en C ++ y C #.
- GPC de Alan Murta , biblioteca General Polygon Clipper.
- Bibliotecas PolygonLib , C ++ y COM para polígonos 2D (optimizadas para grandes conjuntos de polígonos, índices espaciales integrados).