Delaunay refinement
जाली उत्पादन में, डेलाउने परिष्करण जाली उत्पादन के लिए एल्गोरिदम हैं जो जाली लगाने के लिए एक इनपुट की ज्यामिति में स्टेनर बिंदुओं को जोड़ने के सिद्धांत पर आधारित हैं, इस तरह से जो जाली अनुप्रयोग की गुणवत्ता आवश्यकताओं को पूरा करने के लिए डेलाउने त्रिकोण या संवर्धित इनपुट के बाधित डेलाउने त्रिकोण का कारण बनता है। विलम्ब परिष्करण विधियों में चबाने और रूपर्ट द्वारा विधियाँ शामिल हैं। च्यू का दूसरा एल्गोरिथ्म च्यू का दूसरा एल्गोरिथ्म एक पीसवाइज रैखिक प्रणाली (पी. एल. एस.) लेता है और केवल गुणवत्ता वाले त्रिकोणों का एक सीमित डेलाउने त्रिकोण देता है जहां गुणवत्ता को एक त्रिकोण में न्यूनतम कोण द्वारा परिभाषित किया जाता है। एल. पॉल च्यू द्वारा त्रि-आयामी स्थान में एम्बेडेड मेशिंग सतहों के लिए विकसित, च्यू के दूसरे एल्गोरिथ्म को कुछ मामलों में रूपर्ट के एल्गोरिथ्म पर व्यावहारिक लाभों के कारण द्वि-आयामी मेश जनरेटर के रूप में अपनाया गया है और यह स्वतंत्र रूप से उपलब्ध त्रिभुज पैकेज में लागू किया गया डिफ़ॉल्ट गुणवत्ता वाला मेश जनरेटर है। च्यू के दूसरे एल्गोरिथ्म को समाप्त करने और लगभग 28.6 डिग्री तक न्यूनतम कोण के साथ एक स्थानीय सुविधा आकार-श्रेणीकृत जाली का उत्पादन करने की गारंटी है। एल्गोरिथ्म इनपुट शीर्षों के एक सीमित डेलॉने त्रिकोण के साथ शुरू होता है। प्रत्येक चरण में, एक खराब गुणवत्ता वाले त्रिभुज के परिधि केंद्र को एक अपवाद के साथ त्रिभुज में डाला जाता हैः यदि परिधि केंद्र खराब गुणवत्ता वाले त्रिभुज के रूप में एक इनपुट खंड के विपरीत दिशा में स्थित है, तो खंड का मध्य बिंदु डाला जाता है। इसके अलावा, मूल खंड के व्यास गेंद के अंदर (विभाजित होने से पहले) पहले डाले गए किसी भी परिधि केंद्र को त्रिभुज से हटा दिया जाता है। सर्कमसेंटर सम्मिलन को तब तक दोहराया जाता है जब तक कि कोई खराब गुणवत्ता वाला त्रिकोण मौजूद न हो। रूपर्ट का एल्गोरिथ्म रूपर्ट का एल्गोरिथ्म एक समतल सीधी रेखा ग्राफ (या दो से अधिक आयाम में एक पीसवाइज रैखिक प्रणाली) लेता है और केवल गुणवत्ता वाले त्रिकोणों का एक अनुरूप डेलाउने त्रिकोण देता है। एक त्रिभुज को खराब गुणवत्ता वाला माना जाता है यदि इसका परिधि से सबसे छोटा किनारे का अनुपात कुछ निर्धारित सीमा से अधिक है। 1990 के दशक की शुरुआत में जिम रूपर्ट द्वारा खोजा गया, "द्वि-आयामी गुणवत्ता वाले जाल उत्पादन के लिए रूपर्ट का एल्गोरिथ्म शायद पहला सैद्धांतिक रूप से गारंटीकृत मेशिंग एल्गोरिथ्म है जो व्यवहार में वास्तव में संतोषजनक है।" अभिप्रेरणा कम्प्यूटेशनल फ्लूइड डायनामिक्स जैसे कंप्यूटर सिमुलेशन करते समय, एक विंग सेक्शन की 2डी रूपरेखा जैसे मॉडल के साथ शुरुआत की जाती है। 2डी परिमित तत्व विधि के लिए इनपुट त्रिभुजों के रूप में होना चाहिए जो सभी स्थान को भरते हैं, और प्रत्येक त्रिभुज को एक प्रकार की सामग्री से भरा जाना चाहिए-इस उदाहरण में, या तो "वायु" या "पंख"। लंबे, पतले त्रिकोणों का सटीक अनुकरण नहीं किया जा सकता है। अनुकरण का समय आम तौर पर त्रिभुजों की संख्या के समानुपाती होता है, और इसलिए कोई भी त्रिभुजों की संख्या को कम करना चाहता है, जबकि अभी भी उचित रूप से सटीक परिणाम देने के लिए पर्याप्त त्रिभुजों का उपयोग करता है-आमतौर पर एक असंरचित ग्रिड का उपयोग करके। कंप्यूटर बहुभुज मॉडल को परिमित तत्व विधि के लिए उपयुक्त त्रिकोणों में बदलने के लिए रूपर्ट के एल्गोरिदम (या कुछ समान मेशिंग एल्गोरिदम) का उपयोग करता है। एल्गोरिदम एल्गोरिदम इनपुट शीर्षों के डेलाउने त्रिकोण के साथ शुरू होता है और फिर इसमें दो मुख्य संचालन होते हैं। गैर-खाली व्यास वृत्त वाले खंड के मध्य बिंदु को त्रिभुज में डाला जाता है। एक खराब गुणवत्ता वाले त्रिभुज के परिधि केंद्र को त्रिभुज में डाला जाता है, जब तक कि यह परिधि केंद्र किसी खंड के व्यास वृत्त में न हो। इस मामले में, इसके बजाय अतिक्रमण किए गए खंड को विभाजित किया जाता है। इन क्रियाओं को तब तक दोहराया जाता है जब तक कि कोई खराब गुणवत्ता वाला त्रिकोण मौजूद नहीं होता है और सभी खंडों का अतिक्रमण नहीं होता है। स्यूडोकोड फलन रूपर्ट (बिंदु, खंड, सीमा) है टीः = डेलाउनेत्रैंगुलेशन (बिंदु) क्यूः = अतिक्रमण किए गए खंडों और खराब गुणवत्ता वाले त्रिकोणों का समूह जबकि क्यू खाली नहीं हैः// मुख्य लूप यदि क्यू में एक खंड एस होता हैः टी में एस का मध्य बिंदु डालें अन्यथा क्यू में खराब गुणवत्ता वाला त्रिकोण टी होता हैः यदि टी का परिधि केंद्र एक खंड एस का अतिक्रमण करता हैः क्यू में एस जोड़ें; अन्यथाः टी के परिधि केंद्र को टी अंत में डालें यदि अंत में क्यू अंत को अपडेट करते हैं और टी अंत रूपर्ट लौटाते हैं। बिना संशोधन के व्यावहारिक उपयोग रूपर्ट के एल्गोरिथ्म को गैर-तीव्र इनपुट और लगभग 20.7 डिग्री से कम किसी भी खराब-गुणवत्ता सीमा के लिए एक गुणवत्ता जाल को समाप्त करने और उत्पन्न करने की गारंटी है। इन प्रतिबंधों में ढील देने के लिए कई छोटे-छोटे सुधार किए गए हैं। छोटे इनपुट कोणों के पास गुणवत्ता की आवश्यकता में ढील देकर, एल्गोरिथ्म को किसी भी सीधी रेखा के इनपुट को संभालने के लिए बढ़ाया जा सकता है। घुमावदार इनपुट को भी इसी तरह की तकनीकों का उपयोग करके जोड़ा जा सकता है। रूपर्ट के एल्गोरिथ्म को स्वाभाविक रूप से तीन आयामों तक बढ़ाया जा सकता है, हालांकि स्लिवर प्रकार के टेट्राहेड्रॉन के कारण इसकी उत्पादन गारंटी कुछ हद तक कमजोर है। स्वतंत्र रूप से उपलब्ध त्रिभुज पैकेज में दो आयामों में रूपर्ट के एल्गोरिदम का एक विस्तार लागू किया गया है। इस पैकेज में रूपर्ट के एल्गोरिदम के दो रूपों को लगभग 26.5 डिग्री की खराब-गुणवत्ता सीमा के लिए समाप्त करने की गारंटी है। व्यवहार में ये एल्गोरिदम 30 डिग्री से अधिक खराब-गुणवत्ता सीमा के लिए सफल हैं। हालाँकि, ऐसे उदाहरण ज्ञात हैं जिनके कारण एल्गोरिथ्म 29.06 डिग्री से अधिक सीमा के साथ विफल हो जाता है। यह भी देखें स्थानीय विशेषता आकार बहुभुज जाल टेटजेन वोरोनोई आरेख संदर्भ आगे पढ़ने के लिए जाल पीढ़ी त्रिभुज (ज्यामिति) वीडियो क्लिप वाले लेख