Multiple line segment intersection
ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿಯಲ್ಲಿ, ಬಹು ರೇಖೆ ವಿಭಾಗದ ಛೇದಕ ಸಮಸ್ಯೆಯು ಯೂಕ್ಲಿಡಿಯನ್ ಸಮತಲದಲ್ಲಿನ ರೇಖೆ ವಿಭಾಗಗಳ ಪಟ್ಟಿಯನ್ನು ಒದಗಿಸುತ್ತದೆ ಮತ್ತು ಅವುಗಳಲ್ಲಿ ಯಾವುದಾದರೂ ಎರಡು ಛೇದಿಸುತ್ತವೆಯೇ (ಅಡ್ಡ) ಎಂದು ಕೇಳುತ್ತದೆ. ಸರಳ ಕ್ರಮಾವಳಿಗಳು ಪ್ರತಿಯೊಂದು ಜೋಡಿ ವಿಭಾಗಗಳನ್ನು ಪರಿಶೀಲಿಸುತ್ತವೆ. ಆದಾಗ್ಯೂ, ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಸಂಭಾವ್ಯವಾಗಿ ಛೇದಿಸುವ ವಿಭಾಗಗಳನ್ನು ಪರಿಶೀಲಿಸಬೇಕಾದರೆ, ಇದು ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾಗುವುದಿಲ್ಲ ಏಕೆಂದರೆ ಹೆಚ್ಚಿನ ಜೋಡಿ ವಿಭಾಗಗಳು ವಿಶಿಷ್ಟವಾದ ಇನ್ಪುಟ್ ಅನುಕ್ರಮದಲ್ಲಿ ಒಂದಕ್ಕೊಂದು ಹತ್ತಿರದಲ್ಲಿರುವುದಿಲ್ಲ. ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ವಿಭಾಗಗಳಿಗೆ ಈ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವ ಅತ್ಯಂತ ಸಾಮಾನ್ಯ ಮತ್ತು ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿಯಾದ ಮಾರ್ಗವೆಂದರೆ ಸ್ವೀಪ್ ಲೈನ್ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬಳಸುವುದು, ಅಲ್ಲಿ ನಾವು ರೇಖೆಯ ಭಾಗಗಳಾದ್ಯಂತ ಸ್ಲೈಡಿಂಗ್ ರೇಖೆಯನ್ನು ಊಹಿಸಿಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀಗಳ ಆಧಾರದ ಮೇಲೆ ಕ್ರಿಯಾತ್ಮಕ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಅದು ಯಾವ ರೇಖೆಯ ಭಾಗಗಳನ್ನು ಛೇದಿಸುತ್ತದೆ ಎಂಬುದನ್ನು ನಾವು ಟ್ರ್ಯಾಕ್ ಮಾಡುತ್ತೇವೆ. ಶಮೋಸ್-ಹೋಯ್ ಅಲ್ಗಾರಿದಮ್ ಈ ತತ್ವವನ್ನು ಲೈನ್ ಸೆಗ್ಮೆಂಟ್ ಇಂಟರ್ಸೆಕ್ಷನ್ ಡಿಟೆಕ್ಷನ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಅನ್ವಯಿಸುತ್ತದೆ, ಮೇಲೆ ಹೇಳಿದಂತೆ, ಲೈನ್ ಸೆಗ್ಮೆಂಟ್ಗಳ ಗುಂಪೊಂದು ಇಂಟರ್ಸೆಕ್ಷನ್ ಅನ್ನು ಹೊಂದಿದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸಲು; ಬೆಂಟ್ಲೆ-ಒಟ್ಮನ್ ಅಲ್ಗಾರಿದಮ್ ಪ್ರತಿ ಇಂಟರ್ಸೆಕ್ಷನ್ಗೆ ಲಾಗರಿಥಮಿಕ್ ಸಮಯದಲ್ಲಿ ಎಲ್ಲಾ ಇಂಟರ್ಸೆಕ್ಷನ್ಗಳನ್ನು ಪಟ್ಟಿ ಮಾಡಲು ಅದೇ ತತ್ವದಿಂದ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಬೆಂಟ್ಲೆ-ಒಟ್ಮನ್ ಅಲ್ಗಾರಿದಮ್ ಉಲ್ಲೇಖಗಳನ್ನು ಮತ್ತಷ್ಟು ಓದುವ ಅಧ್ಯಾಯ 2: ಲೈನ್ ಸೆಗ್ಮೆಂಟ್ ಇಂಟರ್ಸೆಕ್ಷನ್, ಪು. 19-44 ಅನ್ನು ಸಹ ನೋಡಿ. ಥಾಮಸ್ ಎಚ್. ಕಾರ್ಮೆನ್, ಚಾರ್ಲ್ಸ್ ಇ. ಲೀಸರ್ಸನ್, ರೊನಾಲ್ಡ್ ಎಲ್. ರಿವೆಸ್ಟ್ ಮತ್ತು ಕ್ಲಿಫರ್ಡ್ ಸ್ಟೀನ್. ಅಲ್ಗಾರಿದಮ್ಗಳ ಪರಿಚಯ, ಎರಡನೇ ಆವೃತ್ತಿ. ಎಮ್ಐಟಿ ಪ್ರೆಸ್ ಮತ್ತು ಮೆಕ್ಗ್ರಾ-ಹಿಲ್, 1990. ವಿಭಾಗ 33.2: ಯಾವುದೇ ಜೋಡಿ ವಿಭಾಗಗಳು ಛೇದಿಸುತ್ತವೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವುದು, pp. 934-947. ಜೆ. ಎಲ್. ಬೆಂಟ್ಲೆ ಮತ್ತು ಟಿ. ಓಟ್ಮನ್., ಜ್ಯಾಮಿತೀಯ ಛೇದಕಗಳನ್ನು ವರದಿ ಮಾಡಲು ಮತ್ತು ಎಣಿಸಲು ಕ್ರಮಾವಳಿಗಳು, ಐ. ಇ. ಇ. ಇ. ಟ್ರಾನ್ಸ್. ಗಣಕಯಂತ್ರ. C28 (1979), 643-647. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ರೇಖೆಗಳು ಮತ್ತು ವಿಮಾನಗಳ ಛೇದನ ಕ್ರಮಾವಳಿಗಳು ಮತ್ತು ಡಾನ್ ಸಂಡೇ ರಾಬರ್ಟ್ ಪ್ಲೆಸ್ ಅವರ ಮಾದರಿ ಕೋಡ್. ಉಪನ್ಯಾಸ 4 ಟಿಪ್ಪಣಿಗಳು. ಸೇಂಟ್ ಲೂಯಿಸ್ನಲ್ಲಿರುವ ವಾಷಿಂಗ್ಟನ್ ವಿಶ್ವವಿದ್ಯಾಲಯ, ಸಿಎಸ್ 506: ಕಂಪ್ಯೂಟೇಶನಲ್ ಜಿಯೋಮೆಟ್ರಿ (ಕ್ಯಾಶ್ ಮಾಡಲಾದ ಪ್ರತಿ). ಸಿಜಿಎಎಲ್ನಲ್ಲಿ ಲೈನ್ ಸೆಗ್ಮೆಂಟ್ ಇಂಟರ್ಸೆಕ್ಷನ್, ಜೆಫ್ ಎರಿಕ್ಸನ್ ಅವರ ಕಂಪ್ಯೂಟೇಶನಲ್ ಜಿಯೋಮೆಟ್ರಿ ಅಲ್ಗಾರಿದಮ್ಸ್ ಲೈಬ್ರರಿ "ಲೈನ್ ಸೆಗ್ಮೆಂಟ್ ಇಂಟರ್ಸೆಕ್ಷನ್" ಉಪನ್ಯಾಸ ಟಿಪ್ಪಣಿಗಳು. ಸಿ ಕೋಡ್ನೊಂದಿಗೆ ಲೈನ್-ಲೈನ್ ಇಂಟರ್ಸೆಕ್ಷನ್ ವಿಧಾನ ಮಾದರಿ ಡ್ಯಾರೆಲ್ ರೆಕ್ಸ್ ಫಿನ್ಲೆ ಜ್ಯಾಮಿತೀಯ ಕ್ರಮಾವಳಿಗಳು ಜ್ಯಾಮಿತೀಯ ಇಂಟರ್ಸೆಕ್ಷನ್ ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿ