ऋजुरेखीय बहुभुज: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (7 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Polygon in which all angles are right}} | {{Short description|Polygon in which all angles are right}} | ||
{{About|समकोण बहुभुज|यूक्लिड के तत्वों में दी गई परिभाषा|बहुभुज}} | {{About|समकोण बहुभुज|यूक्लिड के तत्वों में दी गई परिभाषा|बहुभुज}} | ||
[[File:Rectilinear polygons.svg|thumb|सरल रेखीय बहुभुज के कुछ उदाहरण]] | [[File:Rectilinear polygons.svg|thumb|सरल रेखीय बहुभुज के कुछ उदाहरण]]'''ऋजुरेखीय [[बहुभुज]]''' एक बहुभुज है जिसकी सभी बहुभुज भुजाएँ [[समकोण]] पर मिलती हैं। इस प्रकार प्रत्येक शीर्ष पर आंतरिक कोण या तो 90° या 270° होता है। ऋजुरेखीय बहुभुज [[आइसोथेटिक बहुभुज]] की एक विशेष स्थिति है। | ||
अनेक स्थितियों में एक और परिभाषा उपयुक्त मानी गयी है: | अनेक स्थितियों में एक और परिभाषा उपयुक्त मानी गयी है: | ||
ऋजुरेखीय बहुभुज एक बहुभुज है जिसमें भुजाएँ [[कार्तीय समन्वय प्रणाली|कार्तीय निर्देशांक]] के अक्षों के समानांतर होती हैं। बहुभुजों के समुच्चय के बारे में बात करने पर यह अंतर महत्वपूर्ण हो जाता है : बाद की परिभाषा का अर्थ यह होगा कि समुच्चय में सभी बहुभुज की भुजाओं को समान समन्वय अक्षों के साथ संरेखित किया जाता है। दूसरी परिभाषा के ढांचे के भीतर एक [[आयत|आयताकार]] बहुभुज के क्षैतिज किनारों और ऊर्ध्वाधर किनारों के बारे में बात करना स्वाभाविक है। | |||
ऋजुरेखीय बहुभुजों को लंबकोणीय बहुभुज के रूप में भी जाना जाता है। आइसो-ओरिएंटेड, एक्सिस-अलाइन्ड और एक्सिस-ओरिएंटेड बहुभुज, उपयोग में आने वाली अन्य शर्तें हैं। जब इस प्रकार के बहुभुज आयत होते हैं तो ये विशेषण कम भ्रामक होते हैं, और शब्द अक्ष-संरेखित आयत को प्राथमिकता दी जाती है, चूंकि लंबकोणीय आयत और आयताकार आयत को उसी शब्द से जाना जाता हैं। | ऋजुरेखीय बहुभुजों को लंबकोणीय बहुभुज के रूप में भी जाना जाता है। आइसो-ओरिएंटेड, एक्सिस-अलाइन्ड और एक्सिस-ओरिएंटेड बहुभुज, उपयोग में आने वाली अन्य शर्तें हैं। जब इस प्रकार के बहुभुज आयत होते हैं तो ये विशेषण कम भ्रामक होते हैं, और शब्द अक्ष-संरेखित आयत को प्राथमिकता दी जाती है, चूंकि लंबकोणीय आयत और आयताकार आयत को उसी शब्द से जाना जाता हैं। | ||
| Line 14: | Line 14: | ||
== तत्व == | == तत्व == | ||
आयताकार बहुभुज के दो प्रकार के किनारे होते हैं: क्षैतिज और लंबवत। | |||
[[File:Simply Connected Rectilinear Polygon.png|thumbnail|X | [[File:Simply Connected Rectilinear Polygon.png|thumbnail|X उत्तल कोनों को चिन्हित करता है; O अवतल कोनों को चिह्नित करता है। नीली रेखाएँ नॉब हैं; लाल रेखाएँ एंटी-नॉब्स हैं; पीली रेखाएँ न तो नॉब और न ही एंटी-नॉब्स हैं।]] | ||
* लेम्मा: क्षैतिज किनारों की संख्या ऊर्ध्वाधर किनारों की संख्या के बराबर होती है (क्योंकि प्रत्येक क्षैतिज किनारे के बाद एक ऊर्ध्वाधर किनारा होता है और इसके विपरीत)। | * लेम्मा: क्षैतिज किनारों की संख्या ऊर्ध्वाधर किनारों की संख्या के बराबर होती है (क्योंकि प्रत्येक क्षैतिज किनारे के बाद एक ऊर्ध्वाधर किनारा होता है और इसके विपरीत)। | ||
** कोरोलरी: लंबकोणीय पॉलीगोन में किनारों की एक समान संख्या होती है। | ** कोरोलरी: लंबकोणीय पॉलीगोन में किनारों की एक समान संख्या होती है। | ||
सरलरेखीय बहुभुज में दो प्रकार के कोने होते हैं: वे कोने जिनमें छोटा कोण (90°) बहुभुज के आंतरिक होता है, उत्तल कहलाते हैं और वे कोने जिनमें बड़ा कोण (270°) आंतरिक होता है, अवतल कहलाते हैं।<ref name="bybc96">{{Cite journal | doi = 10.1142/S021819599600006X| title = समान आयतों के साथ सरल बहुभुजों को कवर करने के लिए एक रेखीय-समय एल्गोरिथम| journal = International Journal of Computational Geometry & Applications| volume = 06| pages = 79–102| year = 1996| last1 = Bar-Yehuda | first1 = R. | last2 = Ben-Hanoch | first2 = E. }}</ref> | |||
एक | एक नॉब्स एक किनारा है जिसके दो अंत बिंदु उत्तल कोने होते हैं। एक एंटीकनॉब एक किनारा है जिसके दो अंत बिंदु अवतल कोने होते हैं।<ref name="bybc96" /> | ||
== सरल आयताकार बहुभुज == | == सरल आयताकार बहुभुज == | ||
आयताकार बहुभुज जो कि सरल बहुभुज भी है, उसे छिद्र-मुक्त भी कहा जाता है क्योंकि इसमें कोई छिद्र नहीं होता है - केवल एक सतत सीमा होती है। इसके अनेक रोचक गुण हैं: | |||
# उत्तल किनारों की संख्या अवतल किनारों की संख्या से चार अधिक है। यह देखने के लिए, कल्पना करें कि आप बहुभुज की सीमा को दक्षिणावर्त पार करते हैं (अपने दाहिने हाथ को बहुभुज के अंदर और अपने बाएं हाथ को बहुभुज के बाहर की ओर रखकर)। उत्तल कोने पर, आप 90° दाएं मुड़ते हैं और किसी अवतल कोने पर आप 90° बाएँ मुड़ जाते हैं। अंत में आपको संपूर्ण 360° मुड़ना होगा और उस वास्तविक बिंदु पर वापस आना होगा; इसलिए दाएँ घुमावों की संख्या बाएँ घुमावों की संख्या से 4 अधिक होनी चाहिए। | # उत्तल किनारों की संख्या अवतल किनारों की संख्या से चार अधिक है। यह देखने के लिए, कल्पना करें कि आप बहुभुज की सीमा को दक्षिणावर्त पार करते हैं (अपने दाहिने हाथ को बहुभुज के अंदर और अपने बाएं हाथ को बहुभुज के बाहर की ओर रखकर)। उत्तल कोने पर, आप 90° दाएं मुड़ते हैं और किसी अवतल कोने पर आप 90° बाएँ मुड़ जाते हैं। अंत में आपको संपूर्ण 360° मुड़ना होगा और उस वास्तविक बिंदु पर वापस आना होगा; इसलिए दाएँ घुमावों की संख्या बाएँ घुमावों की संख्या से 4 अधिक होनी चाहिए। | ||
| Line 31: | Line 31: | ||
== एक आयताकार बहुभुज में वर्ग और आयत == | == एक आयताकार बहुभुज में वर्ग और आयत == | ||
बहुभुज के किनारों के समानांतर किनारों के साथ एक आयताकार बहुभुज को परिमित संख्या में वर्गों या आयतों द्वारा | बहुभुज के किनारों के समानांतर किनारों के साथ एक आयताकार बहुभुज को परिमित संख्या में वर्गों या आयतों द्वारा आच्छादित किया जा सकता है (बहुभुज आच्छादन देखें)। एक निश्चित आयताकार बहुभुज P में निहित अनेक प्रकार के वर्गों/आयतों में अंतर करना संभव है:<ref name=bybc96/> | ||
बहुभुज '' | बहुभुज ''P'' में एक अधिकतम वर्ग P में एक वर्ग है जो ''P'' में किसी अन्य वर्ग में सम्मलित नहीं है। इसी तरह, एक अधिकतम आयत एक आयत है जो ''P'' में किसी अन्य आयत में सम्मलित नहीं है। | ||
एक वर्ग ''s'' ''P'' में अधिकतम होता है यदि ''s'' के आसन्न किनारों की प्रत्येक जोड़ी ''P'' की सीमा को काटती है। दोनों पक्षों का प्रमाण | एक वर्ग ''s,'' ''P'' में अधिकतम होता है यदि ''s'' के आसन्न किनारों की प्रत्येक जोड़ी ''P'' की सीमा को काटती है। विरोधाभास द्वारा दोनों पक्षों का प्रमाण है: | ||
* यदि ''s'' में एक निश्चित सन्निकट जोड़ी ''P'' की सीमा को नहीं काटती है, तो इस जोड़ी को आगे सीमा की ओर धकेला जाता है, इसलिए ''s'' अधिकतम नहीं है। | * यदि ''s'' में एक निश्चित सन्निकट जोड़ी ''P'' की सीमा को नहीं काटती है, तो इस जोड़ी को आगे सीमा की ओर धकेला जाता है, इसलिए ''s'' अधिकतम नहीं है। | ||
* यदि '' | * यदि ''P'' में ''s'' अधिकतम नहीं है, तो ''P'' में ''s'' को समाहित करने वाला एक बड़ा वर्ग है; इस बड़े वर्ग के आंतरिक भाग में ''s'' के निकटवर्ती किनारों की एक जोड़ी है, इसलिए यह जोड़ी ''P'' की सीमा को नहीं काटती है। | ||
पहली दिशा आयतों के लिए भी सही है, अर्थात: यदि एक आयत ''s'' अधिकतम है, तो ''s'' के आसन्न किनारों की प्रत्येक जोड़ी ''P'' की सीमा को काटती है। दूसरी दिशा आवश्यक रूप से सत्य नहीं है: एक आयत ''P'' की सीमा को 3 आसन्न पक्षों में भी काट सकता है और फिर भी यह अधिकतम नहीं हो सकता है क्योंकि इसे 4 पक्ष में बढ़ाया जा सकता है। | पहली दिशा आयतों के लिए भी सही है, अर्थात: यदि एक आयत ''s'' अधिकतम है, तो ''s'' के आसन्न किनारों की प्रत्येक जोड़ी ''P'' की सीमा को काटती है। दूसरी दिशा आवश्यक रूप से सत्य नहीं है: एक आयत ''P'' की सीमा को 3 आसन्न पक्षों में भी काट सकता है और फिर भी यह अधिकतम नहीं हो सकता है क्योंकि इसे 4 पक्ष में बढ़ाया जा सकता है। | ||
| Line 43: | Line 43: | ||
उपप्रमेय: 'P' में प्रत्येक अधिकतम वर्ग/आयत में कम से कम दो बिंदु होते हैं, दो विपरीत किनारों पर, जो 'P' की सीमा को काटते हैं। | उपप्रमेय: 'P' में प्रत्येक अधिकतम वर्ग/आयत में कम से कम दो बिंदु होते हैं, दो विपरीत किनारों पर, जो 'P' की सीमा को काटते हैं। | ||
कोने का एक वर्ग एक बहुभुज ''P'' में एक अधिकतम वर्ग ''s'' है, जैसे कि ''s'' का कम से कम एक कोना ''P'' के उत्तल कोने को ओवरलैप करता है। प्रत्येक उत्तल कोने के लिए, इसे आच्छादित करने वाला एक अधिकतम (कोना) वर्ग होता है, लेकिन एक अधिकतम वर्ग एक से अधिक कोने को आच्छादित कर सकता है। प्रत्येक कोने के लिए, इसे आच्छादित करने वाले अनेक अलग-अलग अधिकतम आयत हो सकते हैं। | |||
[[File:Simple Rectilinear Polygon with Squares.png|thumb| | [[File:Simple Rectilinear Polygon with Squares.png|thumb|निर्वाहक और विभाजक]] | ||
[[File:Continuator types.png|thumb| | [[File:Continuator types.png|thumb|निर्वाहको के प्रकार]]बहुभुज ''P'' में एक विभाजक वर्ग ''P'' में एक वर्ग ''s'' है जैसे कि ''P''−''s' जुड़ा नहीं है। | ||
* ''लेम्मा'': एक साधारण आयताकार बहुभुज में, एक अधिकतम वर्ग जिसमें एक | * ''लेम्मा'': एक साधारण आयताकार बहुभुज में, एक अधिकतम वर्ग जिसमें एक नॉब्स नहीं होती है, एक विभाजक है।<ref name=ao81>{{Cite journal | doi = 10.1137/0602026| title = क्षेत्रों को वर्गों से आच्छादित करना| journal = SIAM Journal on Algebraic and Discrete Methods| volume = 2| issue = 3| pages = 240| year = 1981| last1 = Albertson | first1 = M. O. | last2 = o’Keefe | first2 = C. J. }}</ref> नॉब को समाहित करने वाला वर्ग, विभाजक हो भी सकता है और नहीं भी। विभिन्न विभाजक वर्गों की संख्या अनंत और अगणनीय भी हो सकती है। उदाहरण के लिए, एक आयत में, प्रत्येक अधिकतम वर्ग जो छोटी भुजाओं में से किसी एक को स्पर्श नहीं करता है, एक विभाजक है। | ||
निर्वाहक वर्ग, एक बहुभुज ''P'' में एक वर्ग ''S'' है जैसे कि ''S'' की सीमा और ''P'' की सीमा के बीच का प्रतिच्छेदन निरंतर है। एक अधिकतम निर्वाहक हमेशा एक कोने वाला वर्ग होता है। इसके अतिरिक्त, एक अधिकतम निर्वाहक में हमेशा एक नॉब्स होती है। इसलिए निर्वाहको की संख्या हमेशा परिमित होती है और नॉब्स की संख्या से बंधी होती है। | |||
उनमें | उनमें उपस्थित नॉब्स की संख्या और उनकी आंतरिक संरचना (चित्र देखें) के आधार पर अनेक अलग-अलग प्रकार के निर्वाहक हैं। एक निर्वाहको के ''बालकनी'' को इसके बिंदुओं के रूप में परिभाषित किया गया है जो किसी अन्य अधिकतम वर्ग (चित्र देखें) द्वारा आच्छादित नहीं किया गया है। | ||
कोई वर्ग | कोई वर्ग निर्वाहक और विभाजक दोनों नहीं हो सकता। सामान्य बहुभुजों में, ऐसे वर्ग हो सकते हैं जो न तो निर्वाहक और न ही विभाजक हों, लेकिन साधारण बहुभुजों में ऐसा नहीं हो सकता है:<ref name=bybc96/> | ||
# एक साधारण आयताकार बहुभुज में जो एक वर्ग नहीं है, कम से कम दो | # एक साधारण आयताकार बहुभुज में, प्रत्येक अधिकतम वर्ग या तो एक विभाजक या एक निर्वाहक होता है। यह आयतों के लिए भी सत्य है: प्रत्येक अधिकतम आयत या तो एक विभाजक या एक निर्वाहक है। | ||
#एक साधारण आयताकार बहुभुज में जो एक वर्ग नहीं है, कम से कम दो निर्वाहक होते हैं। | |||
साधारण बहुभुज में अधिकतम वर्गों और एक पेड़ में नोड्स के बीच एक रोचक सादृश्य है: एक निर्वाहक पत्ती के नोड के अनुरूप है और एक विभाजक एक आंतरिक नोड के अनुरूप है। | |||
== विशेष | == विशेष स्थितियाँ == | ||
सबसे सरल आयताकार बहुभुज एक अक्ष-संरेखित आयत है - एक आयत जिसमें 2 भुजाएँ x अक्ष के समानांतर और 2 भुजाएँ y अक्ष के समानांतर होती हैं। यह भी देखें: [[न्यूनतम बाउंडिंग आयत]]। | सबसे सरल आयताकार बहुभुज एक अक्ष-संरेखित आयत है - एक आयत जिसमें 2 भुजाएँ x अक्ष के समानांतर और 2 भुजाएँ y अक्ष के समानांतर होती हैं। यह भी देखें: [[न्यूनतम बाउंडिंग आयत|न्यूनतम सीमा आयत]]। | ||
[[जगहें|गोलिगॉन]] एक ऋजुरेखीय बहुभुज है जिसकी भुजाओं की लंबाई क्रम से लेने पर, क्रमागत पूर्णांक. होती है। | |||
एक | एक ऋजुरेखीय बहुभुज जो एक आयत नहीं है, कभी भी [[उत्तल बहुभुज]] नहीं होता है, लेकिन यह लम्बवत रूप से उत्तल हो सकता है। लम्बवत उत्तल सरलरेखीय बहुभुज देखें <!-- bold because redirects here -->. | ||
एक मोनोटोन | एक मोनोटोन ऋजुरेखीय बहुभुज एक [[मोनोटोन बहुभुज]] है जो आयताकार बहुभुज भी है। | ||
टी-स्क्वायर रोचक गुणों वाले ऋजुरेखीय बहुभुज के अनुक्रम से उत्पन्न एक फ्रैक्टल है। | |||
== सामान्यीकरण == | == सामान्यीकरण == | ||
* | * लंबकोणीय बहुभुज - 3D में लंबकोणीय बहुभुजों का प्राकृतिक सामान्यीकरण। | ||
* | * ऋजुरेखीयता [http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/trans/tp/&toc=comp/trans/tp/2003/09/i9toc.xml&DOI=10.1109/TPAMI.2003.1227997] | ||
== रेखीय बहुभुजों से संबंधित एल्गोरिथम समस्याएँ == | == रेखीय बहुभुजों से संबंधित एल्गोरिथम समस्याएँ == | ||
उनमें से अधिकांश को सामान्य बहुभुजों के लिए भी कहा जा सकता है, लेकिन अधिक कुशल एल्गोरिदम की अपेक्षा पर अलग से विचार किया जाना चाहिए | उनमें से अधिकांश को सामान्य बहुभुजों के लिए भी कहा जा सकता है, लेकिन अधिक कुशल एल्गोरिदम की अपेक्षा पर अलग से विचार किया जाना चाहिए | ||
*[[ऑर्थोगोनल रेंज खोज|लंबकोणीय | *[[ऑर्थोगोनल रेंज खोज|लंबकोणीय विस्तार खोज]] | ||
*[[ऑर्थोगोनल उत्तल पतवार|लंबकोणीय उत्तल | *[[ऑर्थोगोनल उत्तल पतवार|लंबकोणीय उत्तल आवरण]] निर्माण | ||
*लंबकोणीय बहुभुजों के लिए [[बहुभुजों पर बूलियन संचालन]] (उदाहरण के लिए, प्रतिच्छेदन | *लंबकोणीय बहुभुजों के लिए [[बहुभुजों पर बूलियन संचालन|बहुभुजों पर बूलियन क्रियाविधि]] (उदाहरण के लिए, प्रतिच्छेदन और [[संघ (सेट सिद्धांत)|संघ]] ) | ||
* [[मोशन प्लानिंग]] / [[पथ योजना]] / [[मार्ग]] | * [[मोशन प्लानिंग|गति की योजना]] / [[पथ योजना]] / ऋजुरेखीय बाधाओं के बीच [[मार्ग]] योजना | ||
*[[दृश्यता की समस्या]] | *[[दृश्यता की समस्या|दृश्यता की समस्याएं]] ([[रोशनी की समस्या]]एं) | ||
** | **ऋजुरेखीय आर्ट गैलरी की समस्याएं | ||
* [[अधिकतम खाली आयत]] | * [[अधिकतम खाली आयत]] | ||
== आयताकार अपघटन == | == आयताकार अपघटन == | ||
सरलरेखीय बहुभुजों के लिए विशेष रुचि एक दिए गए सरलरेखीय बहुभुज को सरल इकाइयों - | सरलरेखीय बहुभुजों के लिए विशेष रुचि एक दिए गए सरलरेखीय बहुभुज को सरल इकाइयों - सामान्यतः आयतों या वर्गों में विघटित करने की समस्याएं हैं। अपघटन की समस्याएँ अनेक प्रकार की होती हैं: | ||
* समस्याओं को | * समस्याओं को आच्छादित करने में, लक्ष्य इकाइयों (वर्गों या आयतों) का सबसे छोटा समूह खोजना है, जिसका मिलन बहुभुज के बराबर हो। इकाइयां ओवरलैप हो सकती हैं। बहुभुज आवरण देखें। | ||
* पैकिंग समस्याओं में, लक्ष्य गैर-अतिव्यापी इकाइयों का सबसे बड़ा समूह खोजना है जिसका संघ बहुभुज में समाहित है। संघ बहुभुज से छोटा हो सकता है। | * पैकिंग समस्याओं में, लक्ष्य गैर-अतिव्यापी इकाइयों का सबसे बड़ा समूह खोजना है जिसका संघ बहुभुज में समाहित है। संघ बहुभुज से छोटा हो सकता है। | ||
* विभाजन की समस्याओं में, लक्ष्य गैर-अतिव्यापी इकाइयों का सबसे छोटा समूह खोजना है जिसका संघ बहुभुज के बराबर है। [[बहुभुज विभाजन]] देखें। | * विभाजन की समस्याओं में, लक्ष्य गैर-अतिव्यापी इकाइयों का सबसे छोटा समूह खोजना है जिसका संघ बहुभुज के बराबर है। [[बहुभुज विभाजन]] देखें। | ||
| Line 94: | Line 95: | ||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | [[Category:Articles with hatnote templates targeting a nonexistent page]] | ||
[[Category:Articles with short description]] | [[Category:Articles with short description]] | ||
[[Category:CS1 français-language sources (fr)]] | |||
[[Category:CS1 maint]] | |||
[[Category:CS1 Ελληνικά-language sources (el)]] | |||
[[Category:Citation Style 1 templates|W]] | |||
[[Category:Collapse templates]] | |||
[[Category:Created On 27/11/2022]] | [[Category:Created On 27/11/2022]] | ||
[[Category:Machine Translated Page]] | [[Category:Machine Translated Page]] | ||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Short description with empty Wikidata description]] | [[Category:Short description with empty Wikidata description]] | ||
[[Category:Sidebars with styles needing conversion]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates based on the Citation/CS1 Lua module]] | |||
[[Category:Templates generating COinS|Cite web]] | |||
[[Category:Templates generating microformats]] | |||
[[Category:Templates that are not mobile friendly]] | |||
[[Category:Templates used by AutoWikiBrowser|Cite web]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Wikipedia fully protected templates|Cite web]] | |||
[[Category:Wikipedia metatemplates]] | |||
[[Category:बहुभुजों के प्रकार]] | [[Category:बहुभुजों के प्रकार]] | ||
Latest revision as of 10:29, 28 December 2022
ऋजुरेखीय बहुभुज एक बहुभुज है जिसकी सभी बहुभुज भुजाएँ समकोण पर मिलती हैं। इस प्रकार प्रत्येक शीर्ष पर आंतरिक कोण या तो 90° या 270° होता है। ऋजुरेखीय बहुभुज आइसोथेटिक बहुभुज की एक विशेष स्थिति है।
अनेक स्थितियों में एक और परिभाषा उपयुक्त मानी गयी है:
ऋजुरेखीय बहुभुज एक बहुभुज है जिसमें भुजाएँ कार्तीय निर्देशांक के अक्षों के समानांतर होती हैं। बहुभुजों के समुच्चय के बारे में बात करने पर यह अंतर महत्वपूर्ण हो जाता है : बाद की परिभाषा का अर्थ यह होगा कि समुच्चय में सभी बहुभुज की भुजाओं को समान समन्वय अक्षों के साथ संरेखित किया जाता है। दूसरी परिभाषा के ढांचे के भीतर एक आयताकार बहुभुज के क्षैतिज किनारों और ऊर्ध्वाधर किनारों के बारे में बात करना स्वाभाविक है।
ऋजुरेखीय बहुभुजों को लंबकोणीय बहुभुज के रूप में भी जाना जाता है। आइसो-ओरिएंटेड, एक्सिस-अलाइन्ड और एक्सिस-ओरिएंटेड बहुभुज, उपयोग में आने वाली अन्य शर्तें हैं। जब इस प्रकार के बहुभुज आयत होते हैं तो ये विशेषण कम भ्रामक होते हैं, और शब्द अक्ष-संरेखित आयत को प्राथमिकता दी जाती है, चूंकि लंबकोणीय आयत और आयताकार आयत को उसी शब्द से जाना जाता हैं।
सरलरेखीय बहुभुजों के वर्ग का महत्व निम्नलिखित के अनुसार प्राप्त किया जाता है।
- वे डिजाइन और निर्माण में अपनी सादगी के कारण एकीकृत सर्किट एकीकृत सर्किट लेआउट में आकृतियों के प्रतिनिधित्व के लिए सुविधाजनक हैं। अनेक निर्मित वस्तुओं का परिणाम लंबकोणीय बहुभुज होता है।
- कम्प्यूटेशनल ज्यामिति में समस्याएं बहुभुज के संदर्भ में बताई गई हैं, जो अक्सर लंबकोणीय बहुभुजों तक सीमित होने पर अधिक कम्प्यूटेशनल जटिलता सिद्धांत की अनुमति देती हैं। लंबकोणीय बहुभुजों के लिए आर्ट गैलरी प्रमेय द्वारा एक उदाहरण प्रदान किया गया है, जो मनमाने बहुभुजों की तुलना में अधिक कुशल गार्ड कवरेज की ओर ले जाता है।
तत्व
आयताकार बहुभुज के दो प्रकार के किनारे होते हैं: क्षैतिज और लंबवत।
- लेम्मा: क्षैतिज किनारों की संख्या ऊर्ध्वाधर किनारों की संख्या के बराबर होती है (क्योंकि प्रत्येक क्षैतिज किनारे के बाद एक ऊर्ध्वाधर किनारा होता है और इसके विपरीत)।
- कोरोलरी: लंबकोणीय पॉलीगोन में किनारों की एक समान संख्या होती है।
सरलरेखीय बहुभुज में दो प्रकार के कोने होते हैं: वे कोने जिनमें छोटा कोण (90°) बहुभुज के आंतरिक होता है, उत्तल कहलाते हैं और वे कोने जिनमें बड़ा कोण (270°) आंतरिक होता है, अवतल कहलाते हैं।[1] एक नॉब्स एक किनारा है जिसके दो अंत बिंदु उत्तल कोने होते हैं। एक एंटीकनॉब एक किनारा है जिसके दो अंत बिंदु अवतल कोने होते हैं।[1]
सरल आयताकार बहुभुज
आयताकार बहुभुज जो कि सरल बहुभुज भी है, उसे छिद्र-मुक्त भी कहा जाता है क्योंकि इसमें कोई छिद्र नहीं होता है - केवल एक सतत सीमा होती है। इसके अनेक रोचक गुण हैं:
- उत्तल किनारों की संख्या अवतल किनारों की संख्या से चार अधिक है। यह देखने के लिए, कल्पना करें कि आप बहुभुज की सीमा को दक्षिणावर्त पार करते हैं (अपने दाहिने हाथ को बहुभुज के अंदर और अपने बाएं हाथ को बहुभुज के बाहर की ओर रखकर)। उत्तल कोने पर, आप 90° दाएं मुड़ते हैं और किसी अवतल कोने पर आप 90° बाएँ मुड़ जाते हैं। अंत में आपको संपूर्ण 360° मुड़ना होगा और उस वास्तविक बिंदु पर वापस आना होगा; इसलिए दाएँ घुमावों की संख्या बाएँ घुमावों की संख्या से 4 अधिक होनी चाहिए।
- उपप्रमेय: प्रत्येक आयताकार बहुभुज में कम से कम 4 उत्तल किनारे होते हैं।
- नॉब्स (दो उत्तल किनारों को जोड़ने वाली भुजाएँ) की संख्या एंटीनॉब्स (दो अवतल किनारों को जोड़ने वाली भुजाएँ) की संख्या से चार अधिक है। यह देखने के लिए कि ऐसा क्यों होता है, X को उत्तल किनारों की संख्या और Y को अवतल किनारों की संख्या मान लेते है। पिछले तथ्य से, X=Y+4। माना XX उत्तल किनारों की संख्या के बाद एक उत्तल कोने, XY उत्तल किनारों की संख्या के बाद एक अवतल कोने, YX और YY को समान रूप से परिभाषित करते हैं। फिर निश्चित रूप से X=XX+XY=XX+YX और Y=XY+YY=YX+YY। इसलिए XX=X-XY=X-(Y-YY)=YY+(X-Y)=YY+4।[2]
- उपप्रमेय: प्रत्येक सरलरेखीय बहुभुज में कम से कम 4 नॉब्स होती हैं।
एक आयताकार बहुभुज में वर्ग और आयत
बहुभुज के किनारों के समानांतर किनारों के साथ एक आयताकार बहुभुज को परिमित संख्या में वर्गों या आयतों द्वारा आच्छादित किया जा सकता है (बहुभुज आच्छादन देखें)। एक निश्चित आयताकार बहुभुज P में निहित अनेक प्रकार के वर्गों/आयतों में अंतर करना संभव है:[1]
बहुभुज P में एक अधिकतम वर्ग P में एक वर्ग है जो P में किसी अन्य वर्ग में सम्मलित नहीं है। इसी तरह, एक अधिकतम आयत एक आयत है जो P में किसी अन्य आयत में सम्मलित नहीं है।
एक वर्ग s, P में अधिकतम होता है यदि s के आसन्न किनारों की प्रत्येक जोड़ी P की सीमा को काटती है। विरोधाभास द्वारा दोनों पक्षों का प्रमाण है:
- यदि s में एक निश्चित सन्निकट जोड़ी P की सीमा को नहीं काटती है, तो इस जोड़ी को आगे सीमा की ओर धकेला जाता है, इसलिए s अधिकतम नहीं है।
- यदि P में s अधिकतम नहीं है, तो P में s को समाहित करने वाला एक बड़ा वर्ग है; इस बड़े वर्ग के आंतरिक भाग में s के निकटवर्ती किनारों की एक जोड़ी है, इसलिए यह जोड़ी P की सीमा को नहीं काटती है।
पहली दिशा आयतों के लिए भी सही है, अर्थात: यदि एक आयत s अधिकतम है, तो s के आसन्न किनारों की प्रत्येक जोड़ी P की सीमा को काटती है। दूसरी दिशा आवश्यक रूप से सत्य नहीं है: एक आयत P की सीमा को 3 आसन्न पक्षों में भी काट सकता है और फिर भी यह अधिकतम नहीं हो सकता है क्योंकि इसे 4 पक्ष में बढ़ाया जा सकता है।
उपप्रमेय: 'P' में प्रत्येक अधिकतम वर्ग/आयत में कम से कम दो बिंदु होते हैं, दो विपरीत किनारों पर, जो 'P' की सीमा को काटते हैं।
कोने का एक वर्ग एक बहुभुज P में एक अधिकतम वर्ग s है, जैसे कि s का कम से कम एक कोना P के उत्तल कोने को ओवरलैप करता है। प्रत्येक उत्तल कोने के लिए, इसे आच्छादित करने वाला एक अधिकतम (कोना) वर्ग होता है, लेकिन एक अधिकतम वर्ग एक से अधिक कोने को आच्छादित कर सकता है। प्रत्येक कोने के लिए, इसे आच्छादित करने वाले अनेक अलग-अलग अधिकतम आयत हो सकते हैं।
बहुभुज P में एक विभाजक वर्ग P में एक वर्ग s है जैसे कि P−s' जुड़ा नहीं है।
- लेम्मा: एक साधारण आयताकार बहुभुज में, एक अधिकतम वर्ग जिसमें एक नॉब्स नहीं होती है, एक विभाजक है।[3] नॉब को समाहित करने वाला वर्ग, विभाजक हो भी सकता है और नहीं भी। विभिन्न विभाजक वर्गों की संख्या अनंत और अगणनीय भी हो सकती है। उदाहरण के लिए, एक आयत में, प्रत्येक अधिकतम वर्ग जो छोटी भुजाओं में से किसी एक को स्पर्श नहीं करता है, एक विभाजक है।
निर्वाहक वर्ग, एक बहुभुज P में एक वर्ग S है जैसे कि S की सीमा और P की सीमा के बीच का प्रतिच्छेदन निरंतर है। एक अधिकतम निर्वाहक हमेशा एक कोने वाला वर्ग होता है। इसके अतिरिक्त, एक अधिकतम निर्वाहक में हमेशा एक नॉब्स होती है। इसलिए निर्वाहको की संख्या हमेशा परिमित होती है और नॉब्स की संख्या से बंधी होती है।
उनमें उपस्थित नॉब्स की संख्या और उनकी आंतरिक संरचना (चित्र देखें) के आधार पर अनेक अलग-अलग प्रकार के निर्वाहक हैं। एक निर्वाहको के बालकनी को इसके बिंदुओं के रूप में परिभाषित किया गया है जो किसी अन्य अधिकतम वर्ग (चित्र देखें) द्वारा आच्छादित नहीं किया गया है।
कोई वर्ग निर्वाहक और विभाजक दोनों नहीं हो सकता। सामान्य बहुभुजों में, ऐसे वर्ग हो सकते हैं जो न तो निर्वाहक और न ही विभाजक हों, लेकिन साधारण बहुभुजों में ऐसा नहीं हो सकता है:[1]
- एक साधारण आयताकार बहुभुज में, प्रत्येक अधिकतम वर्ग या तो एक विभाजक या एक निर्वाहक होता है। यह आयतों के लिए भी सत्य है: प्रत्येक अधिकतम आयत या तो एक विभाजक या एक निर्वाहक है।
- एक साधारण आयताकार बहुभुज में जो एक वर्ग नहीं है, कम से कम दो निर्वाहक होते हैं।
साधारण बहुभुज में अधिकतम वर्गों और एक पेड़ में नोड्स के बीच एक रोचक सादृश्य है: एक निर्वाहक पत्ती के नोड के अनुरूप है और एक विभाजक एक आंतरिक नोड के अनुरूप है।
विशेष स्थितियाँ
सबसे सरल आयताकार बहुभुज एक अक्ष-संरेखित आयत है - एक आयत जिसमें 2 भुजाएँ x अक्ष के समानांतर और 2 भुजाएँ y अक्ष के समानांतर होती हैं। यह भी देखें: न्यूनतम सीमा आयत।
गोलिगॉन एक ऋजुरेखीय बहुभुज है जिसकी भुजाओं की लंबाई क्रम से लेने पर, क्रमागत पूर्णांक. होती है।
एक ऋजुरेखीय बहुभुज जो एक आयत नहीं है, कभी भी उत्तल बहुभुज नहीं होता है, लेकिन यह लम्बवत रूप से उत्तल हो सकता है। लम्बवत उत्तल सरलरेखीय बहुभुज देखें .
एक मोनोटोन ऋजुरेखीय बहुभुज एक मोनोटोन बहुभुज है जो आयताकार बहुभुज भी है।
टी-स्क्वायर रोचक गुणों वाले ऋजुरेखीय बहुभुज के अनुक्रम से उत्पन्न एक फ्रैक्टल है।
सामान्यीकरण
- लंबकोणीय बहुभुज - 3D में लंबकोणीय बहुभुजों का प्राकृतिक सामान्यीकरण।
- ऋजुरेखीयता [1]
रेखीय बहुभुजों से संबंधित एल्गोरिथम समस्याएँ
उनमें से अधिकांश को सामान्य बहुभुजों के लिए भी कहा जा सकता है, लेकिन अधिक कुशल एल्गोरिदम की अपेक्षा पर अलग से विचार किया जाना चाहिए
- लंबकोणीय विस्तार खोज
- लंबकोणीय उत्तल आवरण निर्माण
- लंबकोणीय बहुभुजों के लिए बहुभुजों पर बूलियन क्रियाविधि (उदाहरण के लिए, प्रतिच्छेदन और संघ )
- गति की योजना / पथ योजना / ऋजुरेखीय बाधाओं के बीच मार्ग योजना
- दृश्यता की समस्याएं (रोशनी की समस्याएं)
- ऋजुरेखीय आर्ट गैलरी की समस्याएं
- अधिकतम खाली आयत
आयताकार अपघटन
सरलरेखीय बहुभुजों के लिए विशेष रुचि एक दिए गए सरलरेखीय बहुभुज को सरल इकाइयों - सामान्यतः आयतों या वर्गों में विघटित करने की समस्याएं हैं। अपघटन की समस्याएँ अनेक प्रकार की होती हैं:
- समस्याओं को आच्छादित करने में, लक्ष्य इकाइयों (वर्गों या आयतों) का सबसे छोटा समूह खोजना है, जिसका मिलन बहुभुज के बराबर हो। इकाइयां ओवरलैप हो सकती हैं। बहुभुज आवरण देखें।
- पैकिंग समस्याओं में, लक्ष्य गैर-अतिव्यापी इकाइयों का सबसे बड़ा समूह खोजना है जिसका संघ बहुभुज में समाहित है। संघ बहुभुज से छोटा हो सकता है।
- विभाजन की समस्याओं में, लक्ष्य गैर-अतिव्यापी इकाइयों का सबसे छोटा समूह खोजना है जिसका संघ बहुभुज के बराबर है। बहुभुज विभाजन देखें।
संदर्भ
- Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer. ISBN 0-387-96131-3. 1st edition: ; 2nd printing, corrected and expanded, 1988., chapter 8: "The Geometry of Rectangles"
- ↑ 1.0 1.1 1.2 1.3 Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "समान आयतों के साथ सरल बहुभुजों को कवर करने के लिए एक रेखीय-समय एल्गोरिथम". International Journal of Computational Geometry & Applications. 06: 79–102. doi:10.1142/S021819599600006X.
- ↑ "बिट्स के जोड़े की गिनती". Stack Exchange. November 17, 2013.
- ↑ Albertson, M. O.; o’Keefe, C. J. (1981). "क्षेत्रों को वर्गों से आच्छादित करना". SIAM Journal on Algebraic and Discrete Methods. 2 (3): 240. doi:10.1137/0602026.
