अभिकलनात्मक ज्यामिति
अभिकलनात्मक ज्यामिति में, एक घुमाव रेखा कलन विधि या समतलीय घुमाव कलन विधि एक कलन विधि प्रतिमान है जो यूक्लिडियन स्थल में विभिन्न समस्याओं को हल करने के लिए एक वैचारिक 'घुमाव रेखा' या 'घुमाव सतह' का उपयोग करता है। यह अभिकलनात्मक ज्यामिति में महत्वपूर्ण तकनीकों में से एक है।
इस प्रकार की कलन विधि के पीछे का विचार यह कल्पना करना है कि एक रेखा (प्रायः एक लंबवत रेखा) कुछ बिंदुओं पर रुकते हुए तल में बह जाती है या चली जाती है। ज्यामितीय प्रचालन ज्यामितीय वस्तुओं तक ही सीमित हैं जो या तो घुमाव रेखा को काटती हैं या जब भी यह बंद हो जाती हैं तो इसके आसपास के क्षेत्र में होती हैं, और एक बार रेखा सभी वस्तुओं के ऊपर से पारित होने के बाद पूरा समाधान उपलब्ध होता है।
इतिहास
इस दृष्टिकोण को कंप्यूटर चित्रलेख में प्रतिपादन के कलन विधि को क्रमवीक्षण करने के लिए खोजा जा सकता है, इसके बाद एकीकृत परिपथ विन्यास अभिकल्पना के प्रारम्भिक कलन विधि में इस दृष्टिकोण का दोहन किया जा सकता है, जिसमें एक आईसी के ज्यामितीय विवरण को समानांतर पट्टी में संसाधित किया गया था क्योंकि संपूर्ण विवरण मेमोरी में फिट नहीं हो सका।[citation needed]
अनुप्रयोग
इस दृष्टिकोण के अनुप्रयोग से ज्यामितीय कलन विधि के कलन विधि के विश्लेषण में एक सफलता मिली जब माइकल इयान शमोस और होए ने तल में रेखा खंड प्रतिच्छेदन के लिए कलन विधि प्रस्तुत किया, और विशेष रूप से, उन्होंने वर्णन किया कि कैसे कुशल डेटा संरचनाओं (स्व-संतुलन युग्मक खोज ट्री) के साथ क्रमवीक्षण रेखा दृष्टिकोण का संयोजन यह पता लगाना संभव बनाता है कि O(N log N) की समय जटिलता में तल में N खंड के बीच प्रतिच्छेदन हैं या नहीं। [1] निकटता से संबंधित बेंटले-ओटमैन एल्गोरिथ्म O((N + K) log N) की समय जटिलता और O(N) की अंतरिक्ष जटिलता में तल में किसी भी N खंड के बीच सभी K प्रतिच्छेदन की प्रतिवेदन करने के लिए एक घुमाव रेखा तकनीक का उपयोग करता है। [2]
तब से, इस दृष्टिकोण का उपयोग कई समस्याओं के लिए कुशल कलन विधि को अभिकल्पित करने के लिए किया गया है, जैसे कि वोरोनोई आरेख (फॉर्च्यून की कलन विधि) का निर्माण और बहुभुजों पर डेलाउने त्रिभुज या बूलियन संचालन।
सामान्यीकरण और विस्तार
सांस्थितिक व्यापक समतलीय घुमाव का एक रूप है जिसमें प्रसंस्करण बिंदुओं का एक सरल क्रम होता है, जो बिंदुओं को पूरी तरह से क्रमबद्ध करने की आवश्यकता से बचा जाता है; यह कुछ घुमाव रेखा कलन विधि को अधिक कुशलता से निष्पादित करने की अनुमति देता है।
ज्यामितीय कलन विधि को अभिकल्पित करने के लिए घूर्णी कैलीपर्स तकनीक को निविष्ट समतलीय के प्रक्षेपीय द्वैध में समतलीय घुमाव के रूप में भी व्याख्या किया जा सकता है: प्रक्षेपीय द्वैत का रूप एक रेखा के ढलान को एक समतलीय के एक्स-निर्देशांक में बदल देता है। दोहरे तल में बिंदु, इसलिए उनके ढलान द्वारा वर्गीकरण किए गए क्रम में रेखाों के माध्यम से प्रगति, जैसा कि एक घूर्णन कैलीपर्स कलन विधि द्वारा किया जाता है, एक तल घुमाव कलन विधि में उनके एक्स-निर्देशांक द्वारा क्रमबद्ध बिंदुओं के माध्यम से प्रगति के लिए दोहरी है।
व्यापक दृष्टिकोण को उच्च आयामों के लिए सामान्यीकृत किया जा सकता है।[3]
संदर्भ
- ↑ Shamos, Michael I.; Hoey, Dan (1976), "Geometric intersection problems", Proc. 17th IEEE Symp. Foundations of Computer Science (FOCS '76), pp. 208–215, doi:10.1109/SFCS.1976.16, S2CID 124804.
- ↑ Souvaine, Diane (2008), Line Segment Intersection Using a Sweep Line Algorithm (PDF).
- ↑ Sinclair, David (2016-02-11). "A 3D Sweep Hull Algorithm for computing Convex Hulls and Delaunay Triangulation". arXiv:1602.04707 [cs.CG].
