Boolean operations on polygons
ಬಹುಭುಜಾಕೃತಿಗಳ ಮೇಲಿನ ಬೂಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಗಳು ಕಂಪ್ಯೂಟರ್ ಗ್ರಾಫಿಕ್ಸ್ನಲ್ಲಿ ಒಂದು ಅಥವಾ ಹೆಚ್ಚಿನ ಬಹುಭುಜಾಕೃತಿಗಳ ಮೇಲೆ ಕಾರ್ಯನಿರ್ವಹಿಸುವ ಬೂಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಗಳ (AND, OR, NOT, XOR,.) ಒಂದು ಗುಂಪಾಗಿದೆ. ಈ ಕಾರ್ಯಾಚರಣೆಗಳ ಸೆಟ್ಗಳನ್ನು ಕಂಪ್ಯೂಟರ್ ಗ್ರಾಫಿಕ್ಸ್, ಸಿಎಡಿ ಮತ್ತು ಇಡಿಎ (ಇಂಟಿಗ್ರೇಟೆಡ್ ಸರ್ಕ್ಯೂಟ್ ಫಿಸಿಕಲ್ ಡಿಸೈನ್ ಮತ್ತು ವೆರಿಫಿಕೇಶನ್ ಸಾಫ್ಟ್ವೇರ್ನಲ್ಲಿ) ವ್ಯಾಪಕವಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ಗಳು ಗ್ರೀನರ್-ಹಾರ್ಮನ್ ಕ್ಲಿಪ್ಪಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ವಾಟ್ಟಿ ಕ್ಲಿಪ್ಪಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಸದರ್ಲ್ಯಾಂಡ್-ಹಾಡ್ಗ್ಮನ್ ಅಲ್ಗಾರಿದಮ್ (ವಿಶೇಷ ಕೇಸ್ ಅಲ್ಗಾರಿದಮ್) ವೀಲರ್-ಅಥರ್ಟನ್ ಕ್ಲಿಪ್ಪಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ (ವಿಶೇಷ ಕೇಸ್ ಅಲ್ಗಾರಿದಮ್) ಸಾಫ್ಟ್ವೇರ್ನಲ್ಲಿ ಬಳಕೆಗಳು ಬಹುಭುಜಾಕೃತಿಗಳ ಮೇಲಿನ ಬೂಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಗಳಿಗೆ ಆರಂಭಿಕ ಅಲ್ಗಾರಿದಮ್ಗಳು ಬಿಟ್ಮ್ಯಾಪ್ಗಳ ಬಳಕೆಯನ್ನು ಆಧರಿಸಿವೆ. ಬಹುಭುಜಾಕೃತಿಯ ಆಕಾರಗಳನ್ನು ರೂಪಿಸುವಲ್ಲಿ ಬಿಟ್ಮ್ಯಾಪ್ಗಳನ್ನು ಬಳಸುವುದರಿಂದ ಅನೇಕ ನ್ಯೂನತೆಗಳಿವೆ. ಒಂದು ನ್ಯೂನತೆಯೆಂದರೆ, ಬಹುಭುಜಾಕೃತಿಗಳ ರೆಸಲ್ಯೂಶನ್ ಬಹುಭುಜಾಕೃತಿಗಳನ್ನು ಪ್ರತಿನಿಧಿಸಲು ಬಳಸುವ ಬಿಟ್ಗಳ ಸಂಖ್ಯೆಗೆ ಅನುಪಾತದಲ್ಲಿರುವುದರಿಂದ ಮೆಮೊರಿ ಬಳಕೆಯು ತುಂಬಾ ದೊಡ್ಡದಾಗಿರಬಹುದು. ಹೆಚ್ಚಿನ ರೆಸಲ್ಯೂಶನ್ ಬಯಸಿದಲ್ಲಿ, ಹೆಚ್ಚು ಬಿಟ್ಗಳ ಅಗತ್ಯವಿರುತ್ತದೆ. ಬಹುಭುಜಾಕೃತಿಗಳ ಮೇಲಿನ ಬೂಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಗಳ ಆಧುನಿಕ ಅನುಷ್ಠಾನಗಳು ಪ್ಲೇನ್ ಸ್ವೀಪ್ ಕ್ರಮಾವಳಿಗಳನ್ನು (ಅಥವಾ ಸ್ವೀಪ್ ಲೈನ್ ಕ್ರಮಾವಳಿಗಳು) ಬಳಸುತ್ತವೆ. ಬಹುಭುಜಾಕೃತಿಗಳ ಮೇಲಿನ ಬೂಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಗಳಿಗಾಗಿ ಪ್ಲೇನ್ ಸ್ವೀಪ್ ಕ್ರಮಾವಳಿಗಳನ್ನು ಬಳಸುವ ಪ್ರಬಂಧಗಳ ಪಟ್ಟಿಯನ್ನು ಕೆಳಗಿನ ಉಲ್ಲೇಖಗಳಲ್ಲಿ ಕಾಣಬಹುದು. ಒಂದೇ ದಿಕ್ಕಿನ ಕನ್ವೆಕ್ಸ್ ಬಹುಭುಜಾಕೃತಿಗಳು ಮತ್ತು ಮೊನೊಟೋನ್ ಬಹುಭುಜಾಕೃತಿಗಳ ಮೇಲೆ ಬೂಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಮಾಡಬಹುದು. ಇದೇ ರೀತಿಯ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಮೂಹವನ್ನು ಬಳಸಿಕೊಂಡು ಮೂರು ಆಯಾಮದ ಆಕಾರಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುವ ವಿಧಾನವಾದ ಬೂಲಿಯನ್ ಬೀಜಗಣಿತದ ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿಯ ಕನ್ಸ್ಟ್ರಕ್ಟಿವ್ ಸಾಲಿಡ್ ಜ್ಯಾಮಿತಿಯನ್ನು ನೋಡಿ, ಸಾಮಾನ್ಯ ಪಾಲಿಗಾನ್ ಕ್ಲಿಪ್ಪರ್, ಕ್ಲಿಪ್ಪಿಂಗ್ ಕಾರ್ಯಾಚರಣೆಗಳ ಫಲಿತಾಂಶಗಳನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವ ಸಿ ಲೈಬ್ರರಿ ಟಿಪ್ಪಣಿಗಳು ಗ್ರಂಥಸೂಚಿ ಮಾರ್ಕ್ ಡಿ ಬರ್ಗ್, ಮಾರ್ಕ್ ವ್ಯಾನ್ ಕ್ರೆವೆಲ್ಡ್, ಮಾರ್ಕ್ ಓವರ್ಮಾರ್ಸ್, ಮತ್ತು ಓಟ್ಫ್ರೈಡ್ ಶ್ವಾರ್ಜ್ಕೋಫ್, ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿ-ಕ್ರಮಾವಳಿಗಳು ಮತ್ತು ಅನ್ವಯಗಳು, ಎರಡನೇ ಆವೃತ್ತಿ, 2000 ಜಾನ್ ಲೂಯಿಸ್ ಬೆಂಟ್ಲೆ ಮತ್ತು ಥಾಮಸ್ ಎ. ಓಟ್ಮನ್, ಜ್ಯಾಮಿತೀಯ ಛೇದನಗಳನ್ನು ವರದಿ ಮಾಡಲು ಮತ್ತು ಎಣಿಸಲು ಕ್ರಮಾವಳಿಗಳು, ಕಂಪ್ಯೂಟರ್ಗಳ ಮೇಲೆ ಐ. ಇ. ಇ. ಇ ವಹಿವಾಟುಗಳು, ಸಂಪುಟ. ಸಿ-28, ನಂ. 9, ಸೆಪ್ಟೆಂಬರ್ 1979, ಪು. 643-647 ಜಾನ್ ಲೂಯಿಸ್ ಬೆಂಟ್ಲೆ ಮತ್ತು ಡೆರಿಕ್ ವುಡ್, ಆಯತಗಳ ಛೇದನಗಳನ್ನು ವರದಿ ಮಾಡಲು ಒಂದು ಅತ್ಯುತ್ತಮ ಕೆಟ್ಟ ಕೇಸ್ ಅಲ್ಗಾರಿದಮ್, ಕಂಪ್ಯೂಟರ್ಗಳ ಮೇಲಿನ ಐ. ಇ. ಇ. ಇ ವಹಿವಾಟುಗಳು, ಸಂಪುಟ. ಸಿ-29. ಇಲ್ಲ. 7, ಜುಲೈ 1980, ಪು. 571-577 ಉಲ್ರಿಚ್ ಲೌಥರ್, ಆನ್ ಓ (ಎನ್ ಲಾಗ್ ಎನ್) ಅಲ್ಗಾರಿದಮ್ ಫಾರ್ ಬೂಲಿಯನ್ ಮಾಸ್ಕ್ ಆಪರೇಶನ್ಸ್, 18 ನೇ ಡಿಸೈನ್ ಆಟೊಮೇಷನ್ ಕಾನ್ಫರೆನ್ಸ್, 1981, pp. ಜೇಮ್ಸ್ ಎ. ವಿಲ್ಮೋರ್, ಎಫಿಷಿಯೆಂಟ್ ಬೂಲಿಯನ್ ಆಪರೇಶನ್ಸ್ ಆನ್ ಐಸಿ ಮಾಸ್ಕ್ಸ್, 18 ನೇ ಡಿಸೈನ್ ಆಟೊಮೇಷನ್ ಕಾನ್ಫರೆನ್ಸ್, 1981, pp. 571-579 ಥಾಮಸ್ ಓಟ್ಮನ್, ಪೀಟರ್ ವಿಡ್ಮೆಯರ್, ಮತ್ತು ಡೆರಿಕ್ ವುಡ್, "ಎ ಫಾಸ್ಟ್ ಅಲ್ಗಾರಿದಮ್ ಫಾರ್ ದಿ ಬೂಲಿಯನ್ ಮಾಸ್ಕಿಂಗ್ ಪ್ರಾಬ್ಲಮ್", ಕಂಪ್ಯೂಟರ್ ವಿಷನ್, ಗ್ರಾಫಿಕ್ಸ್, ಮತ್ತು ಇಮೇಜ್ ಪ್ರೊಸೆಸಿಂಗ್, 30,1985, pp. 249-268 ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಯುಐಯುಸಿ ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿ ಪುಟಗಳು ರಚನಾತ್ಮಕ ಸಮತಲ ಜ್ಯಾಮಿತಿ, ಡೇವ್ ಎಬರ್ಲಿ ಅವರಿಂದ. ಸಾಫ್ಟ್ವೇರ್ ಮೈಕೆಲ್ ಲಿಯೊನೊವ್ ಬಹುಭುಜಾಕೃತಿಯ ತುಣುಕುಗಳ ಹೋಲಿಕೆಯನ್ನು ಸಂಗ್ರಹಿಸಿದ್ದಾರೆ. ಆಂಗಸ್ ಜಾನ್ಸನ್ ಮೂರು ಕ್ಲಿಪ್ಪಿಂಗ್ ಗ್ರಂಥಾಲಯಗಳನ್ನು ಹೋಲಿಸಿದ್ದಾರೆ. SINED GmbH ಮೂರು ಬಹುಭುಜಾಕೃತಿಯ ತುಣುಕುಗಳ ಕಾರ್ಯಕ್ಷಮತೆ ಮತ್ತು ಸ್ಮರಣೆಯ ಬಳಕೆಯನ್ನು ಹೋಲಿಸಿದೆ. 3ಡಿ ಬೂಲಿಯನ್ ಕಾರ್ಯಾಚರಣೆಗಳಿಗಾಗಿ ಒಂದು ವಾಣಿಜ್ಯ ಗ್ರಂಥಾಲಯದಲ್ಲಿರುವ 5 ಕ್ಲಿಪ್ಪಿಂಗ್ ಗ್ರಂಥಾಲಯಗಳ ಹೋಲಿಕೆಃ ಎಸ್ಜಿಕೋರ್ ಸಿ + +/ಸಿ #ಗ್ರಂಥಾಲಯ. comp.graphics.algorithms FAQ, 2D ಮತ್ತು 3D ಬಹುಭುಜಾಕೃತಿಗಳೊಂದಿಗೆ ಗಣಿತದ ಸಮಸ್ಯೆಗಳಿಗೆ ಪರಿಹಾರಗಳು. ಮ್ಯಾಥಿಯಸ್ ಕ್ರಾಮ್ಸ್ ಜಿಎಫ್ಎಕ್ಸ್ಪೋಲಿ, 2ಡಿ ಬಹುಭುಜಾಕೃತಿಗಳಿಗೆ ಉಚಿತ ಸಿ ಗ್ರಂಥಾಲಯ (ಬಿಎಸ್ಡಿ ಪರವಾನಗಿ). ಕ್ಲಾಸ್ ಹೋಲ್ವೆರ್ಡಾರ ಬೂಲಿಯನ್, 2ಡಿ ಬಹುಭುಜಾಕೃತಿಗಳಿಗಾಗಿ ಸಿ + + ಗ್ರಂಥಾಲಯವಾಗಿದೆ. ಡೇವಿಡ್ ಕೆನ್ನಿಸನ್ರ ಪಾಲಿಪ್ಯಾಕ್, ವಾಟ್ಟಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಆಧರಿಸಿದ FORTRAN ಗ್ರಂಥಾಲಯವಾಗಿದೆ. ಕ್ಲಾಮರ್ ಶುಟ್ಟೆಯ ಕ್ಲಿಪ್ಪೋಲಿ, ಸಿ + + ನಲ್ಲಿ ಬರೆಯಲಾದ ಬಹುಭುಜಾಕೃತಿಯ ಕ್ಲಿಪ್ಪರ್. ಮೈಕೆಲ್ ಲಿಯೊನೊವ್ ಅವರ ಪಾಲಿ _ ಬೂಲಿಯನ್, ಒಂದು ಸಿ + + ಗ್ರಂಥಾಲಯವಾಗಿದ್ದು, ಇದು ಶುಟ್ಟೆ ಕ್ರಮಾವಳಿಯನ್ನು ವಿಸ್ತರಿಸುತ್ತದೆ. ಆಂಗಸ್ ಜಾನ್ಸನ್ನ ಕ್ಲಿಪ್ಪರ್, ಮುಕ್ತ-ಮೂಲ ಫ್ರೀವೇರ್ ಗ್ರಂಥಾಲಯವಾಗಿದ್ದು (ಡೆಲ್ಫಿ, ಸಿ + + ಮತ್ತು ಸಿ #ನಲ್ಲಿ ಬರೆಯಲಾಗಿದೆ) ಇದು ವಾಟ್ಟಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಆಧರಿಸಿದೆ. ಜಿಯೋಲಿಬ್, ಸಿ + + ಮತ್ತು ಸಿ #ನಲ್ಲಿ ಲಭ್ಯವಿರುವ ವಾಣಿಜ್ಯ ಗ್ರಂಥಾಲಯವಾಗಿದೆ. ಅಲನ್ ಮುರ್ತಾರ ಜಿಪಿಸಿ, ಜನರಲ್ ಪಾಲಿಗೊನ್ ಕ್ಲಿಪ್ಪರ್ ಲೈಬ್ರರಿ. 2ಡಿ ಬಹುಭುಜಾಕೃತಿಗಳಿಗಾಗಿ ಪಾಲಿಗೊನ್ಲಿಬ್, ಸಿ + + ಮತ್ತು ಸಿಒಎಂ ಗ್ರಂಥಾಲಯಗಳು (ದೊಡ್ಡ ಬಹುಭುಜಾಕೃತಿಯ ಸಮೂಹಗಳಿಗೆ ಹೊಂದುವಂತೆ, ಅಂತರ್ನಿರ್ಮಿತ ಪ್ರಾದೇಶಿಕ ಸೂಚ್ಯಂಕಗಳು). ಜ್ಯಾಮಿತೀಯ ಕ್ರಮಾವಳಿಗಳು ಜ್ಯಾಮಿತಿ ಸಂಸ್ಕರಣೆ