ऋजुरेखीय बहुभुज

This article is about समकोण बहुभुज. For यूक्लिड के तत्वों में दी गई परिभाषा, see बहुभुज.

सरल रेखीय बहुभुज के कुछ उदाहरण

एक ऋजुरेखीय बहुभुज एक बहुभुज है जिसकी सभी बहुभुज भुजाएँ समकोण पर मिलती हैं। इस प्रकार प्रत्येक शीर्ष पर आंतरिक कोण या तो 90° या 270° होता है। ऋजुरेखीय बहुभुज आइसोथेटिक बहुभुज की एक विशेष स्थिति है।

अनेक स्थितियों में एक और परिभाषा उपयुक्त मानी गयी है:

एक ऋजुरेखीय बहुभुज एक बहुभुज है जिसमें भुजाएँ कार्तीय निर्देशांक के अक्षों के समानांतर होती हैं। बहुभुजों के समुच्चय के बारे में बात करने पर यह अंतर महत्वपूर्ण हो जाता है : बाद की परिभाषा का अर्थ यह होगा कि समुच्चय में सभी बहुभुज की भुजाओं को समान समन्वय अक्षों के साथ संरेखित किया जाता है। दूसरी परिभाषा के ढांचे के भीतर एक आयताकार बहुभुज के क्षैतिज किनारों और ऊर्ध्वाधर किनारों के बारे में बात करना स्वाभाविक है।

ऋजुरेखीय बहुभुजों को लंबकोणीय बहुभुज के रूप में भी जाना जाता है। आइसो-ओरिएंटेड, एक्सिस-अलाइन्ड और एक्सिस-ओरिएंटेड बहुभुज, उपयोग में आने वाली अन्य शर्तें हैं। जब इस प्रकार के बहुभुज आयत होते हैं तो ये विशेषण कम भ्रामक होते हैं, और शब्द अक्ष-संरेखित आयत को प्राथमिकता दी जाती है, चूंकि लंबकोणीय आयत और आयताकार आयत को उसी शब्द से जाना जाता हैं।

सरलरेखीय बहुभुजों के वर्ग का महत्व निम्नलिखित के अनुसार प्राप्त किया जाता है।

• वे डिजाइन और निर्माण में अपनी सादगी के कारण एकीकृत सर्किट एकीकृत सर्किट लेआउट में आकृतियों के प्रतिनिधित्व के लिए सुविधाजनक हैं। अनेक निर्मित वस्तुओं का परिणाम लंबकोणीय बहुभुज होता है।
• कम्प्यूटेशनल ज्यामिति में समस्याएं बहुभुज के संदर्भ में बताई गई हैं, जो अक्सर लंबकोणीय बहुभुजों तक सीमित होने पर अधिक कम्प्यूटेशनल जटिलता सिद्धांत की अनुमति देती हैं। लंबकोणीय बहुभुजों के लिए आर्ट गैलरी प्रमेय द्वारा एक उदाहरण प्रदान किया गया है, जो मनमाने बहुभुजों की तुलना में अधिक कुशल गार्ड कवरेज की ओर ले जाता है।

तत्व

एक आयताकार बहुभुज के दो प्रकार के किनारे होते हैं: क्षैतिज और लंबवत।

X marks convex corners; O marks concave corners. Blue lines are knobs; red lines are anti-knobs; yellow lines are neither.

• लेम्मा: क्षैतिज किनारों की संख्या ऊर्ध्वाधर किनारों की संख्या के बराबर होती है (क्योंकि प्रत्येक क्षैतिज किनारे के बाद एक ऊर्ध्वाधर किनारा होता है और इसके विपरीत)।
  • कोरोलरी: लंबकोणीय पॉलीगोन में किनारों की एक समान संख्या होती है।

एक सरलरेखीय बहुभुज में दो प्रकार के कोने होते हैं: वे कोने जिनमें छोटा कोण (90°) बहुभुज के आंतरिक होता है, उत्तल कहलाते हैं और वे कोने जिनमें बड़ा कोण (270°) आंतरिक होता है, अवतल कहलाते हैं। एक घुंडी एक किनारा है जिसके दो अंत बिंदु उत्तल कोने होते हैं। एक एंटीकनॉब एक ​​किनारा है जिसके दो अंत बिंदु अवतल कोने होते हैं।

सरल आयताकार बहुभुज

एक आयताकार बहुभुज जो कि सरल बहुभुज भी है, उसे छिद्र-मुक्त भी कहा जाता है क्योंकि इसमें कोई छिद्र नहीं होता है - केवल एक सतत सीमा होती है। इसके अनेक रोचक गुण हैं:

1. उत्तल किनारों की संख्या अवतल किनारों की संख्या से चार अधिक है। यह देखने के लिए, कल्पना करें कि आप बहुभुज की सीमा को दक्षिणावर्त पार करते हैं (अपने दाहिने हाथ को बहुभुज के अंदर और अपने बाएं हाथ को बहुभुज के बाहर की ओर रखकर)। उत्तल कोने पर, आप 90° दाएं मुड़ते हैं और किसी अवतल कोने पर आप 90° बाएँ मुड़ जाते हैं। अंत में आपको संपूर्ण 360° मुड़ना होगा और उस वास्तविक बिंदु पर वापस आना होगा; इसलिए दाएँ घुमावों की संख्या बाएँ घुमावों की संख्या से 4 अधिक होनी चाहिए।
   • उपप्रमेय: प्रत्येक आयताकार बहुभुज में कम से कम 4 उत्तल किनारे होते हैं।
2. नॉब्स (दो उत्तल किनारों को जोड़ने वाली भुजाएँ) की संख्या एंटीनॉब्स (दो अवतल किनारों को जोड़ने वाली भुजाएँ) की संख्या से चार अधिक है। यह देखने के लिए कि ऐसा क्यों होता है, 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।
   • उपप्रमेय: प्रत्येक सरलरेखीय बहुभुज में कम से कम 4 नॉब्स होती हैं।

एक आयताकार बहुभुज में वर्ग और आयत

बहुभुज के किनारों के समानांतर किनारों के साथ एक आयताकार बहुभुज को परिमित संख्या में वर्गों या आयतों द्वारा कवर किया जा सकता है (बहुभुज कवरिंग देखें)। एक निश्चित आयताकार बहुभुज P में निहित अनेक प्रकार के वर्गों/आयतों में अंतर करना संभव है:

बहुभुज पी में एक अधिकतम वर्ग पी में एक वर्ग है जो पी में किसी अन्य वर्ग में शामिल नहीं है। इसी तरह, एक अधिकतम आयत एक आयत है जो 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' जुड़ा नहीं है।

• लेम्मा: एक साधारण आयताकार बहुभुज में, एक अधिकतम वर्ग जिसमें एक घुंडी नहीं होती है, एक विभाजक है। नॉब वाला वर्ग विभाजक हो भी सकता है और नहीं भी। विभिन्न विभाजक वर्गों की संख्या अनंत और बेशुमार भी हो सकती है। उदाहरण के लिए, एक आयत में, प्रत्येक अधिकतम वर्ग जो छोटी भुजाओं में से किसी एक को स्पर्श नहीं करता है, एक विभाजक है।

एक निरंतर वर्ग एक बहुभुज पी में एक वर्ग एस है जैसे कि एस की सीमा और पी की सीमा के बीच का चौराहा निरंतर है। एक अधिकतम निरंतर हमेशा एक कोने वाला वर्ग होता है। इसके अलावा, एक अधिकतम निरंतरता में हमेशा एक घुंडी होती है। इसलिए निरंतरकों की संख्या हमेशा परिमित होती है और घुंडियों की संख्या से बंधी होती है।

उनमें मौजूद घुंडियों की संख्या और उनकी आंतरिक संरचना (चित्र देखें) के आधार पर अनेक अलग-अलग प्रकार के निरंतर हैं। एक निरंतरता के बालकनी को इसके बिंदुओं के रूप में परिभाषित किया गया है जो किसी अन्य अधिकतम वर्ग (चित्र देखें) द्वारा कवर नहीं किया गया है।

कोई वर्ग निरंतर और विभाजक दोनों नहीं हो सकता। सामान्य बहुभुजों में, ऐसे वर्ग हो सकते हैं जो न तो निरंतर और न ही विभाजक हों, लेकिन साधारण बहुभुजों में ऐसा नहीं हो सकता है:# एक साधारण आयताकार बहुभुज में, प्रत्येक अधिकतम वर्ग या तो एक विभाजक या एक निरंतर होता है। यह आयतों के लिए भी सत्य है: प्रत्येक अधिकतम आयत या तो एक विभाजक या एक सतत है।

1. एक साधारण आयताकार बहुभुज में जो एक वर्ग नहीं है, कम से कम दो निरंतर होते हैं।

एक साधारण बहुभुज में अधिकतम वर्गों और एक पेड़ में नोड्स के बीच एक दिलचस्प सादृश्य है: एक निरंतर पत्ती के नोड के अनुरूप है और एक विभाजक एक आंतरिक नोड के अनुरूप है।

विशेष मामले

सबसे सरल आयताकार बहुभुज एक अक्ष-संरेखित आयत है - एक आयत जिसमें 2 भुजाएँ x अक्ष के समानांतर और 2 भुजाएँ y अक्ष के समानांतर होती हैं। यह भी देखें: न्यूनतम बाउंडिंग आयत।

एक जगहें एक सीधीरेखीय बहुभुज है जिसकी भुजाओं की लंबाई लगातार पूर्णांक होती है।

एक सीधीरेखीय बहुभुज जो एक आयत नहीं है, कभी भी उत्तल बहुभुज नहीं होता है, लेकिन यह लम्बवत रूप से उत्तल हो सकता है। लम्बवत उत्तल सरलरेखीय बहुभुज देखें .

एक मोनोटोन रेक्टिलाइनियर बहुभुज एक मोनोटोन बहुभुज है जो रेक्टिलाइनियर भी है।

एक टी-स्क्वायर (फ्रैक्टल) | टी-स्क्वायर दिलचस्प गुणों वाले रेक्टिलाइनियर पॉलीगोन के अनुक्रम से उत्पन्न एक फ्रैक्टल है।

सामान्यीकरण

• पॉलीहेड्रॉन#लंबकोणीय पॉलीहेड्रा - 3डी में ओर्थोगोनल बहुभुजों का प्राकृतिक सामान्यीकरण।
• सीधीरेखीयता [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"