Space partitioning
ಜ್ಯಾಮಿತಿಯಲ್ಲಿ, ಬಾಹ್ಯಾಕಾಶ ವಿಭಜನೆಯು ಒಂದು ಸಂಪೂರ್ಣ ಜಾಗವನ್ನು (ಸಾಮಾನ್ಯವಾಗಿ ಒಂದು ಯೂಕ್ಲಿಡಿಯನ್ ಜಾಗ) ಎರಡು ಅಥವಾ ಹೆಚ್ಚಿನ ಬೇರ್ಪಡುವ ಉಪಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸುವ ಪ್ರಕ್ರಿಯೆಯಾಗಿದೆ (ಒಂದು ಗುಂಪಿನ ವಿಭಜನೆಯನ್ನೂ ಸಹ ನೋಡಿ). ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಬಾಹ್ಯಾಕಾಶ ವಿಭಜನೆಯು ಜಾಗವನ್ನು ಅತಿಕ್ರಮಿಸದ ಪ್ರದೇಶಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ. ಬಾಹ್ಯಾಕಾಶದಲ್ಲಿನ ಯಾವುದೇ ಬಿಂದುವನ್ನು ನಿಖರವಾಗಿ ಒಂದು ಪ್ರದೇಶದಲ್ಲಿ ಇದೆ ಎಂದು ಗುರುತಿಸಬಹುದು. ಬಾಹ್ಯಾಕಾಶ-ವಿಭಜನಾ ವ್ಯವಸ್ಥೆಗಳು ಸಾಮಾನ್ಯವಾಗಿ ಶ್ರೇಣೀಕೃತವಾಗಿರುತ್ತವೆ, ಅಂದರೆ ಒಂದು ಜಾಗವನ್ನು (ಅಥವಾ ಬಾಹ್ಯಾಕಾಶದ ಪ್ರದೇಶ) ಹಲವಾರು ಪ್ರದೇಶಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ, ಮತ್ತು ನಂತರ ಅದೇ ಬಾಹ್ಯಾಕಾಶ-ವಿಭಜನಾ ವ್ಯವಸ್ಥೆಯನ್ನು ಹೀಗೆ ರಚಿಸಲಾದ ಪ್ರತಿಯೊಂದು ಪ್ರದೇಶಕ್ಕೂ ಪುನರಾವರ್ತಿತವಾಗಿ ಅನ್ವಯಿಸಲಾಗುತ್ತದೆ. ಪ್ರದೇಶಗಳನ್ನು ಮರವಾಗಿ ಸಂಘಟಿಸಬಹುದು, ಇದನ್ನು ಬಾಹ್ಯಾಕಾಶ-ವಿಭಜಕ ಮರ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಹೆಚ್ಚಿನ ಬಾಹ್ಯಾಕಾಶ-ವಿಭಜನಾ ವ್ಯವಸ್ಥೆಗಳು ಜಾಗವನ್ನು ವಿಭಜಿಸಲು ಸಮತಲಗಳನ್ನು (ಅಥವಾ, ಹೆಚ್ಚಿನ ಆಯಾಮಗಳಲ್ಲಿ, ಹೈಪರ್ ಪ್ಲೇನ್ಗಳು) ಬಳಸುತ್ತವೆಃ ಸಮತಲದ ಒಂದು ಬದಿಯಲ್ಲಿರುವ ಬಿಂದುಗಳು ಒಂದು ಪ್ರದೇಶವನ್ನು ರೂಪಿಸುತ್ತವೆ ಮತ್ತು ಇನ್ನೊಂದು ಬದಿಯಲ್ಲಿರುವ ಬಿಂದುಗಳು ಮತ್ತೊಂದು ಪ್ರದೇಶವನ್ನು ರೂಪಿಸುತ್ತವೆ. ಸಮತಲದಲ್ಲಿ ನಿಖರವಾಗಿ ಬಿಂದುಗಳನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಒಂದು ಅಥವಾ ಇನ್ನೊಂದು ಬದಿಗೆ ಅನಿಯಂತ್ರಿತವಾಗಿ ನಿಗದಿಪಡಿಸಲಾಗುತ್ತದೆ. ಈ ರೀತಿಯಲ್ಲಿ ವಿಮಾನಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಜಾಗವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ವಿಭಜಿಸುವುದರಿಂದ ಬಿ. ಎಸ್. ಪಿ ಮರವನ್ನು ಉತ್ಪಾದಿಸುತ್ತದೆ, ಇದು ಜಾಗವನ್ನು ವಿಭಜಿಸುವ ಅತ್ಯಂತ ಸಾಮಾನ್ಯ ರೂಪಗಳಲ್ಲಿ ಒಂದಾಗಿದೆ. ಕಂಪ್ಯೂಟರ್ ಗ್ರಾಫಿಕ್ಸ್ನಲ್ಲಿ ಉಪಯೋಗಗಳು ಕಂಪ್ಯೂಟರ್ ಗ್ರಾಫಿಕ್ಸ್ನಲ್ಲಿ ಬಾಹ್ಯಾಕಾಶ ವಿಭಜನೆಯು ವಿಶೇಷವಾಗಿ ಮುಖ್ಯವಾಗಿದೆ, ವಿಶೇಷವಾಗಿ ರೇ ಟ್ರೇಸಿಂಗ್ನಲ್ಲಿ ಹೆಚ್ಚಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ, ಅಲ್ಲಿ ಇದನ್ನು ವಾಸ್ತವ ದೃಶ್ಯದಲ್ಲಿ ವಸ್ತುಗಳನ್ನು ಸಂಘಟಿಸಲು ಆಗಾಗ್ಗೆ ಬಳಸಲಾಗುತ್ತದೆ. ಒಂದು ವಿಶಿಷ್ಟ ದೃಶ್ಯವು ಲಕ್ಷಾಂತರ ಬಹುಭುಜಾಕೃತಿಗಳನ್ನು ಹೊಂದಿರಬಹುದು. ಪ್ರತಿಯೊಂದರೊಂದಿಗೆ ಕಿರಣ/ಬಹುಭುಜಾಕೃತಿಯ ಛೇದಕ ಪರೀಕ್ಷೆಯನ್ನು ಮಾಡುವುದು ಗಣನೆಯ ದೃಷ್ಟಿಯಿಂದ ಬಹಳ ದುಬಾರಿ ಕಾರ್ಯವಾಗಿದೆ. ಬಾಹ್ಯಾಕಾಶ-ವಿಭಜನೆಯ ದತ್ತಾಂಶ ರಚನೆಯಲ್ಲಿ ವಸ್ತುಗಳನ್ನು ಸಂಗ್ರಹಿಸುವುದು (ಉದಾಹರಣೆಗೆ ಕೆ-ಡಿ ಮರ ಅಥವಾ ಬಿಎಸ್ಪಿ ಮರ) ಕೆಲವು ರೀತಿಯ ರೇಖಾಗಣಿತ ಪ್ರಶ್ನೆಗಳನ್ನು ನಿರ್ವಹಿಸಲು ಸುಲಭವಾಗಿಸುತ್ತದೆ-ಉದಾಹರಣೆಗೆ ಒಂದು ಕಿರಣವು ವಸ್ತುವನ್ನು ಛೇದಿಸುತ್ತದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವಲ್ಲಿ, ಬಾಹ್ಯಾಕಾಶ ವಿಭಜನೆಯು ಛೇದಕ ಪರೀಕ್ಷೆಯ ಸಂಖ್ಯೆಯನ್ನು ಪ್ರತಿ ಪ್ರಾಥಮಿಕ ಕಿರಣಕ್ಕೆ ಕೇವಲ ಕೆಲವಕ್ಕೆ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ, ಇದು ಬಹುಭುಜಾಕೃತಿಗಳ ಸಂಖ್ಯೆಗೆ ಸಂಬಂಧಿಸಿದಂತೆ ಲಾಗರಿಥಮಿಕ್ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ನೀಡುತ್ತದೆ. ಬಾಹ್ಯಾಕಾಶ ವಿಭಜನೆಯನ್ನು ಹೆಚ್ಚಾಗಿ ಸ್ಕ್ಯಾನ್ಲೈನ್ ಕ್ರಮಾವಳಿಗಳಲ್ಲಿ ಕ್ಯಾಮೆರಾದ ನೋಡುವ ಫ್ರಸ್ಟಮ್ನಿಂದ ಬಹುಭುಜಾಕೃತಿಗಳನ್ನು ತೆಗೆದುಹಾಕಲು ಬಳಸಲಾಗುತ್ತದೆ, ಇದು ಪೈಪ್ಲೈನ್ನಿಂದ ಸಂಸ್ಕರಿಸಿದ ಬಹುಭುಜಾಕೃತಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೀಮಿತಗೊಳಿಸುತ್ತದೆ. ಘರ್ಷಣೆ ಪತ್ತೆಹಚ್ಚುವಿಕೆಯಲ್ಲೂ ಒಂದು ಬಳಕೆಯಿದೆಃ ಎರಡು ವಸ್ತುಗಳು ಒಂದಕ್ಕೊಂದು ಹತ್ತಿರದಲ್ಲಿವೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ಬಾಹ್ಯಾಕಾಶ ವಿಭಜನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಹೆಚ್ಚು ವೇಗವಾಗಿರುತ್ತದೆ. ಇಂಟಿಗ್ರೇಟೆಡ್ ಸರ್ಕ್ಯೂಟ್ ವಿನ್ಯಾಸದಲ್ಲಿ, ಒಂದು ಪ್ರಮುಖ ಹಂತವೆಂದರೆ ಡಿಸೈನ್ ರೂಲ್ ಚೆಕ್. ಈ ಹಂತವು ಪೂರ್ಣಗೊಂಡ ವಿನ್ಯಾಸವನ್ನು ತಯಾರಿಸಬಹುದೆಂದು ಖಚಿತಪಡಿಸುತ್ತದೆ. ಚೆಕ್ ಅಗಲಗಳು ಮತ್ತು ಅಂತರಗಳು ಮತ್ತು ಇತರ ಜ್ಯಾಮಿತಿಯ ಮಾದರಿಗಳನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸುವ ನಿಯಮಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಆಧುನಿಕ ವಿನ್ಯಾಸವು ತಂತಿಗಳು ಮತ್ತು ಟ್ರಾನ್ಸಿಸ್ಟರ್ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುವ ಶತಕೋಟಿ ಬಹುಭುಜಾಕೃತಿಗಳನ್ನು ಹೊಂದಿರಬಹುದು. ದಕ್ಷ ಪರಿಶೀಲನೆಯು ಜ್ಯಾಮಿತಿಯ ಪ್ರಶ್ನೆಯ ಮೇಲೆ ಹೆಚ್ಚು ಅವಲಂಬಿತವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಯಾವುದೇ ಬಹುಭುಜಾಕೃತಿಯು ಇತರ ಯಾವುದೇ ಬಹುಭುಜಾಕೃತಿಯಿಂದ ಕನಿಷ್ಠ n ನ್ಯಾನೊಮೀಟರ್ಗಳಷ್ಟು ದೂರದಲ್ಲಿರಬೇಕು ಎಂದು ಒಂದು ನಿಯಮವು ನಿರ್ದಿಷ್ಟಪಡಿಸಬಹುದು. ಎಲ್ಲಾ ಬದಿಗಳಲ್ಲಿ ಒಂದು ಬಹುಭುಜಾಕೃತಿಯನ್ನು n/2 ರಿಂದ ವಿಸ್ತರಿಸುವ ಮೂಲಕ ಮತ್ತು ಎಲ್ಲಾ ಛೇದಿಸುವ ಬಹುಭುಜಾಕೃತಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮೂಲಕ ಇದನ್ನು ಜ್ಯಾಮಿತಿಯ ಪ್ರಶ್ನೆಯಾಗಿ ಪರಿವರ್ತಿಸಲಾಗುತ್ತದೆ. ಸಂಭವನೀಯತೆ ಮತ್ತು ಸಂಖ್ಯಾಶಾಸ್ತ್ರೀಯ ಕಲಿಕೆಯ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಬಾಹ್ಯಾಕಾಶ ವಿಭಜನೆಯಲ್ಲಿನ ಘಟಕಗಳ ಸಂಖ್ಯೆಯು ಸಂಭವನೀಯತೆ ಸಿದ್ಧಾಂತದ ಕೆಲವು ಫಲಿತಾಂಶಗಳಲ್ಲಿ ಪ್ರಮುಖ ಪಾತ್ರವನ್ನು ವಹಿಸುತ್ತದೆ. ಹೆಚ್ಚಿನ ವಿವರಗಳಿಗಾಗಿ ಗ್ರೋತ್ ಫಂಕ್ಷನ್ ಅನ್ನು ನೋಡಿ. ಭೌಗೋಳಿಕ ಮತ್ತು ಜಿಐಎಸ್ನಲ್ಲಿ ಭೌಗೋಳಿಕ ಪ್ರಾದೇಶಿಕ ವಾಸ್ತವತೆಯನ್ನು ಜಲಶಾಸ್ತ್ರೀಯ ಮಾನದಂಡಗಳು, ಆಡಳಿತಾತ್ಮಕ ಮಾನದಂಡಗಳು, ಗಣಿತದ ಮಾನದಂಡಗಳು ಅಥವಾ ಇತರ ಅನೇಕ ಅಂಶಗಳಿಂದ ವಿಭಜಿಸಲಾಗಿರುವ ಅನೇಕ ಅಧ್ಯಯನಗಳು ಮತ್ತು ಅನ್ವಯಗಳಿವೆ. ಕಾರ್ಟೋಗ್ರಫಿ ಮತ್ತು ಜಿಐಎಸ್-ಭೌಗೋಳಿಕ ಮಾಹಿತಿ ವ್ಯವಸ್ಥೆಯ ಸಂದರ್ಭದಲ್ಲಿ, ವಿಭಾಗದ ಕೋಶಗಳನ್ನು ಪ್ರಮಾಣಿತ ಸಂಕೇತಗಳಿಂದ ಗುರುತಿಸುವುದು ಸಾಮಾನ್ಯವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ ಹೈಡ್ರೋಗ್ರಾಫಿಕಲ್ ಜಲಾನಯನ ಪ್ರದೇಶಗಳು ಮತ್ತು ಉಪ-ಜಲಾನಯನ ಪ್ರದೇಶಗಳನ್ನು ಗುರುತಿಸುವ ಎಚ್. ಯು. ಸಿ ಕೋಡ್, ದೇಶಗಳನ್ನು ಮತ್ತು ಅದರ ಉಪವಿಭಾಗಗಳನ್ನು ಗುರುತಿಸುವ ಐಎಸ್ಒ 3166-2 ಕೋಡ್ಗಳು, ಅಥವಾ ಅನಿಯಂತ್ರಿತ ಡಿಜಿಜಿಗಳು-ಚತುರ್ಭುಜಗಳು ಅಥವಾ ಸ್ಥಳಗಳನ್ನು ಗುರುತಿಸುವ ಪ್ರತ್ಯೇಕ ಜಾಗತಿಕ ಗ್ರಿಡ್ಗಳು. ದತ್ತಾಂಶ ರಚನೆಗಳು ಸಾಮಾನ್ಯ ಬಾಹ್ಯಾಕಾಶ-ವಿಭಜನಾ ವ್ಯವಸ್ಥೆಗಳು ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಒಳಗೊಂಡಿವೆಃ ಬಿಎಸ್ಪಿ ಮರಗಳು ಕ್ವಾಡ್ಟ್ರೀಸ್ ಆಕ್ಟ್ರೀಸ್ ಕೆ-ಡಿ ಮರಗಳು ತೊಟ್ಟಿಗಳು ಆರ್-ಮರಗಳು ಘಟಕಗಳ ಸಂಖ್ಯೆ ಎನ್-ಆಯಾಮದ ಯೂಕ್ಲಿಡಿಯನ್ ಜಾಗವನ್ನು-ಆಯಾಮದ ಹೈಪರ್ ಪ್ಲೇನ್ಗಳಿಂದ ವಿಭಜಿಸಲಾಗಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ವಿಭಾಗದಲ್ಲಿನ ಘಟಕಗಳ ಸಂಖ್ಯೆ ಎಷ್ಟು? ಹೈಪರ್ ಪ್ಲೇನ್ಗಳು ಸಾಮಾನ್ಯ ಸ್ಥಾನದಲ್ಲಿರುವಾಗ ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಘಟಕಗಳನ್ನು ಸಾಧಿಸಲಾಗುತ್ತದೆ, ಅಂದರೆ, ಯಾವುದೇ ಎರಡು ಸಮಾನಾಂತರವಾಗಿಲ್ಲ ಮತ್ತು ಯಾವುದೇ ಮೂರು ಒಂದೇ ಛೇದಕವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ಈ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಘಟಕಗಳನ್ನು ಹೀಗೆ ಸೂಚಿಸಿ. ನಂತರ, ಈ ಕೆಳಗಿನ ಪುನರಾವರ್ತಿತ ಸಂಬಂಧವು ಈ ಕೆಳಗಿನಂತೆ ಇರುತ್ತದೆಃ-ಯಾವುದೇ ಆಯಾಮಗಳಿಲ್ಲದಿದ್ದಾಗ, ಒಂದೇ ಒಂದು ಬಿಂದುವು ಇರುತ್ತದೆ. - ಯಾವುದೇ ಹೈಪರ್ ಪ್ಲೇನ್ಗಳು ಇಲ್ಲದಿದ್ದಾಗ, ಎಲ್ಲಾ ಜಾಗವು ಒಂದೇ ಅಂಶವಾಗಿದೆ. ಮತ್ತು ಅದರ ಪರಿಹಾರವೆಂದರೆಃ ವೇಳೆ (ಉದಾಹರಣೆಗೆ ಪರಿಗಣಿಸಿ. ಲಂಬ ಹೈಪರ್ ಪ್ಲೇನ್ಗಳು; ಪ್ರತಿ ಹೆಚ್ಚುವರಿ ಹೈಪರ್ ಪ್ಲೇನ್ ಅಸ್ತಿತ್ವದಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಘಟಕವನ್ನು 2 ಎಂದು ವಿಭಜಿಸುತ್ತದೆ). ಇದು ಈ ರೀತಿ ಮೇಲಿನ ಮಿತಿಯನ್ನು ಹೊಂದಿದೆಃ ಬೈನರಿ ಸ್ಪೇಸ್ ಪಾರ್ಟಿಷನಿಂಗ್ ಡಿಸ್ಕ್ರೀಟ್ ಗ್ಲೋಬಲ್ ಗ್ರಿಡ್ ಪಾಲಿಗಾನ್ ಪಾರ್ಟಿಷನ್ ಟೆಸಿಲೇಷನ್ ಉಲ್ಲೇಖಗಳು ಕಂಪ್ಯೂಟರ್ ಗ್ರಾಫಿಕ್ಸ್ ಜ್ಯಾಮಿತೀಯ ಕ್ರಮಾವಳಿಗಳನ್ನು ಸಹ ನೋಡಿ