Delaunay refinement
மெஷ் உற்பத்தியில், டெலவுனே சுத்திகரிப்புகள் என்பது மெஷ் உருவாக்கத்திற்கான வழிமுறைகளாகும், இது மெஷ் செய்யப்பட வேண்டிய ஒரு உள்ளீட்டின் வடிவவியலில் ஸ்டெய்னர் புள்ளிகளைச் சேர்க்கும் கொள்கையின் அடிப்படையில், டெலவுனே முக்கோணத்தை ஏற்படுத்தும் அல்லது மெஷிங் பயன்பாட்டின் தரத் தேவைகளைப் பூர்த்தி செய்ய பெருக்கப்பட்ட உள்ளீட்டின் கட்டுப்படுத்தப்பட்ட டெலவுனே முக்கோணத்தை ஏற்படுத்தும். தாமதமான சுத்திகரிப்பு முறைகளில் செவ் மற்றும் ரூபர்ட் முறைகள் அடங்கும். செவின் இரண்டாவது வழிமுறை செவின் இரண்டாவது வழிமுறை ஒரு துண்டுப்பிரதியாக நேரியல் அமைப்பை (பி. எல். எஸ்) எடுத்து, ஒரு முக்கோணத்தில் உள்ள குறைந்தபட்ச கோணத்தால் தரம் வரையறுக்கப்படும் தரமான முக்கோணங்களின் வரையறுக்கப்பட்ட டெலானே முக்கோணத்தை மட்டுமே வழங்குகிறது. முப்பரிமாண இடத்தில் உட்பொதிக்கப்பட்ட மேற்பரப்புகளை இணைப்பதற்காக எல். பால் செவ் என்பவரால் உருவாக்கப்பட்டது, சில சந்தர்ப்பங்களில் ரூபர்ட்டின் வழிமுறையை விட நடைமுறை நன்மைகள் காரணமாக செவின் இரண்டாவது வழிமுறை இரு பரிமாண மெஷ் ஜெனரேட்டராக ஏற்றுக்கொள்ளப்பட்டுள்ளது, மேலும் இது இலவசமாக கிடைக்கும் முக்கோண தொகுப்பில் செயல்படுத்தப்படும் இயல்புநிலை தரமான மெஷ் ஜெனரேட்டராகும். ச்யூவின் இரண்டாவது வழிமுறை, குறைந்தபட்சம் 28 டிகிரி வரை கோணத்துடன் உள்ளூர் அம்ச அளவு-தரப்படுத்தப்பட்ட மெஷ்களை நிறுத்துவதற்கும் உற்பத்தி செய்வதற்கும் உத்தரவாதம் அளிக்கிறது. வழிமுறை உள்ளீட்டு செங்குத்துகளின் கட்டுப்படுத்தப்பட்ட டெலானே முக்கோணத்துடன் தொடங்குகிறது. ஒவ்வொரு படியிலும், ஒரு மோசமான தரமான முக்கோணத்தின் சுற்றளவு ஒரு விதிவிலக்குடன் முக்கோணத்திற்குள் செருகப்படுகிறதுஃ சுற்றளவு மையம் ஒரு உள்ளீட்டு பிரிவின் எதிர் பக்கத்தில் மோசமான தரமான முக்கோணமாக இருந்தால், பிரிவின் நடுப்புள்ளி செருகப்படுகிறது. மேலும், அசல் பிரிவின் விட்டம் கொண்ட பந்துக்குள் (அது பிரிக்கப்படுவதற்கு முன்பு) முன்பு செருகப்பட்ட சுற்றளவு மையங்கள் முக்கோணத்திலிருந்து அகற்றப்படுகின்றன. மோசமான தரமான முக்கோணங்கள் இல்லாத வரை சர்க்கம் சென்டர் செருகல் மீண்டும் மீண்டும் செய்யப்படுகிறது. ரூபர்ட்டின் வழிமுறை வடிவர்ட்டின் வழிமுறை ஒரு சமதள நேர் கோடு வரைபடத்தை (அல்லது இரண்டுக்கு மேற்பட்ட பரிமாணத்தில் ஒரு துண்டுப்பிரதியாக நேரியல் அமைப்பை) எடுத்து, தரமான முக்கோணங்களின் இணக்கமான டெலானே முக்கோணத்தை மட்டுமே வழங்குகிறது. ஒரு முக்கோணம் ஒரு சுற்றளவு முதல் குறுகிய விளிம்பு விகிதம் சில பரிந்துரைக்கப்பட்ட வரம்பை விட அதிகமாக இருந்தால் அது மோசமான தரமாகக் கருதப்படுகிறது. 1990 களின் முற்பகுதியில் ஜிம் ரூபெர்ட் கண்டுபிடித்தார், "இரு பரிமாண தரமான மெஷ் தலைமுறைக்கான ரூபெர்ட்டின் வழிமுறை நடைமுறையில் உண்மையிலேயே திருப்திகரமாக இருக்கும் முதல் கோட்பாட்டளவில் உத்தரவாதம் அளிக்கப்பட்ட மெஷிங் வழிமுறை". உந்துதல் கணக்கீட்டு திரவ இயக்கவியல் போன்ற கணினி உருவகப்படுத்துதல்களைச் செய்யும்போது, ஒருவர் ஒரு இறக்கைப் பிரிவின் 2டி அவுட்லைன் போன்ற மாதிரியுடன் தொடங்குகிறார். 2டி வரையறுக்கப்பட்ட உறுப்பு முறைக்கான உள்ளீடு அனைத்து இடங்களையும் நிரப்பும் முக்கோணங்களின் வடிவத்தில் இருக்க வேண்டும், மேலும் ஒவ்வொரு முக்கோணமும் ஒரு வகையான பொருளால் நிரப்பப்பட வேண்டும்-இந்த எடுத்துக்காட்டில், "காற்று" அல்லது "விங்". நீளமான, ஒல்லியான முக்கோணங்களை துல்லியமாக உருவகப்படுத்த முடியாது. உருவகப்படுத்துதல் நேரம் பொதுவாக முக்கோணங்களின் எண்ணிக்கைக்கு விகிதாசாரமாக இருக்கும், எனவே ஒருவர் முக்கோணங்களின் எண்ணிக்கையைக் குறைக்க விரும்புகிறார், அதே நேரத்தில் நியாயமான துல்லியமான முடிவுகளை வழங்க போதுமான முக்கோணங்களைப் பயன்படுத்துகிறார்-பொதுவாக கட்டமைக்கப்படாத கட்டத்தைப் பயன்படுத்துவதன் மூலம். பலகோண மாதிரியை வரையறுக்கப்பட்ட உறுப்பு முறைக்கு பொருத்தமான முக்கோணங்களாக மாற்ற கணினி ரூபர்ட்டின் வழிமுறையைப் (அல்லது சில ஒத்த மெஷிங் வழிமுறை) பயன்படுத்துகிறது. அல்காரிதம் அல்காரிதம் உள்ளீட்டு செங்குத்துகளின் டெலவுனே முக்கோணத்துடன் தொடங்கி பின்னர் இரண்டு முக்கிய செயல்பாடுகளைக் கொண்டுள்ளது. வெற்றிடமற்ற விட்ட வட்டங்களைக் கொண்ட ஒரு பிரிவின் நடுப்பகுதி முக்கோணத்திற்குள் செருகப்படுகிறது. ஒரு மோசமான தரமான முக்கோணத்தின் சுற்றளவு முக்கோணத்திற்குள் செருகப்படுகிறது, இந்த சுற்றளவு மையம் சில பிரிவின் விட்ட வட்டத்தில் இல்லாவிட்டால். இந்த வழக்கில், அதற்கு பதிலாக ஆக்கிரமிக்கப்பட்ட பிரிவு பிரிக்கப்படுகிறது. மோசமான தரமான முக்கோணங்கள் இல்லாத வரை மற்றும் அனைத்து பிரிவுகளும் ஆக்கிரமிக்கப்படாத வரை இந்த செயல்பாடுகள் மீண்டும் மீண்டும் செய்யப்படுகின்றன. சூடோகோடு செயல்பாடு ரூபர்ட் (புள்ளிகள், பிரிவுகள், வாசல்) என்பது T: = DelaunayTriangulation (புள்ளிகள்) Q: = ஆக்கிரமிக்கப்பட்ட பிரிவுகளின் தொகுப்பு மற்றும் மோசமான தரமான முக்கோணங்கள், அதே நேரத்தில் Q காலியாக இல்லைஃ// Q இல் ஒரு பிரிவு s இருந்தால் முக்கிய வளையம்ஃ S இன் நடுப்புள்ளியை T இல் செருகவும் இல்லையெனில் Q இல் மோசமான தரமான முக்கோணம் t உள்ளதுஃ t இன் சுற்றளவு ஒரு பகுதியை ஆக்கிரமித்தால் s: S ஐ Q க்குச் சேர்க்கவும்; இல்லையெனில்ஃ T இன் சுற்றளவு மையத்தை T முனையில் செருகவும். மாற்றமின்றி நடைமுறை பயன்பாடு ரூபர்ட்டின் வழிமுறை தீவிரமற்ற உள்ளீடு மற்றும் சுமார் 20.7 டிகிரிக்கு குறைவான எந்தவொரு மோசமான தர வரம்பிற்கும் ஒரு தரமான கண்ணி நிறுத்தப்பட்டு உருவாக்க உத்தரவாதம் அளிக்கிறது. இந்த கட்டுப்பாடுகளை தளர்த்த பல்வேறு சிறிய முன்னேற்றங்கள் செய்யப்பட்டுள்ளன. சிறிய உள்ளீட்டு கோணங்களுக்கு அருகில் தரத் தேவையை தளர்த்துவதன் மூலம், எந்தவொரு நேர் கோடு உள்ளீட்டையும் கையாள வழிமுறை நீட்டிக்கப்படலாம். வளைந்த உள்ளீட்டை இதே போன்ற நுட்பங்களைப் பயன்படுத்தி இணைக்கலாம். ரூபர்ட்டின் வழிமுறையை இயற்கையாகவே மூன்று பரிமாணங்களுக்கு நீட்டிக்க முடியும், இருப்பினும் ஸ்லிவர் வகை டெட்ராஹெட்ரான் காரணமாக அதன் வெளியீட்டு உத்தரவாதங்கள் ஓரளவு பலவீனமாக உள்ளன. இரண்டு பரிமாணங்களில் ரூபர்ட்டின் வழிமுறையின் நீட்டிப்பு இலவசமாக கிடைக்கும் முக்கோண தொகுப்பில் செயல்படுத்தப்படுகிறது. இந்த தொகுப்பில் உள்ள ரூபர்ட்டின் வழிமுறையின் இரண்டு மாறுபாடுகள் சுமார் 26 டிகிரி மோசமான தர வரம்பிற்கு முடிவடையும் என்று உத்தரவாதம் அளிக்கப்படுகிறது. நடைமுறையில் இந்த வழிமுறைகள் 30 டிகிரிக்கு மேல் மோசமான தர வரம்புகளுக்கு வெற்றிகரமாக உள்ளன. இருப்பினும், 29.06 டிகிரிகளை விட அதிகமான வரம்புடன் வழிமுறை தோல்வியடைவதற்கான எடுத்துக்காட்டுகள் அறியப்படுகின்றன. மேலும் காண்க உள்ளூர் அம்ச அளவு பலகோண கண்ணி டெட்ஜென் வோரோனோய் வரைபடம் குறிப்புகள் மேலும் படிக்க கண்ணி தலைமுறை முக்கோணம் (வடிவியல்) வீடியோ கிளிப்களைக் கொண்ட கட்டுரைகள்