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

चित्रा 1. मनमाना आकार और आकार के त्रिकोण में कम विचलन के साथ एक खुला (अनंत) अर्ध-यादृच्छिक अनुक्रम के निर्माण के लिए एक नई प्रत्यक्ष विधि। आंकड़ा पहले 150 अंकों के लिए पंद्रह यादृच्छिक त्रिकोण में अंकों के वितरण को दर्शाता है।

संक्षिप्त समीक्षा

कम विसंगति के अनुक्रम जो समान रूप से नमूना / एक वर्ग भरते हैं, लगभग सौ वर्षों तक सक्रिय रूप से अध्ययन किया गया है। इनमें से अधिकांश अर्ध-यादृच्छिक अनुक्रमों को सरल खिंचाव द्वारा आयतों तक विस्तारित किया जा सकता है, बिना विसंगति को काफी नुकसान पहुंचाए।

हालांकि, इस पोस्ट में हम एक मनमाना त्रिकोण में कम विचलन के साथ दृश्यों के एक दिलचस्प और महत्वपूर्ण विस्तार पर विचार करेंगे।

जहाँ तक मैं समझ सकता था, एक त्रिभुज में समान रूप से वितरित बिंदुओं और अनुक्रमों के सेट के निर्माण पर बहुत कम ध्यान दिया गया था। बसु [२०१४] , पिलंड्स [२००५] और ब्रैंडोलिनी [२०१३] द्वारा हाल के वर्षों के उल्लेखनीय कार्य मुख्य हैं, यदि इस विषय पर केवल लेख नहीं हैं।

ये लेखक आमतौर पर एक बहुत ही सैद्धांतिक और विश्लेषणात्मक कोण से इस समस्या पर विचार करते हैं, और लगभग हमेशा इसे एक ही नियमित त्रिकोण के लिए हल करते हैं। उनके विपरीत, मेरी पोस्ट मुख्य रूप से ग्राफिक्स के प्रतिपादन में व्यावहारिक तकनीकों के विकास के लिए है।

पोस्ट प्रत्यक्ष निर्माण की एक सरल विधि का वर्णन करती है, जिसे स्वीकृति / बहिष्करण, या त्याग या पुनरावृत्ति की आवश्यकता नहीं होती है; और सबसे महत्वपूर्ण बात यह है कि इसे मनमाने आकार और आकार के त्रिभुजों पर लागू किया जा सकता है।

पोस्ट में चार खंड हैं:

चुकता यादृच्छिक क्रम
एक त्रिकोण पर एक इकाई वर्ग ओवरले।
विकृति में कमी
आगे सामान्यीकरण

1. बिन्दुओं का अर्ध-क्रमबद्ध क्रम

आप सोच सकते हैं कि एक वर्ग में 100 अंक रखना ताकि आसन्न बिंदुओं के बीच न्यूनतम दूरी जितनी बड़ी हो सके उतना आसान हो। लेकिन क्या होगा अगर आपको 13 अंक रखने की आवश्यकता है? 47? 2019 अंक के बारे में क्या!

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

एक और क्रम है जो मुझे उपयोग करना पसंद है, उत्कृष्ट स्थानीय के साथ-साथ वैश्विक गुणों के साथ। यही क्रम है

R_{2}

$R_2$ मेरी पिछली पोस्ट में विस्तार से वर्णित है "अर्ध-यादृच्छिक अनुक्रमों की अप्रत्याशित दक्षता" ।

संक्षेप में, हम एक अनंत द्वि-आयामी अनुक्रम को परिभाषित करते हैं

R_{2}

$R_2$ ऐसा है

\ pmb {t} _n = \ left \ {p \ _ \ _ {अल्फा} \ right \} \ quad n = 1,2,3, ... \ pmb {t} _n = \ left \ {n \ pmb {\ _ अल्फा} \ right \} \ quad n = 1,2,3, ...

$\ pmb {t} _n = \ left \ {p \ _ \ _ {अल्फा} \ right \} \ quad n = 1,2,3, ... \ pmb {t} _n = \ left \ {n \ pmb {\ _ अल्फा} \ right \} \ quad n = 1,2,3, ...$

t e x t r m ज ह ा ं q u a d p m b A l p h a = l e f t (f r a c 1 g, f r a c 1 g^{2} r i g h t),

$\ textrm {जहां} \ quad \ pmb {\ Alpha} = \ left (\ frac {1} {g}, \ frac {1} {g ^ 2} \ right),$

t e x t r m औ र g s i m e q 1.32471795572 ट ै ग 1

$\ textrm {और} \; g \ simeq 1.32471795572 \ टैग {1}$

इस विशेष अर्थ के बारे में और पढ़ें।

ज ी

$जी$ , जिसे अक्सर "प्लास्टिक स्थिरांक" कहा जाता है, विकिपीडिया या मैथवर्ल्ड पर पढ़ा जा सकता है।

नतीजतन, चित्रा 2 एक कम विचलन (और तुलना के लिए एक सरल वर्दी यादृच्छिक नमूना) के साथ विभिन्न दृश्यों की तुलना दिखाता है। जैसा कि आप देख सकते हैं, यह यादृच्छिक नमूना अंकों के संचय को प्रदर्शित करता है। इसके अलावा, इसमें ऐसे क्षेत्र होते हैं जिनमें बिल्कुल भी बिंदु नहीं होते हैं ("श्वेत शोर"), जबकि निम्न विचलन वाला अर्ध-यादृच्छिक अनुक्रम नियतात्मक तरीके से अंकों के (अनंत) अनुक्रम के निर्माण की एक विधि है ताकि किसी भी स्तर पर रखे गए अंक समान रूप से वितरित किए जा सकें अंतरिक्ष।

चित्रा 2. विभिन्न कम-विचलन क्वैसी-यादृच्छिक अनुक्रमों के पहले 150 सदस्यों का चित्रण। ध्यान दें कि वे सभी एक समान वर्दी यादृच्छिक वितरण (नीचे बाएं) की तुलना में अंतरिक्ष में अधिक समान रूप से वितरित अंक बनाते हैं।

2. एक त्रिकोण पर एक इकाई वर्ग का आरोपण

त्रिभुज से समान यादृच्छिक नमूने सुनिश्चित करने के लिए तीन प्रसिद्ध तरीके हैं:

समांतर चतुर्भुज विधि
क्रेमर की विधि और
उलटा संभावना वितरण विधि।

चित्रा 3. समांतर चतुर्भुज विधि

समांतर चतुर्भुज विधि इस प्रकार है।

त्रिभुज के लिए

\ p {{एबीसी}

$\ p {{एबीसी}$ एक समांतर चतुर्भुज पर विचार करें

p m b A B C A^{'}

$\ pmb {ABCA '}$ ।

एक इकाई वर्ग के एक बिंदु के लिए

(r_{1}, r_{2})

$(r_1, r_2)$ ऐसे बिंदु निर्धारित करें

p m b P

$\ pmb {P}$ कि

p m b P = r_{1} p m b A C + r_{2} p m b A B

$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$ ।

यह बिंदु हमेशा समांतर चतुर्भुज के अंदर होगा। हालांकि, अगर यह एक अतिरिक्त त्रिकोण में प्रकट होता है

p m b A B C^{'}

$\ pmb {ABC '}$ फिर हमें इसे त्रिकोण में वापस फ्लिप करने की आवश्यकता है

\ p {{एबीसी}

$\ p {{एबीसी}$ ।

वह है, अगर

r_{1} + r_{2} < 1

$r_1 + r_2 <1$ तो

p m b P = r_{1} p m b A C + r_{2} p m b A B

$\ pmb {P} = r_1 \ pmb {AC} + r_2 \ pmb {AB}$ लेकिन अगर

r_{1} + r_{2} > 1

$r_1 + r_2> 1$ तो

p m b P = (1 - r_{1}) p m b A C + (1 - r_{2}) p m b A B

$\ pmb {P} = (1-r_1) \ pmb {AC} + (1-r_2) \ pmb {AB}$ ।

हालांकि, यह समझना बहुत महत्वपूर्ण है कि भले ही ये विधियां त्रिभुज से एक समान नमूना प्रदान करती हैं, इसका मतलब यह नहीं है कि इस तरह के परिवर्तन से हमारे अर्ध-यादृच्छिक बिंदुओं की एक समान स्थानिक व्यवस्था (यानी, कम विचलन) को संरक्षित किया जाएगा।

उदाहरण के लिए, समांतर चतुर्भुज विधि के मामले में, प्रतिबिंब अक्सर एक बिंदु में किसी अन्य मौजूदा बिंदु के बहुत करीब हो सकता है। जाहिर है, यह कम-विचलन संरचना को नष्ट कर देता है और विरूपण / पट्टी के रूप में प्रकट होता है।

इसी प्रकार, व्युत्क्रम प्रायिकता वितरण विधि बिंदुओं पर अरेखीय विकृति लागू करती है। हॉल्टन और सेबल अनुक्रमों में, इसका मतलब है कि दो बिंदु बहुत बार खुद को बहुत करीब से एक साथ धकेलते हैं।

चित्रा 4 दिखाता है कि समानांतर चतुर्भुज विधि का उपयोग करके एक इकाई वर्ग से एक त्रिकोण में एक क्षेत्र को बदलते समय विभिन्न अर्ध-यादृच्छिक अनुक्रमों में से प्रत्येक में कितनी अच्छी तरह से कम विसंगति बनी हुई है।

चित्रा 4. एक त्रिकोण में विभिन्न अर्ध-यादृच्छिक अनुक्रमों के परिवर्तन की तुलना। ऊपर होल्टन अनुक्रम है, मध्य में सेबल अनुक्रम है, नीचे अनुक्रम है

$R_2$ । यह देखा जा सकता है कि होल्टन अनुक्रम में अंकों की महत्वपूर्ण भीड़ होती है, और सोबोल अनुक्रम में महत्वपूर्ण बैंड गठन होता है। उनकी तुलना में, क्रम में

$R_2$ अंक बहुत समान रूप से वितरित किए जाते हैं, और लगभग कोई ध्यान देने योग्य भीड़ या धारियां नहीं होती हैं।

तीन अलग-अलग त्रिभुज विधियों और कई अलग-अलग अर्ध-यादृच्छिक अनुक्रमों में, समांतर चतुर्भुज विधि अनुक्रम विधि पर लागू होती है

$R_2$ एकमात्र संयोजन है जो निरंतर परिणाम बनाता है जो विरूपण के बिना कम विचरण बनाए रखने के मामले में स्वीकार्य हैं।

इस संयोजन के उत्कृष्ट परिणामों को चित्र 5 में अधिक विस्तार से जांचा जा सकता है।

चित्रा 5. आप देख सकते हैं कि परिवर्तित अनुक्रम

$R_2$ समान रूप से कई वितरित करने के लिए एक बहुत ही सरल लेकिन प्रभावी तरीका प्रदान करता है

$एन$ त्रिकोण में अंक। यह एक्यूट-एंगल्ड और ऑब्ल्ट-एंगल्ड ट्राइंगल के साथ काम करता है। (रंग व्यवस्था को इंगित करता है)।

3. अन्य पहलू

विकृति

समांतर चतुर्भुज विधि को आधार वैक्टर के रूप में त्रिकोण के दो पक्षों की पसंद की आवश्यकता होती है।

यदि लंबवत यादृच्छिक क्रम में चिह्नित किए जाते हैं, तो अंक के पैटर्न आमतौर पर चित्र 6 में दिखाए गए समान होते हैं।

चित्रा 6. बेतरतीब ढंग से कोने के क्रम का चयन करके प्राप्त अंकों के पैटर्न। ध्यान दें कि ज्यादातर मामलों में, विरूपण स्पष्ट रूप से ध्यान देने योग्य है।

हालांकि, यह पता चला है कि कोने के क्रम की सावधानीपूर्वक पसंद के साथ, विकृतियों को काफी कम किया जा सकता है। सबसे विशेष रूप से, यदि आप त्रिकोण को लेबल करते हैं ताकि

ए

$ए$ सबसे बड़ा कोण है (यानी, सबसे बड़ा पक्ष इसके खिलाफ है), फिर पक्ष

p m b A B

$\ pmb {AB}$ और

p m b A C

$\ pmb {AC}$ एक समांतर चतुर्भुज के दो पक्षों के रूप में उपयोग किया जाता है।

यदि हम यह आदेश लेते हैं, तो हमें आंकड़े 1, 4 और 5 में दिखाए गए बिंदुओं के पैटर्न मिलते हैं।

हालांकि, यहां तक कि एक निश्चित क्रम के साथ, कुछ मामलों में, विरूपण प्रभाव अभी भी ध्यान देने योग्य हैं। वे सबसे अधिक ध्यान देने योग्य होते हैं जब त्रिकोण में कोणों में से एक बहुत छोटा होता है। प्रसूति त्रिकोण के मामले में, जब सबसे छोटा कोण 30 डिग्री से कम होता है, तो कुछ विकृति ध्यान देने योग्य होती है, और तीव्र-कोण वाले त्रिकोण के मामले में, जब सबसे छोटा कोण 20 डिग्री से कम होता है, तो विरूपण दिखाई देता है। (यदि नमूना किए गए त्रिकोण Delaunay जाल का हिस्सा हैं, तो ऐसी विकृति समस्याएं न्यूनतम हो सकती हैं, क्योंकि Delaunay त्रिकोण विशेष रूप से छोटे कोणों के साथ त्रिकोणों की संख्या को कम करने के लिए डिज़ाइन किया गया है।)

अन्य आकार

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

R_{2} R_{2}

$R_2R_2$ कम विचलन के साथ, आप गौसियन वक्र द्वारा बंधे क्षेत्र में परिवर्तित कर सकते हैं, जबकि बिंदुओं के बीच एक समान दूरी बनाए रखते हैं।

एक त्रिकोण में अंक का समान वितरण